### Random graphs and the parity quantifierRandom graphs and the parity quantifier

Access Restriction
Subscribed

 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

Source: ACM Digital Library