Fri Feb 25, 2011
60 Evans Hall, 4:10–6 PM
Phokion G. Kolaitis (Professor of Computer Science, University of California, Santa Cruz)
Random Graphs and the Parity Quantifier
The classical zero-one law for first-order logic asserts that the asymptotic probability of every first-order definable property of finite graphs always exists and is either zero or one. Over the years zero-one laws have been established for numerous extensions of first-order logic, including least-fixed point logic, finite-variable infinitary logics, and certain fragments of existential second-order logic. The zero-one law, however, fails to hold for any logical formalism that is powerful enough to express parity, that is, the property “there is an odd number of elements”; in fact, for such logical formalisms, even the convergence law fails to hold.
In this work, we turn the parity barrier into a feature and systematically investigate the asymptotic probabilities of properties of finite graphs expressible in first-order logic augmented with the parity quantifier. Our main result is a “modular convergence law” that captures the limiting behavior of properties expressible in this extension of first-order logic on finite graphs.
This is joint work with Swastik Kopparty, Institute for Advanced Study.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium(with support from the Graduate Assembly).