Access Restriction

Author Kolaitis, Phokion G. ♦ Kopparty, Swastik
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Gowers norms ♦ Random graphs ♦ Low-degree polynomials ♦ Subgraph counts ♦ Zero-one laws
Abstract The classical zero-one law for first-order logic on random graphs says that for every first-order property ϕ in the theory of graphs and every $\textit{p}$ ∈ (0,1), the probability that the random graph $\textit{G}(\textit{n},$ $\textit{p})$ satisfies ϕ approaches either 0 or 1 as $\textit{n}$ approaches infinity. It is well known that this law fails to hold for any formalism that can express the parity quantifier: for certain properties, the probability that $\textit{G}(\textit{n},\textit{p})$ satisfies the property need not converge, and for others the limit may be strictly between 0 and 1. In this work, we capture the limiting behavior of properties definable in first order logic augmented with the parity quantifier, FO[⌖], over $\textit{G}(\textit{n},\textit{p}),$ thus eluding the above hurdles. Specifically, we establish the following “modular convergence law”. For every FO[⌖] sentence ϕ, there are two explicitly computable rational numbers $a_{0},$ $a_{1},$ such that for $\textit{i}$ ∈ {0,1}, as $\textit{n}$ approaches infinity, the probability that the random graph $\textit{G}(2\textit{n}+\textit{i},$ $\textit{p})$ satisfies ϕ approaches $a_{i}.$ Our results also extend appropriately to FO equipped with $Mod_{q}$ quantifiers for prime $\textit{q}.$ In the process of deriving this theorem, we explore a new question that may be of interest in its own right. Specifically, we study the joint distribution of the subgraph statistics modulo 2 of $\textit{G}(\textit{n},\textit{p}):$ namely, the number of copies, mod 2, of a fixed number of graphs $F_{1},$ …, $F_{ℓ}$ of bounded size in $\textit{G}(\textit{n},\textit{p}).$ We first show that every FO[⌖] property ϕ is almost surely determined by subgraph statistics modulo 2 of the above type. Next, we show that the limiting joint distribution of the subgraph statistics modulo 2 depends only on $\textit{n}$ mod 2, and we determine this limiting distribution completely. Interestingly, both these steps are based on a common technique using multivariate polynomials over finite fields and, in particular, on a new generalization of the Gowers norm. The first step is analogous to the Razborov-Smolensky method for lower bounds for $AC^{0}$ with parity gates, yet stronger in certain ways. For instance, it allows us to obtain examples of simple graph properties that are exponentially uncorrelated with every FO[⌖] sentence, which is something that is not known for $AC^{0}[⌖].$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 60
Issue Number 5
Page Count 34
Starting Page 1
Ending Page 34

Open content in new tab

   Open content in new tab
Source: ACM Digital Library