% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm} \usepackage{amsmath} \usepackage{amssymb} \usepackage{mathrsfs} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%% %extra shortcuts \newcommand{\beq}[1]{\begin{equation}\label{#1}} \newcommand{\enq}[0]{\end{equation}} \newcommand{\C}[2]{{{#1}\choose{{#2}}}} \newcommand{\ga}[0]{\alpha } \newcommand{\gb}[0]{\beta } \newcommand{\gc}[0]{\gamma } \newcommand{\gd}[0]{\delta } \newcommand{\gD}[0]{\Delta } \newcommand{\gG}[0]{\Gamma } \newcommand{\gl}[0]{\lambda } \newcommand{\gL}[0]{\Lambda} \newcommand{\go}[0]{\omega} \newcommand{\gO}[0]{\Omega} \newcommand{\Om}[0]{\Omega} \newcommand{\gdi}[0]{\delta_i } \newcommand{\gli}[0]{\lambda_i } \newcommand{\gs}[0]{\sigma} \newcommand{\gS}[0]{\Sigma} \newcommand{\gz}[0]{\zeta} \newcommand{\eps}[0]{\varepsilon } \newcommand{\vt}[0]{\vartheta} \newcommand{\td}[1]{\tilde{#1}} \newcommand{\0}[0]{\emptyset} \newcommand{\ra}[0]{\rightarrow} \newcommand{\Ra}[0]{\Rightarrow} \newcommand{\CC}[0]{{\bf C}} \newcommand{\ZZ}[0]{{\bf Z}} \newcommand{\EE}[0]{{\bf E}} \newcommand{\FF}[0]{{\bf F}} \newcommand{\ff}[0]{{\bf f}} \newcommand{\GG}[0]{{\bf G}} \newcommand{\HH}[0]{{\bf H}} \newcommand{\II}[0]{{\bf I}} \newcommand{\KK}[0]{{\bf K}} \newcommand{\MM}[0]{{\bf M}} \newcommand{\PP}[0]{{\bf P}} \newcommand{\RR}[0]{\mbox{${\bf R}^+$}} \newcommand{\Rr}[0]{\mbox{${\bf R}$}} \newcommand{\Nn}[0]{{\bf N}} \newcommand{\VV}[0]{{\bf V}} \newcommand{\XX}[0]{{\bf X}} \newcommand{\YY}[0]{{\bf Y}} \newcommand{\xx}[0]{{\bf x}} \newcommand{\zz}[0]{\mathbf{z}} \newcommand{\A}[0]{{\cal A}} \newcommand{\B}[0]{{\cal B}} \newcommand{\cee}[0]{{\fancyfont C}} %\newcommand{\cee}[0]{{\cal C}} \newcommand{\D}[0]{{\cal D}} \newcommand{\eee}[0]{{\cal E}} \newcommand{\f}[0]{{\cal F}} \newcommand{\g}[0]{{\cal G}} \newcommand{\h}[0]{{\cal H}} \newcommand{\I}[0]{{\cal I}} %\newcommand{\k}[0]{{\cal K}} \newcommand{\m}[0]{{\cal M}} \newcommand{\Oh}[0]{{\cal O}} \newcommand{\pee}[0]{{\cal P}} %\newcommand{\r}[0]{{\cal R}} \newcommand{\s}[0]{{\cal S}} \newcommand{\T}[0]{{\cal T}} \newcommand{\sub}[0]{\subseteq} \newcommand{\sm}[0]{\setminus} \renewcommand{\dots}[0]{,\ldots,} \renewcommand{\iff}[0]{\Longleftrightarrow} \newcommand{\ov}[0]{\overline} \newcommand{\un}[0]{\underline} \newcommand{\uzero}[0]{\underline{0}} \newcommand{\uone}[0]{\underline{1}} \newcommand{\1}[0]{\bf 1} \newcommand{\vol}[0]{{\rm Vol}} \newcommand{\row}[0]{{\rm row}} \newcommand{\sh}[0]{\hat{\sigma}} \newcommand{\zit}[1]{\gz^{Tr({#1})}} \newcommand{\Qx}[0]{Q^x} \newcommand{\Bx}[0]{\B^x} \newcommand{\Var}[0]{{\rm Var}} \newcommand{\win}[0]{{\rm win}} \newcommand{\gap}[0]{{\rm gap}} \newcommand{\covby}[0]{<\hspace{-0.09in}\cdot~} \newcommand{\cov}[0]{~\cdot\hspace{-0.09in}>} \newcommand{\hcl}[0]{{\rm hc}(\gl)} \newcommand{\alam}[0]{\ga_{\gl}} \newcommand{\plam}[0]{p_{\gl}} \newcommand{\plg}[0]{p^G_{\gl}} \newcommand{\ba}[0]{2^{[n]}} \newcommand{\BA}[0]{\{0,1\}^{S}} \newcommand{\lra}[0]{\longleftrightarrow} \newcommand{\Da}[0]{\Downarrow} \newcommand{\Ua}[0]{\Uparrow} \newcommand{\da}[0]{\downarrow} \newcommand{\ua}[0]{\uparrow} \newcommand{\E}[0]{{\sf E}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf Modular statistics for subgraph counts \\in sparse random graphs} \author{Bobby DeMarco\thanks{Supported by NSF grant DMS1201337.}\\ \small\tt rvdemarco@gmail.com \and Jeff Kahn\thanks{Supported by NSF grant DMS1201337.} \\ \small Department of Mathematics\\[-0.8ex] \small Rutgers University\\[-0.8ex] \small Piscataway, NJ, USA\\ \small\tt jkahn@math.rutgers.edu \and Amanda Redlich\thanks{Supported by NSF Award No. 1004382.}\\ \small Department of Mathematics\\[-0.8ex] \small Bowdoin College\\[-0.8ex] \small Brunswick, ME, USA\\ \small\tt aredlich@bowdoin.edu } \date{\dateline{Feb 6, 2014}{Jan 27, 2015}\\ \small Mathematics Subject Classifications: 05C80, 03C13} \begin{document} \maketitle \begin{abstract} Answering a question of Kolaitis and Kopparty, we show that, for given integer $q>1$ and pairwise nonisomorphic connected graphs $G_1\dots G_k$, if $p=p(n) $ is such that $\Pr(G_{n,p}\supseteq G_i)\rightarrow 1$ $\forall i$, then, with $\xi_i$ the number of copies of $G_i$ in $G_{n,p}$, $(\xi_1\dots \xi_k)$ is asymptotically uniformly distributed on ${\bf Z}_q^k$. \end{abstract} \section{Introduction} For graphs $G, H$ write $N(G,H)$ for the number of unlabeled copies of $H$ in $G$ (e.g. $N(K_r,K_s) = \C{r}{s}$). We use both $G_{n,p}$ and $G(n,p)$ for the ordinary (``binomial" or ``Erd\H{o}s-R\'enyi") random graph. We are interested here in extending to nonconstant $p$ the following beautiful result of Kolaitis and Kopparty \cite{kk}. \begin{theorem}\label{TKK} Fix an integer $q>1$, $p\in (0,1)$ and pairwise nonisomorphic connected graphs $G_1\dots G_k$, each with at least two vertices, and let $\xi_i $ be $ N(G_{n,p},G_i) \pmod{q}$. Then the distribution of $\xi = (\xi_1\dots \xi_k)$ is $e^{-\gO(n)}$-close to uniform on $\ZZ_q^k$. In particular, for each $a\in \ZZ_q^k$, $ \Pr(\xi =a)\ra q^{-k} $ as $n\rightarrow \infty$. \end{theorem} % \noindent (Recall two distributions are $\eps$-{\em close} if their statistical (a.k.a. variation) distance is at most $\eps$.) Essentially, this theorem states that for constants $p$ and $q$, subgraphs of $G(n,p)$ are uniformly distributed modulo $q$. Theorem \ref{TKK} was motivated by an application to 0-1 laws for first order logic with a parity quantifier or, more generally, a quantifier that allows counting modulo $q$; see Section \ref{Discussion} for a little more on this. A natural question raised in \cite{kk} (and communicated to the authors by S.K.) asks, to what extent does Theorem \ref{TKK} remain true if $p$ is allowed to tend to zero as $n $ grows, e.g. if $p=n^{-\ga}$ for some fixed $\ga>0$? Our purpose here is to answer this question. We need a little notation. For a graph $H=(V,E)$, set $v_H=|V|$, $e_H=|H|:=|E|$, $\rho(H)= e_H/v_H$ and $m(H) = \max\{\rho(H'):H'\sub H, v_{H'}>0\}$. Recall (see e.g. \cite{JLR}) that $n^{-1/m(H)}$ is a threshold function for containment of $H$; that is, the probability that $G_{n,p}$ ($p=p(n)$) contains a copy of $H$ tends to 0 if $pn^{1/m(H)}\ra 0$ and to 1 if $pn^{1/m(H)}\ra \infty$. Given a collection $\g$ of graphs, set $m(\g) =\max\{m(G):G\in\g\}$, $p_\g(n) = n^{-1/m(\g)}$ and $$ \Phi_\g(n,p) = \min_{G\in \g}\min\{n^{v_H}p^{e_H}:H\sub G ,v_H>0\}. $$ \begin{theorem}\label{MT} Let q, $G_1\dots G_k$ and $\xi=(\xi_1\dots \xi_k)$ be as in Theorem \ref{TKK} and $\g=\{G_1\dots G_k\}$. If $p=\omega(p_\g(n))$, then the distribution of $\xi$ is $\exp[-\gO(\Phi_\g(n,p))]$-close to uniform on $\ZZ_q^k$. \end{theorem} \noindent (Of course the constant in the exponent depends on $q$ and $\g$.) Suppose e.g. that $q=k=2$, $G_1=K_3$, and $G_2=K_4$. Then $m(\g)=m(G_2)=3/2$ ($m(G_1)=1$) and $p_\g(n)=n^{-2/3}$, so the theorem says that, asymptotically speaking, the parities of the numbers of copies of $K_3$ and $K_4$ are independent with each equally likely to be even or odd, provided $p=\omega(n^{-2/3})$. For the special case $\g=\{K_3\}$, a somewhat weaker version of Theorem~\ref{MT}---with $\exp[-\gO(\Phi_\g(n,p))]$ replaced by something polynomial in $n$ and $p$---has been shown by Noga Alon \cite{SKPC}. \medskip We should also note here an immediate consequence of Theorem \ref{MT}, which again answers a question from \cite{kk}. \begin{corollary}\label{Cor} Let $q$, $\g$ be as in Theorem \ref{TKK}, fix a positive irrational $\ga$, and let $I=\{i\in [k]: m(G_i) < \ga^{-1}\}$ and $J=[k]\sm I$. Then for $p=n^{-\ga}$ and $a\in \ZZ_q^k$ (and $\xi$ as in Theorem \ref{TKK}), $$\Pr(\xi=a)\ra \left\{\begin{array}{ll} q^{-|I|}&\mbox{if $a_j=0 ~\forall j\in J$,}\\ 0&\mbox{otherwise.} \end{array}\right. $$ \end{corollary} \noindent This is of interest partly for its possible relevance to proving a modular convergence law (again see Section \ref{Discussion}) for $p=n^{-\ga}$ with $\ga$ irrational ({\em cf.} \cite[Theorem 6]{ss}, which says that for such $p$ a 0-1 law holds for any first order property); but we also have, again from \cite{kk}: ``Even the behavior of subgraph frequencies mod 2 in this setting [i.e. with $p$ as in Corollary \ref{Cor}] seems quite intriguing." \medskip The proof of Theorem \ref{MT}, given in the next section, is similar to that of Theorem \ref{TKK} in \cite{kk}. In truth, we just add one little idea to the machinery of \cite{kk}; nonetheless, as the proof answers a rather basic question, and was apparently not quite trivial to find, it seems worth recording. \section{Proof}\label{Proof} We will need the following two facts, the first of which, from \cite{kk}, generalizes a result of Babai, Nisan and Szegedy \cite{bns}. \begin{lemma}\label{poly} Let $q>1$ and $d>0$ be integers and $p \in (0,1)$. Let $\mathcal{F}\subseteq 2^{[m]}$ and let $Q(z_{1}, \ldots z_{m})\in\ZZ_{q}[z_{1},\ldots z_{m}]$ be a polynomial of the form $$\sum_{S \in \mathcal{F}}a_{S} \prod_{i \in S}z_{i}+Q'(z_{1},\ldots z_{m}),$$ where $\deg (Q')1$ be an integer and $\omega \in \CC$ a primitive $q^{th}$-root of unity. Let $\xi=(\xi_1, \ldots, \xi_l)$ be a random variable taking values in $\ZZ_{q}^{l}$. Suppose that for every nonzero $c \in \ZZ^{l}_{q}$, $$|\E[\omega^{\sum c_i \xi_i}]|\leq \epsilon.$$ Then the distribution of $\xi$ is $(q^{l}\epsilon)$-close to uniform on $\ZZ^{l}_{q}$. \end{lemma} \begin{proof}[Proof of Theorem \ref{MT}] Letting $e$ run over edges of $K_n$, the argument of \cite{kk} expresses each $\sum c_i\xi_i$ in the natural way as a polynomial in the indicators $\mathbf{z}_e:={\bf 1}_{\{e\in G(n,p)\}}$ ($e\in E(K_n)$)---namely, $$ \sum_i c_i\xi_i =\sum_i c_i\sum\{\prod_{e\in H}\mathbf{z}_e: G_i\cong H\sub K_n\} $$ ---and for the $\eee$ of Lemma \ref{poly} uses $\gO(n)$ vertex-disjoint copies of some largest $G_i$ among those with $c_i\neq 0$. The problem with this in the present situation is the (hidden) dependence of the bound in \eqref{Eomega} on $p$. We get around this difficulty by choosing our random graph in two steps, so that when we come to apply Lemma \ref{poly} we are back to constant $p$. % For simplicity we now write $\Phi$ for $\Phi_\g(n,p)$, $\GG '$ for $G(n,2p)$ and $\GG $ for the random subgraph of ${\bf G'}$ in which each edge is present, independently of other choices, with probability 1/2; in particular, our $\xi_i$'s are functions of $\GG $ ($=G(n,p)$). \medskip Given $\GG'$, we will apply Lemma \ref{poly} with variables $\mathbf{z}_e ={\bf 1}_{\{e\in \GG \}}$ ($e\in \GG'$), $\f$ the collection of copies of $G_1\dots G_k$ in $\GG'$, and $\mathcal{E}\sub \f$ a large collection of vertex-disjoint copies of an appropriate $G_i$; so first of all we need existence of such an $\eee$. For a given $\eps$, let $\D=\D_\eps $ be the event that $\GG'$ contains, for each $i$, a collection of $r:=\eps \Phi$ vertex-disjoint copies of $G_i$. \begin{proposition}\label{Dprop} There is a fixed $\eps>0$ (depending on $\g$) for which \beq{PrD} \Pr(\ov{\D}) < \exp[-\gO(\Phi)]. \enq \end{proposition} \noindent {\em Proof.} Though we don't know a reference, this is presumably not new and the ideas needed to prove it may all be found in \cite{JLR}; so we just indicate what's involved. Fix $i\in [k]$ and write $H$ for $G_i$. Let $Y$ be the maximum size of a collection of disjoint copies of $H$ in $\GG'$. It is enough to show that the (more properly, ``a") {\em median} of $Y$ is $\gO( \Phi)$; \eqref{PrD} then follows {\em via} an inequality of Talagrand (\cite{Talagrand} or \cite[Theorem 2.29]{JLR}) as in the argument for the edge-disjoint analogue of Proposition~\ref{Dprop} given on page 77 of \cite{JLR}. (In our case Talagrand's inequality says that for a median $m$ of $Y$ and $t>0$, $\Pr(Y\leq m-t) \leq 2\exp[-t^2/(4\psi(m))]$, where $\psi(r) =r|H|$.) For a lower bound on the median of $Y$, write $X$ for the number of copies of $H$ (in $\GG'$) and $Z$ for the number of (unordered) pairs of non-disjoint copies. Then: \medskip\noindent (i) $\E(X) =\gO(\Phi)$ (this is immediate from the definitions); \medskip\noindent (ii) w.h.p. $X>(1-o(1))\E X$ (a basic application of the 2nd moment method; see \cite[Remark 3.7]{JLR}); \medskip\noindent (iii) $\E Z \frac{(1-o(1))\E^2X}{\E X + 8c\E^2X/\Phi} =\gO(\Phi) \] (where the first inequality uses the fact that $x^2/(x+2z)$ is increasing in $x$ for $x,z>0$).\qed \medskip In view of Proposition~\ref{Dprop} it is enough to show that for any $G'$ satisfying $\D$, the conditional distribution of $\xi$ given $\{{\bf G'}=G'\}$ is $\exp[-\Omega(\Phi)]$-close to uniform on $\ZZ_q^k$. % Given such a $G'$ and $\uzero\neq c\in \ZZ_q^k$, take $\f_i$ to consist of all copies of $G_i$ in $G'$ ($i\in [k]$) and $\f=\cup \{\f_i:c_i\neq 0\}$. Fix, in addition, some $i_0\in [k]$ with $c_{i_0}\neq 0$ and $|G_{i_0}|=\max\{|G_i|:c_i\neq 0\}=:d$, and some $\eee=\{E_1\dots E_r\}\sub \f_{i_0}$, with the $E_i$'s vertex-disjoint. We have $$ \sum_{i\in [k]} c_i\xi_i = \sum_{i\in [k]}c_i\sum_{H\in \f_i}\prod_{e\in H}\zz_e =: Q(\zz), $$ where $\zz_e = {\bf 1}_{\{e\in \GG\}}$ for $e\in G'$. % We then need to say that $Q$, $\f$ and $\eee$ (with $q, d$ and $p=1/2$) satisfy the requirements of Lemma \ref{poly}. But the first three of these are immediate and the fourth follows from the connectivity of the $G_i$'s: for $H\in \f\sm\eee$, if $V(H)\not\sub V(E_i) ~\forall i$, then (since $H$ is connected and the $E_i$'s are vertex-disjoint) $H\not\sub \cup E_i$, whence $|H\cap (\cup E_i)|<|H|\leq d$; otherwise we have $V(H)\sub V(E_j)$ for some $j$ and, since $H\neq E_j$, $|H\cap (\cup E_i)| = |H\cap E_j|< |E_i|=d$. % Thus Lemma \ref{poly} applies, yielding \beq{Eomega'} |\E ~\omega^{Q(z)}| \leq \exp[-\Omega(\Phi)], \enq and then (since this was for any $c\neq\uzero$) Lemma \ref{xor} says that, as desired, the conditional distribution of $\xi$ given $\{{\bf G'}=G'\}$ is $\exp[-\Omega(\Phi)]$-close to uniform on $\ZZ_q^k$. \bigskip\noindent $~$ \end{proof} \section{Discussion}\label{Discussion} As mentioned earlier, Theorem \ref{TKK} is a key ingredient in the proof of the Kolaitis-Kopparty ``modular convergence law" for first order logic with a parity quantifier, or, more generally, a quantifier that allows counting mod $q$. This law says, briefly, that, for fixed $p$ and $n\ra\infty$, the probability of a given sentence in the system under consideration tends to a limit that depends only on the congruence class of $n$ mod $q$. (See also \cite{strange} for an in-depth discussion of 0-1 laws for random graphs.) As suggested in \cite{kk}, it would be interesting to understand to what extent such a law holds in the sparse setting. Theorem \ref{MT} gets about half way to this goal (for $p$ in its range); % but the other half---an assertion like Theorem 2.3 of \cite{kk} to the effect that all relevant information is contained in the subgraph frequencies---seems to require something new, since the quantifier elimination process underlying that step depends critically on properties of $G(n,p)$ that hold for constant $p$ but fail when $p$ tends to zero. \medskip In closing we just mention that it would be interesting to find a proof of Theorem \ref{MT} that proceeds from first principles and does not depend on the ``generalized inner product" polynomials underlying Lemma \ref{poly}. \subsection*{Acknowledgement} We would like to thank Swastik Kopparty for telling us the problem and for helpful conversations on the material of Section \ref{Discussion}. \begin{thebibliography}{10} \bibitem{bns} L. Babai, N. Nisan and M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, in {\em Proc. 21st ACM Symposium on the Theory of Computing}, 1989. \iffalse \bibitem{zo2} R. Fagin, \textit{Probabilities on finite models}, Journal of Symbolic Logic, vol. 41 (1), 1976, pp 50-58. \bibitem{zo1} Yu. V. Glebskii, D. I. Kogan, M. I. Liogon'kii, and V. A. Talanov, \textit{Range and degree of realizability of formulas in the restricted predicate calculus}, Cybernetics and Systems Analysis, vol. 5, Springer New York, 1969, pp 142-154. \fi \bibitem{JLR} S. Janson, T. \L uczak and A. Ruci\'nski, \textit{Random Graphs}, Wiley-Interscience, 2000. \bibitem{SKPC} S. Kopparty, personal communication. \bibitem{kk} P. G. Kolaitis and S. Kopparty, \textit{Random graphs and the parity quantifier}, J. ACM, vol. 60 (5) Article 37, 2013. \bibitem{ss} S. Shelah and J. Spencer, Zero-one laws for sparse random graphs, {\em J. Amer. Math. Soc.} {\bf 1} (1988), 97-115. \bibitem{strange} J. Spencer, \textit{The Strange Logic of Random Graphs}, Springer, 2001 \bibitem{Talagrand} M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, {\em Inst. Hautes \'Etudes Sci. Publ. Math.} {\bf 81} (1995), 73-205. \end{thebibliography} \end{document}