Rehana Patel - Wesleyan University
0-1 Laws for Classes of Graphs with a Forbidden Subgraph
A first order labeled 0-1 law for a class of structures says, essentially, that almost all members of that class look alike when viewed through the lens of first order logic ("almost all", of course, has a precise definition). It is known that the class of all graphs has such a 0-1 law (Glebskii et. al., Fagin); so does each class of K_n-free graphs, n > 2, K_n being the complete graph on n vertices (Kolaitis, Promel and Rothschild). We will identify a criterion under which certain classes of graphs are guaranteed to have a first order labeled 0-1 law. This criterion encompasses the examples cited above. Using this criterion, we will demonstrate the existence of 0-1 laws for a new, infinite family of classes of graphs, which we call the n-kite-free graphs. All definitions will be stated and explained.
[Program Information | Faculty | Mathematics Seminar | Mathematics Links]
[Math Department Home Page | Marist College]