An Application of Logic to Combinatorics
Rishiparna Patel, Department of Mathematics and Computer Science, St. John’s College of Liberal Arts and Sciences
Abstract
Roughly speaking, first order logic is a language with which we can talk about properties of mathematical structures. A class of structures (eg. graphs, partial orders) is said to have a 'labeled first order 0-1 law' if almost all its members look the same, when described in the language of first order logic. It is known that the class of all graphs has a labeled first order 0-1 law (Glebskii et al, Fagin). For any configuration H, for instance a triangle, or a pentagon, we say that a graph G is 'H-free' if the configuration H does not appear anywhere inside G. The class of all K_n-free graphs, n > 2, is also known to have a labeled first order 0-1 law (Kolaitis, Promel and Rothschild). I will provide an easy-to-state condition on a configuration H, which ensures that the class of H-free graphs has a labeled first order 0-1 law. This condition encompasses the previous examples, and gives rise to many new ones.