Zero-One Laws for Existential First-Order Sentences of Bounded Quantifier Depth
Article No.: 12, Pages 1 - 27
Abstract
For any fixed positive integer k, let αk denote the smallest α ∈ (0,1) such that the random graph sequence {G(n, n-α)}n does not satisfy the zero-one law for the set εk of all existential first-order sentences that are of quantifier depth at most k. This article finds upper and lower bounds on αk, showing that as k → ∞, we have α k = (k - 2 - t(k))-1 for some function t(k) = Θ (k-2). We also establish the precise value of αk when k = 4.
1 Introduction
Given a graph G, we denote by \(V(G)\) the set of its vertices and by \(E(G)\) the set of its edges; when G is clear from the context, we simply write V and E, respectively. We set \(e(G) = |E(G)|\) and \(v(G) = |V(G)|\). When two vertices x and y are adjacent, we write \(\lbrace x, y\rbrace \in E\). When the graph and its edge set areevident, we also alternatively use the notation \(x \sim y\). We denote by \(\mathbb {N}\) the set of all positive integers and by \(\mathbb {N}_{0}\) the set of all non-negative integers.
The first-order logic on graphs comprises finite sentences (for detailed definitions, see [[11], Section 2.1]) involving the following symbols:
•
variables that denote vertices, and are represented in general by lowercase letters such as \(x, y, z \ldots\);
•
the relation of vertex equality (i.e., \(x = y\)) and the relation of vertex adjacency (i.e., \(x \sim y\));
•
Boolean connectives \(\wedge , \vee , \lnot , \Rightarrow , \Leftrightarrow\);
•
existential (denoted \(\exists\)) and universal (denoted \(\forall\)) quantification, allowed only over vertices.
We refer the reader to [5, 11, 12, 13] for further reading on first-order logic. Examples of first-order sentences includewhich expresses the property of a graph that it contains an isolated vertex, andwhich expresses the property of a graph that there exists a vertex with degree precisely 1, i.e., precisely 1 neighbour. The quantifier depth, also referred to as the quantifier rank, of a first-order sentence is defined as the maximum number of nested quantifiers in the sentence; we refer the reader to [11], Definition 3.8, for the formal definition. We call a first-order sentence existential if (i) all its quantifiers are existential and (ii) negations are allowed only in front of atomic formulas.
\[\exists x [\forall y [\lnot x \sim y]],\]
\[\exists x [\exists y [[x \sim y] \wedge \forall z [x \sim z \Rightarrow z = y]]],\]
Neither of the examples above is an existential first-order sentence; an example of such a sentence would bewhich expresses the property that there exists a vertex with at least two neighbours. Given a first-order sentence \(\gamma\) and a graph G, the notation \(G \models \gamma\) indicates that \(\gamma\) is true on G.
\[\exists x [\exists y \exists z [[x \sim y] \wedge [x \sim z] \wedge [\lnot y = z]]],\]
We recall the Erdős-Rényi random graph model \(G(n, p(n))\)—starting with n vertices that are denoted \(1, \ldots , n\), the edge between vertices i and j is added with probability \(p(n)\), mutually independently over all pairs \(\lbrace i, j\rbrace\). We say that a graph property A holds asymptotically almost surely (abbreviated henceforth as a.a.s.) on \(\lbrace G(n, p(n))\rbrace\) if the probability that A holds on \(G(n, p(n))\) approaches 1 as \(n \rightarrow \infty\); similarly, we say that a sentence \(\gamma\) is a.a.s. true on \(\lbrace G(n, p(n))\rbrace\) if \(\lim _{n \rightarrow \infty } {\mathbf {P}}\left[G(n, p(n)) \models \gamma \right] = 1\).
Given a set \(\mathcal {L}\) of first-order sentences, we say that the random graph sequence \(\left\lbrace G(n, p(n))\right\rbrace _{n}\) satisfies the zero-one law for \(\mathcal {L}\) if for every sentence \(\gamma\) in \(\mathcal {L}\), the limit \(\lim _{n \rightarrow \infty } {\mathbf {P}}\left[G(n, p(n)) \models \gamma \right]\) exists and equals either 0 or 1.
In [4], the following well-known theorem was established.
For \(\alpha \in (0,1)\), the random graph sequence \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) satisfies the zero-one law for first-order logic if and only if \(\alpha\) is irrational.
In [1], it was shown that when first-order sentences of quantifier depth at most k, for a given positive integer k, are considered, \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) satisfies the zero-one law for all \(\alpha \lt (k-2)^{-1}\), and it fails to satisfy the zero-one law when \(\alpha = (k-2)^{-1}\). This is stated in the following theorem.
If \(\,0 \lt \alpha \lt \frac{1}{k-2}\), then the random graph sequence \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) satisfies the zero-one law for the set \(\mathcal {F}_{k}\) of all first-order sentences of quantifier depth of at most k; for \(\alpha = \frac{1}{k-2}\), the random graph sequence \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) does not satisfy the zero-one law.
In this article, we consider the next most natural question: What range of \(\alpha\) in \((0,1)\) will allow \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) to satisfy the zero-one law when we consider existential first-order sentences of bounded quantifier depth? For \(k \in \mathbb {N}\), let \(\mathcal {E}_{k}\) denote the set of all existential first-order sentences of quantifier depth at most k. Since \(\mathcal {E}_{k} \subset \mathcal {F}_{k}\), Theorem 1.3 implies that for all \(0 \lt \alpha \lt \frac{1}{k-2}\), \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) satisfies the zero-one law for \(\mathcal {E}_{k}\). Thus, ifthen \(\alpha _{k} \geqslant \frac{1}{k-2}\). On the other hand, let us denote by \(K_{k}\) the complete graph on k vertices and let \(A(k)\) denote the existential first-order sentence, of quantifier depth k, that states that \(K_{k}\) is present as a subgraph, i.e.,Since \(K_{k}\) is a strictly balanced graph with density \({k \choose 2}/k = (k-1)/2\) (see discussions following Lemma 2.7 for definitions of densities of graphs and strictly balanced graphs), the threshold function for \(A(k)\) is \(p(n) = n^{-\frac{2}{k-1}}\) and the probabilities \({\mathbf {P}}[G(n,n^{-\frac{2}{k-1}}) \models A(k)]\) converge to a limit in \((0,1)\). Consequently, \(\lbrace G(n,n^{-\frac{2}{k-1}})\rbrace _{n}\) does not satisfy the zero-one law for \(\mathcal {E}_{k}\), which in turn tells us that \(\alpha _{k} \lt 1\) for \(k \geqslant 4\).
\begin{equation} \alpha _{k} = \inf \left\lbrace \alpha \gt 0: \left\lbrace G\left(n, n^{-\alpha _{k}}\right)\right\rbrace _{n} \text{ does not satisfy the zero-one law for } \mathcal {E}_{k}\right\rbrace , \end{equation}
(1.1)
\begin{equation} A(k) = \exists v_{1} \exists v_{2} \ldots \exists v_{k} [v_{1} \sim v_{2}] \wedge [v_{1} \sim v_{3}] \wedge \cdots \wedge [v_{k-1} \sim v_{k}]. \end{equation}
(1.2)
Note that since \(K_{2}\) has density \(\frac{1}{2}\), the threshold function for \(A(2)\) (as defined in Equation (1.2)) is \(n^{-2}\). Moreover, the threshold probability for containing an isolated vertex is \(\frac{\ln n}{n}\) (see [14], Corollary 3.31). Using these two facts, it can be shown that \(\alpha = 2\) is the only value of \(\alpha\) for which \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) does not satisfy the zero-one law for \(\mathcal {E}_{2}\). From Theorem 1.3, we know that for all \(\alpha \in (0,1)\), the sequence \(\left\lbrace G\left(n, n^{-\alpha }\right)\right\rbrace _{n}\) satisfies the zero-one law for \(\mathcal {F}_{3}\) and hence also for \(\mathcal {E}_{3}\). We also know that \(K_{3}\) has density 1, so that the threshold function for \(A(3)\) is \(n^{-1}\). These two facts yield that \(\alpha _{3} = 1\). The above observations reveal that for both \(k = 2\) and \(k = 3\), the values of \(\alpha _{k}\) fall outside of the range \((0,1)\).
Theorem 1.4 gives the statement of the main result of this article.
For any positive integer \(k \geqslant 5\), let \(\mathcal {E}_{k}\) denote the set of all existential first-order sentences of quantifier depth at most k. Let \(\alpha _{k}\) be as defined in Equation (1.1). ThenFor \(k = 4\), we have \(\alpha _{k} = \frac{7}{13}\).
\begin{equation} \alpha _{k} = \left\lbrace k - 2 - \Theta \left(\frac{1}{k^{2}}\right)\right\rbrace ^{-1} \text{ as } k \rightarrow \infty . \end{equation}
(1.3)
One may expect that \(\alpha _{k}\) would be significantly larger than \(\frac{1}{k-2}\). But Theorem 1.4 shows that the order of magnitude, as \(k \rightarrow \infty\), of the difference \(\alpha _{k}-\frac{1}{k-2}\) is only \(O(k^{-4})\), which is surprisingly small.
Given two sets \(\mathcal {L}_{1}\) and \(\mathcal {L}_{2}\) of logical sentences with \(\mathcal {L}_{1} \subset \mathcal {L}_{2}\), if there exists a random graph sequence \(\left\lbrace G(n,p(n))\right\rbrace _{n}\) that satisfies the zero-one law for \(\mathcal {L}_{1}\) but not for \(\mathcal {L}_{2}\), then we conclude that \(\mathcal {L}_{2}\) has strictly greater expressive power than \(\mathcal {L}_{1}\) (in particular, there are properties that can be expressed in \(\mathcal {L}_{2}\) but not in \(\mathcal {L}_{1}\)). In this sense, \(\mathcal {F}_{k}\) has greater expressive power than \(\mathcal {E}_{k}\), but the observation made in the last line of the previous paragraph tells us that the difference in their expressive powers is not much.
We give here a brief discussion of existing literature that deals with questions of a similar flavour. We begin with the following classical result (proved independently in [27] and [26]): \(\lbrace G(n,\tfrac{1}{2})\rbrace _{n}\) satisfies the zero-one law for first-order logic. In [15], it was shown that there exists an existential monadic second-order (EMSO) sentence \(\psi\) over a vocabulary of four binary relations and nine first-order variables such that, if, for each \(n \in \mathbb {N}\), we denote by \(\mu _{n}(\psi)\) the fraction of finite models with domain \(\lbrace 0, 1, \ldots , n-1\rbrace\) for which \(\psi\) holds, then the asymptotic probability \(\mu (\psi) = \lim _{n \rightarrow \infty } \mu _{n}(\psi)\) does not exist, establishing the failure of zero-one laws for EMSO logic. In [16], this was improved by establishing the existence of an EMSO sentence \(\psi ^{\prime }\) on undirected graphs, over a vocabulary comprising only one binary relation, which has no asymptotic probability. In [17], denoting by \(L_{\infty , \omega }^{k}\) the logic comprising arbitrarily many conjunctions and disjunctions but at most k distinct variables, it was shown that the random graph sequence \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) satisfies the zero-one law for \(L_{\infty , \omega }^{k}\) when \(k = \lceil 1/\alpha \rceil\), whereas \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) fails to satisfy convergence laws for \(L_{\infty , \omega }^{k+1}\) if \(\alpha = 1/m\) for \(m \gt 2\). Finally, in [18], it was shown that for every \(k \in \mathbb {N}\) and \(\epsilon \gt 0\), there exists \(\alpha \in ((k-1)^{-1}, (k-1)^{-1}+\epsilon)\) such that \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) does not satisfy the zero-one law for first-order sentences with k variables, whereas it does satisfy the zero-one law for this logic for \(\alpha \in (0, (k-1)^{-1}]\).
In Section 2, we describe several definitions, tools, and results from the literature that are to be used in the proof of Theorem 1.4; in Section 3 and Section 4, respectively, we discuss our derivation of the upper and lower bounds on \(\alpha _{k}\) as \(k \rightarrow \infty\); and in Section 5, we discuss the derivation of the exact value of \(\alpha _{4}\) (part of the proof that \(\alpha _{4} = \frac{7}{13}\) is in the Appendix of the version put on Arxiv, which can be found here).
2 Tools and Results Used in Our Article
We start by describing a suitable version of the well-known Ehrenfeucht-Fraïsse games used to analyse existential first-order sentences on graphs. For \(n \in \mathbb {N}\), let \([n] = \left\lbrace 1, \ldots , n\right\rbrace\).
Given two graphs G and H and a positive integer k, the existential Ehrenfeucht game of k rounds, denoted \(\operatorname{EHR}[G, H, k]\), is played by Spoiler and Duplicator as follows. At the very beginning of the game, Spoiler chooses one of the graphs G and H. Without loss of generality, assume that he chooses G. Each of the k rounds consists of the choice of a vertex from G by Spoiler, followed by the choice of a vertex from H by Duplicator. Suppose \(x_{i}\) is the vertex selected from G and \(y_{i}\) is the vertex selected from H in round i, for \(i \in [k]\). Duplicator wins if all of the following conditions hold: for all \(i, j \in [k]\),
(i)
\(x_{i} = x_{j} \Leftrightarrow y_{i} = y_{j}\);
(ii)
\(x_{i} \sim x_{j} \Leftrightarrow y_{i} \sim y_{j}\).
We define the relation \(\sim _{k}\) as follows: given two graphs G and H, we say \(G \sim _{k} H\) if Duplicator wins \(\operatorname{EHR}[G, H, k]\). This is an equivalence relation which partitions the space of all graphs into finitely many equivalence classes (see [Section 2.2, [5]] and [[11], Lemma 3.13]). The following well-known theorem states the connection between existential Ehrenfeucht games and existential first-order sentences of bounded quantifier depth (see [10], [[11], Theorem 3.9], [12], and [13]).
Given any two graphs G and H and any \(k \in \mathbb {N}\), \(G \sim _{k} H\) if and only if, for any existential first-order sentence \(\gamma\) of quantifier depth at most k, either both \(G \models \gamma\) and \(H \models \gamma\), or both \(G \models \lnot \gamma\) and \(H \models \lnot \gamma\), i.e., G and H have the same truth value for all existential first-order sentences of quantifier depth at most k.
Henceforth, for two random variables X and Y, or for a random variable X and a probability distribution \(\mu\), we write \(X \stackrel{d}{=} Y\) to indicate that X and Y have the same distribution, and \(X \stackrel{d}{=} \mu\) to indicate that X follows the distribution \(\mu\).
Duplicator wins \(\operatorname{EHR}\left[G_{1}, G_{2}, k\right]\) a.a.s. for \(G_{1} \stackrel{d}{=} G\left(m, p(m)\right)\) and \(G_{2} \stackrel{d}{=} G\left(n, p(n)\right)\) that are independent of each other, as \(m, n \rightarrow \infty\), if and only if \(\left\lbrace G\left(n, p(n)\right)\right\rbrace _{n}\) satisfies the zero-one law for existential first-order logic of quantifier depth k.
Assume that \(\left\lbrace G\left(n, p(n)\right)\right\rbrace _{n}\) satisfies the zero-one law for \(\mathcal {E}_{k}\). Then, given any sentence \(\gamma\) in \(\mathcal {E}_{k}\), either \(\lim _{n \rightarrow \infty }{\mathbf {P}}\left[G\left(n,p(n)\right) \models \gamma \right] = 0\), in which case \(G_{1}\) and \(G_{2}\) both satisfy \(\lnot \gamma\) with probability approaching 1 as \(m, n \rightarrow \infty\), or \(\lim _{n \rightarrow \infty }{\mathbf {P}}\left[G\left(n,p(n)\right) \models \gamma \right] = 1\), in which case \(G_{1}\) and \(G_{2}\) both satisfy \(\gamma\) with probability approaching 1 as \(m, n \rightarrow \infty\). Since this is true for every such sentence \(\gamma\), and the set \(\mathcal {E}_{k}\) is finite, by Theorem 2.2, we have \(G_{1} \sim _{k} G_{2}\) a.a.s., i.e., Duplicator wins \(\operatorname{EHR}\left[G_{1}, G_{2}, k\right]\) a.a.s.
Let us now assume that Duplicator wins \(\operatorname{EHR}\left[G_{1}, G_{2}, k\right]\) a.a.s. Assume that \(\left\lbrace G\left(n,p(n)\right)\right\rbrace _{n}\) does not satisfy the zero-one law for \(\mathcal {E}_{k}\). Then there exists a sentence \(\gamma \in \mathcal {E}_{k}\) such that
(i)
either there exists an infinite sequence \(\lbrace r_{n}\rbrace _{n}\) of positive integers, with \(r_{n} \uparrow \infty\) as \(n \uparrow \infty\), such that \({\mathbf {P}}\left[G\left(r_{n},p(r_{n})\right) \models \gamma \right]\) approaches a limit \(c \in (0,1)\) as \(n \rightarrow \infty\), or
(ii)
there exist two infinite sequences \(\left\lbrace r_{n}\right\rbrace _{n}\) and \(\left\lbrace s_{n}\right\rbrace _{n}\) of positive integers, with \(r_{n} \uparrow \infty\) and \(s_{n} \uparrow \infty\) as \(n \uparrow \infty\), such that \(\lim _{n \rightarrow \infty }{\mathbf {P}}\left[G\left(r_{n},p(r_{n})\right) \models \gamma \right] = 0\) and \(\lim _{n \rightarrow \infty }{\mathbf {P}}\left[G\left(s_{n},p(s_{n})\right) \models \gamma \right] = 1\).
In the former scenario, Spoiler wins the game on independently chosen \(G_{1} \stackrel{d}{=} G(r_{n},p(r_{n}))\) and \(G_{2} \stackrel{d}{=} G(r_{n},p(r_{n}))\) with probability at least \(c(1-c) + o(1)\) as \(n \rightarrow \infty\), whereas in the latter, Spoiler wins the game on independently chosen \(G_{1} \stackrel{d}{=} G(r_{n},p(r_{n}))\) and \(G_{2} \stackrel{d}{=} G(s_{n},p(s_{n}))\) with asymptotic probability 1 as \(n \rightarrow \infty\). This contradicts our assumption, and thus concludes the proof.□
Let us now switch to some very helpful results describing distributions of small subgraphs inside the random graph. Given two graphs G and H, we say that \(H \subset G\) if \(V(H) \subset V(G)\) and \(E(H) \subset E(G)\).
Let H and G be graphs on vertex sets \(\lbrace x_{1}, \ldots , x_{k}\rbrace\) and \(\lbrace x_{1}, \ldots , x_{\ell }\rbrace\), respectively, with \(H \subset G\). A graph \(\widetilde{G}\) on \(\lbrace \widetilde{x}_{1}, \ldots , \widetilde{x}_{\ell }\rbrace\) is a strict \((G, H)\)-extension of a graph \(\widetilde{H}\) on \(\lbrace \widetilde{x}_{1}, \ldots , \widetilde{x}_{k}\rbrace\) if \(\widetilde{H} \subset \widetilde{G}\) and \(\lbrace x_{i}, x_{j}\rbrace \in E(G) \setminus E(H)\) iff \(\lbrace \widetilde{x}_{i}, \widetilde{x}_{j}\rbrace \in E(\widetilde{G}) \setminus E(\widetilde{H})\) for all \(i \in [\ell ]\) and \(j \in [\ell ] \setminus [k]\).
Setting \(v(G, H) = |V(G) \setminus V(H)|\) and \(e(G, H) = |E(G) \setminus E(H)|\), for \(\alpha \gt 0\), we defineWe define the pair \((G, H)\) to be \(\alpha\)-safe if for every \(H \subset S \subseteq G\), we have \(f_{\alpha }(S, H) \gt 0\).
\begin{equation} f_{\alpha }(G, H) = v(G, H) - \alpha e(G, H). \end{equation}
(2.1)
Let \(S = \left\lbrace \widetilde{x}_{1}, \ldots , \widetilde{x}_{k}\right\rbrace\) be a subset of the vertex set \([n]\) of \(G(n, p(n))\). For each subset W of \([n] \setminus S\) of cardinality \(\ell -k\), if we can enumerate the vertices of W as \(\widetilde{x}_{k+1}, \ldots , \widetilde{x}_{\ell }\) such that the induced subgraph on \(W \cup S\) is a strict \((G, H)\)-extension of the induced subgraph on S, we set \(\mathbf {1}_{W} = 1\); otherwise, \(\mathbf {1}_{W} = 0\). We define the random variable
\begin{equation} N_{(G, H)}\left(\widetilde{x}_{1}, \ldots , \widetilde{x}_{k}\right) = \sum _{W \subset [n] \setminus S, |W| = \ell -k} \mathbf {1}_{W}. \end{equation}
(2.2)
Suppose we are given graphs G and H and \(\alpha \gt 0\) such that the pair \((G, H)\) is \(\alpha\)-safe. Then, for any \(\epsilon \gt 0\),Moreover, we have, for all \(\widetilde{x}_{1}, \ldots , \widetilde{x}_{k} \in [n]\),
\begin{equation} \begin{split}\lim _{n \rightarrow \infty } {\mathbf {P}}\left[\left|N_{(G, H)}\left(\widetilde{x}_{1}, \ldots , \widetilde{x}_{k}\right) - {\mathbf {E}}\left[N_{(G, H)}\left(\widetilde{x}_{1}, \ldots , \widetilde{x}_{k}\right)\right]\right| \le \epsilon {\mathbf {E}}\left[N_{(G, H)}\left(\widetilde{x}_{1}, \ldots , \widetilde{x}_{k}\right)\right] \right.\\ \left.\forall \left\lbrace \widetilde{x}_{1}, \ldots , \widetilde{x}_{k}\right\rbrace \subset [n] \text{ in } G(n, n^{-\alpha })\right] = 1.\end{split} \end{equation}
(2.3)
\begin{equation} {\mathbf {E}}\left[N_{(G, H)}\left(\widetilde{x}_{1}, \ldots , \widetilde{x}_{k}\right)\right] = \Theta \left(n^{f_{\alpha }(G, H)}\right). \end{equation}
(2.4)
For \(r \in \mathbb {N}\), graph G, \(a, b \in \mathbb {N}_{0}\) with \(a+b \le r\), distinct vertices \(x_{1}, \ldots , x_{a}, y_{1}, \ldots , y_{b}\), we call a vertex v, distinct from all \(x_{i}\)’s and \(y_{j}\)’s, an \((a,b)\)-witness with respect to \(\left(\left\lbrace x_{1}, \ldots , x_{a}\right\rbrace , \left\lbrace y_{1}, \ldots , y_{b}\right\rbrace \right)\) if \(v \sim x_{i}\) for all \(i \in [a]\) and \(v \nsim y_{j}\) for all \(j \in [b]\). A graph G satisfies the full level-r extension property, sometimes referred to as Alice’s restaurant property, if for every \(a, b \in \mathbb {N}_{0}\) with \(a+b \le r\) and every distinct \(x_{1}, \ldots , x_{a}, y_{1}, \ldots , y_{b}\), there exists an \((a,b)\)-witness with respect to \(\left(\left\lbrace x_{1}, \ldots , x_{a}\right\rbrace , \left\lbrace y_{1}, \ldots , y_{b}\right\rbrace \right)\) in G.
We state here a useful lemma that shows that given \(r \in \mathbb {N}\), the random graph sequence \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) a.a.s. has the full level-r extension property for all sufficiently small \(\alpha\). See [6], proof of Theorem 4.1 and statement of Corollary 4.2 or [1], Section 3.3, case (1) of the proof of Theorem 3 for a proof of this fact.
For any positive integer r, the random graph sequence \(\left\lbrace G(n, n^{-\alpha })\right\rbrace _{n}\) a.a.s. has the full level-r extension property whenever \(\alpha \lt \frac{1}{r}\).
Thus, for \(\alpha \lt \frac{1}{r}\), Duplicator a.a.s. wins \(\operatorname{EHR}\left[G_{1}, G_{2}, r+1\right]\) for \(G_{1} \stackrel{d}{=} G\left(m, p(m)\right)\) and \(G_{2} \stackrel{d}{=} G\left(n, p(n)\right)\), independent of each other, as \(m, n \rightarrow \infty\).
To prove that, for given \(k \in \mathbb {N}\) and suitable \(\alpha _{k}\), \(\left\lbrace G\left(n, n^{-\alpha _{k}}\right)\right\rbrace _{n}\) does not satisfy the zero-one law for existential first-order sentences of quantifier depth k, we come up with a sentence of quantifier depth k that implies the existence of a small, suitable (in some sense) fixed graph as an induced subgraph in \(G\left(n, n^{-\alpha _{k}}\right)\). For this, we require some tools from random graph theory describing the asymptotic behaviour of the number of copies of a given finite graph as an induced subgraph in \(G\left(n, n^{-\alpha _{k}}\right)\) as \(n \rightarrow \infty\). This motivates the quantities defined below.
For a finite graph G with \(|V(G)| = v\) and \(|E(G)| = e\), we call \(\rho (G) = \frac{e}{v}\) the density of the graph. We define the maximal density of a finite G, denoted \({\rho _{\max }}(G)\), as the maximum of \(\rho (H)\) over all subgraphs H of G. A finite G is called balanced if \(\rho (H) \le \rho (G)\) for every subgraph H of G; it is called strictly balanced if \(\rho (H) \lt \rho (G)\) for every proper subgraph H of G; it is called unbalanced if it is not balanced. Clearly \({\rho _{\max }}(G) = \rho (G)\) for balanced G. Finally, a function \(r(n)\) is called a threshold function for some graph property P if a.a.s. \(\lbrace G(n, p(n))\rbrace\) does not satisfy P whenever \(p(n) \ll r(n)\) and a.a.s. \(\lbrace G(n, p(n))\rbrace\) satisfies P whenever \(p(n) \gg r(n)\), or vice versa.
We include here a brief discussion on Theorems 2.8, 2.9, and 2.10 before stating them formally. Questions pertaining to the appearance of small subgraphs in random graphs, especially the Erdős-Rényi random graphs, have been widely studied over the last several decades (see, e.g., [2, 7, 8, 9, 14, 19, 20, 21, 22, 23, 24, 25]). It is not hard to see that, given a finite graph H, if we consider the property \(B(H)\) that \(G(n,p(n))\) contains a copy of H that is not necessarily an induced subgraph of \(G(n,p(n))\), then \(B(H)\) is monotone (i.e., if \(G_{1} \subset G_{2}\) and \(B(H)\) holds for \(G_{1}\), then \(B(H)\) holds for \(G_{2}\) as well). For any monotone graph property, it is well known that there exists a threshold probability (see [28]).
When H is not necessarily strictly balanced, then Theorem 2.9 tells us that for \(p(n) = n^{-1/{\rho _{\max }}(H)}\), the probability that \(G(n,p(n))\) contains an induced copy of H is bounded away from 0 and 1. Sharper results are known: for example, when H is strictly balanced with v vertices, e edges, and a automorphisms, letting \(A(H)\) denote the property that a graph contains no copy of H, we have \(\lim _{n \rightarrow \infty } {\mathbf {P}}[G(n, c n^{-v/e}) \models A(H)] \rightarrow \exp \lbrace -c^{e}/a\rbrace\), for any positive c (see [2], Theorem 10.1.1). We require a further generalization of the previous result: when we consider several strictly balanced graphs that are not isomorphic to one another, the joint distribution of the numbers of induced copies of these graphs in \(G(n,p(n))\) converges in distribution to a collection of independent Poisson random variables, and this is stated in Theorem 2.10.
Let G be a graph with maximum density \(\rho\). If \(p(n) \ll n^{-1/\rho (G)}\), the probability that \(G(n,n^{-1/\rho (G)})\) contains a copy of G approaches 0 as \(n \rightarrow \infty\), whereas when \(1-\epsilon \gt p(n) \gg n^{-1/\rho (G)}\) for some constant \(\epsilon \gt 0\), the probability that \(G(n,n^{-1/\rho (G)})\) contains an induced copy of G approaches 1 as \(n \rightarrow \infty\).
For a given finite graph G, we define \(\Phi _{G}(n, p(n)) = \min \lbrace {\mathbf {E}}[N^{n}_{H}]: H \subseteq G, e(H) \gt 0\rbrace\), where \(N^{n}_{H}\) denotes the number of induced copies of H in \(G(n, p(n))\).
For a given finite graph G with at least one edge, for every edge probability sequence \(\lbrace p(n)\rbrace _{n \in \mathbb {N}}\), we have
\begin{equation} \exp \left\lbrace -\frac{1}{1-p(n)} \Phi _{G}(n, p(n))\right\rbrace \le {\mathbf {P}}\left[G(n, p(n)) \text{ contains induced } G\right] \le \exp \left\lbrace -\Theta \left(\Phi _{G}(n, p(n))\right)\right\rbrace . \end{equation}
(2.5)
From Theorem 2.9 and [14], Section 3.3, we conclude that
\begin{equation} \begin{split} 0 \lt \liminf _{n \rightarrow \infty } {\mathbf {P}}\left[G\left(n, n^{-1/{\rho _{\max }}(G)}\right) \text{ contains induced } G\right] \\ \le \limsup _{n \rightarrow \infty } {\mathbf {P}}\left[G\left(n, n^{-1/{\rho _{\max }}(G)}\right) \text{ contains induced } G\right] \lt 1.\end{split} \end{equation}
(2.6)
Let \(H_{1}, \ldots , H_{m}\) be given strictly balanced, non-isomorphic finite graphs such that \(\rho (H_{1}) = \cdots = \rho (H_{m}) = \rho _{0}\). Let \(a_{i}\) be the number of automorphisms of \(H_{i}\) for \(i \in [m]\). Set \(\alpha = \tfrac{1}{\rho _{0}}\), and for some \(c \gt 0\), consider \(\lbrace G(n, c n^{-\alpha })\rbrace _{n}\). If \(N_{H_{i}}^{n}\) denotes the number of induced copies of \(H_{i}\) in \(G(n, c n^{-\alpha })\) for \(n \in \mathbb {N}\) and \(i \in [m]\), then the random vector \((N^{n}_{H_{1}}, \ldots , N^{n}_{H_{m}})\) converges in distribution to the random vector \((\xi _{1}, \ldots , \xi _{m})\) where \(\xi _{1}, \ldots , \xi _{m}\) are independent with \(\xi _{i} \stackrel{d}{=} \operatorname{Poisson}(a_{i}^{-1} c^{e_{i}})\), where \(e_{i}\) is the number of edges in \(H_{i}\).
3 Upper Bound
This section is devoted to finding an upper bound on \(\alpha _{k}\) as defined in Equation (1.1), for \(k \geqslant 5\), which involves coming up with
(i)
a sentence \(\varphi _{k} \in \mathcal {E}_{k}\), and
(ii)
a finite set \(\Sigma _{k}\) of finite graphs such that \(\varphi _{k}\) is true on a graph G if and only if G contains \(\Gamma\) as an induced subgraph for some \(\Gamma \in \Sigma _{k}\).
The sentence \(\varphi _{k}\) states that there exists a clique of size \(k-3\), comprising vertices \(a_{1}, \ldots , a_{k-3}\), henceforth called the roots, such that
(i)
for distinct \(i, j \in [k-3]\), there exists a vertex \(v_{i,j}\) that is adjacent to \(a_{\ell }\) for all \(\ell \in [k-3] \setminus \lbrace i, j\rbrace\) but not to \(a_{i}\) and \(a_{j}\), and we call these \(v_{i,j}\) ground vertices;
(ii)
for each \(v_{i,j}\) and \(\ell \in [k-3]\), there exists a vertex \(v_{i, j, \ell }\) that is adjacent to \(v_{i,j}\) and \(a_{t}\) for all \(t \in [k-3] \setminus \lbrace \ell \rbrace\), but not to \(a_{\ell }\), and we call these \(v_{i,j,\ell }\) first-level to \(v_{i,j}\);
(iii)
for each \(v_{i,j}\), each \(v_{i,j,\ell }\), and \(m \in [k-3]\), there exists a vertex \(v_{i,j,\ell ,m}\) that is adjacent to \(v_{i,j}\), \(v_{i,j,\ell }\), and \(a_{t}\) for all \(t \in [k-3] \setminus \lbrace m\rbrace\), but not to \(a_{m}\), and we call these \(v_{i,j,\ell ,m}\) second-level to \(v_{i,j}\) and \(v_{i,j,\ell }\);
(iv)
for each \(v_{i,j}\) and each \(v_{i,j,\ell }\), there exists a vertex \(w_{i,j,\ell }\) that is adjacent to \(v_{i,j}\), \(v_{i,j,\ell }\), and \(a_{t}\) for all \(t \in [k-3]\), and we call these \(w_{i,j,\ell }\) universal to \(v_{i,j}\) and \(v_{i,j,\ell }\).
The definition makes it immediate that \(\varphi _{k}\) is existential first order with quantifier depth precisely k.
Henceforth, a vertex \(v_{i,j,\ell }\) that is first-level to ground vertex \(v_{i,j}\) is simply referred to as a first-level vertex, a vertex \(v_{i,j,\ell ,m}\) that is second-level to ground vertex \(v_{i,j}\) and first-level vertex \(v_{i,j,\ell }\) is referred to as a second-level vertex, and a vertex \(w_{i,j,\ell }\) that is universal to \(v_{i,j}\) and \(v_{i,j,\ell }\) is referred to as a universal vertex (the notations reveal which ground and/or first-level vertices they correspond to).
Since \(\varphi _{k}\) is an existential first-order sentence that requires the presence of the above-mentioned finite list of vertices with edges and non-edges as described in (i)–(iv), any graph G that satisfies \(\varphi _{k}\) has to have such a subset of vertices and an induced subgraph on that subset that has the edges and non-edges prescribed in (i)–(iv). The collection \(\Sigma _{k}\) of all possible such induced subgraphs will clearly be finite. Every graph in \(\Sigma _{k}\) will comprise only the following vertices: (i) the \(k-3\) roots, (ii) the \({k-3 \choose 2}\) ground vertices, (iii) for each ground vertex, the vertices first-level to it, (iv) for each ground vertex and each corresponding first-level vertex, the vertices second-level to them, and (v) for each ground vertex and each corresponding first-level vertex, the vertex universal to them.
From the very definition of \(\Sigma _{k}\), it follows that \(G \models \varphi _{k}\) if and only if G contains an induced subgraph isomorphic to some \(\Gamma\) in \(\Sigma _{k}\).
We discuss briefly the possibility of overlaps among the vertices listed in (i)–(iv). Since each \(v_{i,j}\) is non-adjacent to two vertices, \(a_{i}\) and \(a_{j}\), out of \(a_{1}, \ldots , a_{k-3}\), whereas each \(v_{i^{\prime },j^{\prime },\ell }\) is non-adjacent to only one vertex \(a_{\ell }\) out of \(a_{1}, \ldots , a_{k-3}\), no \(v_{i^{\prime },j^{\prime },\ell }\) can coincide with any \(v_{i,j}\). For this same reason, no \(v_{i^{\prime },j^{\prime },\ell ,m}\) can coincide with any \(v_{i,j}\). However, for some \(\lbrace i,j,\ell \rbrace \ne \lbrace i^{\prime },j^{\prime },\ell ^{\prime }\rbrace\), it is possible to have \(v_{i,j,\ell } = v_{i^{\prime },j^{\prime },\ell ^{\prime },m}\) provided \(m = \ell\). Each \(w_{i,j,\ell }\) is adjacent to every one of the vertices \(a_{1}, \ldots , a_{k-3}\), which means that it can coincide with no \(v_{i^{\prime },j^{\prime }}\), no \(v_{i^{\prime },j^{\prime },\ell ^{\prime }}\), and no \(v_{i^{\prime },j^{\prime },\ell ^{\prime },m}\). Two first-level vertices may coincide with each other; likewise, two second-level vertices may coincide with one another, and two universal vertices may coincide with one another.
If \(\alpha _{0}^{-1} := \min \left\lbrace {\rho _{\max }}(\Gamma): \Gamma \in \Sigma _{k}\right\rbrace\), then \(\alpha _{0}^{-1}\) is at least \(k - 2 - O(\frac{1}{k^{2}})\).
The proof comprises a few lemmas. For \(\Gamma \in \Sigma _{k}\), we call a first-level vertex \(v_{i,j,\ell }\) unique if it coincides with no other first-level vertex, and a second-level vertex \(v_{i,j,\ell ,m}\) unique if it coincides with no other vertex in \(\Gamma\) (i.e., with neither any first-level vertex nor any other second-level vertex). Let \(\Gamma\) contain a unique first-level vertices and b unique second-level vertices \(v_{i,j,\ell ,m}\) such that the corresponding first-level vertex \(v_{i,j,\ell }\) is also unique. We consider the subgraph H of \(\Gamma\) induced on (i) all roots, (ii) all ground vertices, (iii) all unique first-level vertices, (iv) all unique second-level vertices whose corresponding first-level vertices are also unique, (v) all universal vertices \(w_{i,j,\ell }\) whose corresponding first-level vertices \(v_{i,j,\ell }\) are unique, and let the number of distinct such vertices be \(\mu\).
In H, there are (i) \({k-3 \choose 2}\) edges with both end-points roots, (ii) \((k-5){k-3 \choose 2}\) edges with one end-point a root and another a ground vertex, (iii) \(a(k-3)\) edges with one end-point a unique first-level vertex and the other a root or a ground vertex, (iv) \(b(k-2)\) edges with one end-point a unique second-level vertex and the other a root or a ground vertex or a unique first-level vertex.
For each universal \(w_{i,j,\ell }\) with \(v_{i,j,\ell }\) unique, \(w_{i,j,\ell }\) is adjacent to all roots and the corresponding ground vertex \(v_{i,j}\), thus contributing \(\mu (k-2)\) many edges, whereas each unique first-level vertex will have an edge with one of these universal vertices, contributing additional a edges. Thus,If \(b \ge \frac{k^{4}}{4}\), then \(\rho (H)\) is at least \(k-2-O(k^{-2})\).
\begin{align} \rho (H) &\ge \frac{{k-3 \choose 2} + (k-5){k-3 \choose 2} + a(k-3) + b(k-2) + \mu (k-2) + a}{k-3 + {k-3 \choose 2} + a + b + \mu } \nonumber \nonumber\\ &= \frac{\frac{(k-3)(k-4)^{2}}{2} + (a+b+\mu)(k-2)}{\frac{(k-3)(k-2)}{2} + a+b+\mu }. \end{align}
(3.1)
For any fixed \(\epsilon \in (0, \frac{1}{2})\), there exists some \(k_{0} \in \mathbb {N}\) such that for all \(k \geqslant k_{0}\), if \(a \lt (\frac{1}{2} - \epsilon)k^{3}\), then \({\rho _{\max }}(\Gamma) \gt k-2\).
Let \(\lambda\) be the total number of distinct first-level vertices in \(\Gamma\). Recall that \(\Gamma\) contains a unique first-level vertices. If a first-level vertex is not unique, it coincides with at least one other first-level vertex. Thus, the remaining \((k-3) {k-3 \choose 2} - a\) non-unique first-level vertices contribute at most \(\tfrac{1}{2}\lbrace (k-3){k-3 \choose 2} - a\rbrace\) distinct vertices. Therefore,Consider the induced subgraph H of \(\Gamma\) comprising (i) all roots, (ii) all ground vertices, (iii) all first-level vertices, (iv) all universal vertices (let there be \(\mu\) distinct such vertices).
\begin{equation} \lambda \le a + \frac{1}{2}\left\lbrace (k-3) {k-3 \choose 2} - a\right\rbrace \lt \left(\frac{1}{2} - \frac{\epsilon }{2}\right) k^{3} (1+o(1)). \end{equation}
(3.2)
There are \({k-3 \choose 2}\) edges in H with both end-points roots and \((k-5){k-3 \choose 2}\) edges with one end-point a root and the other a ground vertex. Each of the distinct first-level vertices is adjacent to \(k-4\) roots, hence there are \(\lambda (k-4)\) edges in H with one end-point a root and another a first-level vertex. When a first-level vertex v is not unique, there exists some \(\ell\) and some subset S of \(\lbrace \lbrace i, j\rbrace : i \ne j, i, j \in [k-3]\rbrace\) with \(|S| \ge 2\) such that \(v = v_{i,j,\ell }\) for all \(\lbrace i, j\rbrace \in S\). The edges in H whose one end-point is v and the other a ground vertex, are given by \(\lbrace v_{i,j}, v\rbrace = \lbrace v_{i,j}, v_{i,j,\ell }\rbrace\) for all \(\lbrace i, j\rbrace \in S\), and they are distinct. Thus, the number of edges in H whose one end-point is a first-level vertex and the other a ground vertex is at least \((k-3) {k-3 \choose 2}\). Each distinct universal vertex is adjacent to \(k-3\) roots, and to at least one ground vertex (e.g., if universal vertices \(w_{i,j,\ell }\) and \(w_{i,j,\ell ^{\prime }}\), for distinct \(\ell\) and \(\ell ^{\prime }\), coincide, then edges \(\lbrace w_{i,j,\ell }, v_{i,j}\rbrace\) and \(\lbrace w_{i,j,\ell ^{\prime }}, v_{i,j}\rbrace\) will coincide too, and will be counted once). Thus, the number of edges in H whose one end-point is a universal vertex and another a root or a ground vertex is at least \(\mu (k-2)\). Finally, each first-level vertex is adjacent to at least one universal vertex, even when the first-level vertex is non-unique and the universal vertex coincides with another universal vertex (e.g., the first-level vertices \(v_{i_{1},j_{1},\ell }\) and \(v_{i_{2},j_{2},\ell }\) may coincide, and the universal vertices \(w_{i_{1},j_{1},\ell }\) and \(w_{i_{2},j_{2},\ell }\) may coincide, so that edges \(\lbrace v_{i_{1},j_{1},\ell }, w_{i_{1},j_{1},\ell }\rbrace\) and \(\lbrace v_{i_{2},j_{2},\ell }, w_{i_{2},j_{2},\ell }\rbrace\) coincide and are counted once). Thus, the number of edges in H whose one end-point is a universal vertex and the other a first-level vertex is at least \(\lambda\). Thus,for all k large enough. Consequently, we can find a \(k_{0} \in \mathbb {N}\) such that for all \(k \geqslant k_{0}\), we have \({\rho _{\max }}(\Gamma) \ge \rho (H) \gt k-2\) as long as the hypothesis of Lemma 3.2 holds.□
\begin{align} \rho (H) &\ge \frac{{k-3 \choose 2} + (k-5){k-3 \choose 2} + \lambda (k-4) + {k-3 \choose 2}(k-3) + \mu (k-2) + \lambda }{(k-3) + {k-3 \choose 2} + \lambda + \mu } \nonumber \nonumber\\ &= k-2 + \frac{\frac{1}{2}(k-3)^{2}(k-8) - \lambda }{\frac{1}{2}(k-3)(k-2) + \lambda + \mu } \nonumber \nonumber\\ & \ge k-2 + \frac{\frac{1}{2}(k-3)^{2}(k-8) - \left(\frac{1}{2} - \frac{\epsilon }{2}\right)k^{3}}{\frac{1}{2}(k-3)(k-2) + \lambda + \mu } \gt k-2 \end{align}
(3.3)
By our definition, a unique first-level vertex is forbidden from coinciding with another first-level vertex, but may coincide with a second-level vertex. If \(v_{i,j,\ell }\) is a unique first-level vertex that coincides with the second-level vertex \(v_{i_{1},j_{1},\ell _{1},\ell }\) for some \(\lbrace i_{1},j_{1}\rbrace \ne \lbrace i,j\rbrace\), we call the edge \(\lbrace v_{i,j,\ell }, v_{i_{1},j_{1}}\rbrace\) a skewed edge. A first-level vertex can coincide with either another first-level vertex or a second-level vertex. Suppose two first-level vertices \(v_{i_{1},j_{1},\ell _{1}}\) and \(v_{i_{2},j_{2},\ell _{2}}\) are adjacent. If there exists no \(m \in [k-3]\) such that \(v_{i_{2},j_{2},\ell _{2}} = v_{i_{1},j_{1},\ell _{1},m}\) nor \(m^{\prime } \in [k-3]\) such that \(v_{i_{1},j_{1},\ell _{1}} = v_{i_{2},j_{2},\ell _{2},m^{\prime }}\), then the presence of the edge \(\lbrace v_{i_{1},j_{1},\ell _{1}}, v_{i_{2},j_{2},\ell _{2}}\rbrace\) only serves to unnecessarily increase the density. To elucidate this observation further, notice that if there did exist \(m \in [k-3]\) such that \(v_{i_{2},j_{2},\ell _{2}} = v_{i_{1},j_{1},\ell _{1},m}\), then by definition, \(v_{i_{1},j_{1},\ell _{1},m}\) and consequently \(v_{i_{2},j_{2},\ell _{2}}\) would have been adjacent to \(v_{i_{1},j_{1},\ell _{1}}\). Likewise, if there did exist \(m^{\prime } \in [k-3]\) such that \(v_{i_{1},j_{1},\ell _{1}} = v_{i_{2},j_{2},\ell _{2},m^{\prime }}\), then by definition, \(v_{i_{2},j_{2},\ell _{2},m^{\prime }}\) and consequently \(v_{i_{1},j_{1},\ell _{1}}\) would have been adjacent to \(v_{i_{2},j_{2},\ell _{2}}\). If neither such an m nor such an \(m^{\prime }\) exists, then there is no compulsion for \(v_{i_{1},j_{1},\ell _{1}}\) and \(v_{i_{2},j_{2},\ell _{2}}\) to be adjacent. If despite that, we consider the presence of an edge between them, then we are unnecessarily adding an edge and increasing the density of the graph \(\Gamma\). Since our aim is to obtain a lower bound on \({\rho _{\max }}(\Gamma)\) for \(\Gamma \in \Sigma _{k}\), any unnecessary increment in density does not help our cause. Thus, we may assume that two first-level vertices are adjacent only if at least one of them coincides with a second-level vertex. An edge that has first-level vertices at both end-points is called a first-level edge.
Suppose the number of skewed edges in \(\Gamma\) is g and the number of first-level edges is h. Suppose \(g + h \ge 2k^{2}\), then \({\rho _{\max }}(\Gamma) \gt k-2\) for all k sufficiently large.
Consider the induced subgraph H of \(\Gamma\) comprising (i) all roots, (ii) all ground vertices, (iii) all first-level vertices (let the number of distinct first-level vertices be \(\lambda\), as in Lemma 3.2), (iv) all universal vertices (let the number of distinct universal vertices be \(\mu\)).
As in Lemma 3.2, we argue that□
\begin{align} \rho (H) & \ge \frac{{k-3 \choose 2} + (k-5){k-3 \choose 2} + \lambda (k-4) + (k-3){k-3 \choose 2} + g + \ell + \mu (k-2) + \lambda }{(k-3) + {k-3 \choose 2} + \lambda + \mu } \nonumber \nonumber\\ &= k-2 + \frac{\frac{1}{2}(k-3)^{2}(k-8) + (g+\ell) - \lambda }{\frac{1}{2}(k-3)(k-2) + \lambda + \mu } \nonumber \nonumber\\ &\ge k-2 + \frac{\frac{1}{2}(k-3)^{2}(k-8) + 2k^{2} - (k-3){k-3 \choose 2}}{\frac{1}{2}(k-3)(k-2) + \lambda + \mu } \nonumber \nonumber\\ &= k-2 + \frac{2k^{2} - 2(k-3)^{2}}{\frac{1}{2}(k-3)(k-2) + \lambda + \mu } \gt k-2. \end{align}
(3.4)
Lemmas 3.2 and 3.3 show that we only need to consider the scenario where, for the fixed \(\epsilon\) mentioned in Lemma 3.2, we have \(a \gt (\tfrac{1}{2} - \epsilon)k^{3}\), and \(g+h \lt 2k^{2}\). As \(k \rightarrow \infty\), this implies that there are at least \((\tfrac{1}{2} - \epsilon)k^{3}\) unique first-level vertices that are non-adjacent to all other first-level vertices and all ground vertices other than the corresponding ground vertex, i.e., such a unique first-level vertex \(v_{i,j,\ell }\) is adjacent to no ground vertex \(v_{i^{\prime },j^{\prime }}\) with \(\lbrace i^{\prime }, j^{\prime }\rbrace \ne \lbrace i, j\rbrace\). We call such a unique first-level vertex pure. No second-level vertex can coincide with a pure first-level vertex.
For each fixed \(\epsilon \in (0, 1/8)\), there exists a \(k_{1} \in \mathbb {N}\) such that, for all \(k \geqslant k_{1}\), if \(\Gamma\) contains \(\widetilde{a} \ge (\tfrac{1}{2} - \epsilon)k^{3}\) pure first-level vertices and \(b \lt \tfrac{k^{4}}{4}\), then \({\rho _{\max }}(\Gamma) \gt k-2\).
Let \(\widetilde{\lambda }\) be the number of second-level vertices in \(\Gamma\) with the corresponding first-level vertices pure. Recall that the number of unique second-level vertices in \(\Gamma\) with the corresponding first-level vertices also unique is b, and the pure first-level vertices form a subset of the unique first-level vertices. If \(v_{i,j,\ell ,m}\) is a non-unique second-level vertex with the corresponding first-level vertex \(v_{i,j,\ell }\) pure, then \(v_{i,j,\ell ,m}\) coincides with another second-level vertex.
There are at most b unique second-level vertices \(v_{i,j,\ell ,m}\) with \(v_{i,j,\ell }\) pure, and \((k-3)^{2} {k-3 \choose 2} - b\), not necessarily distinct, second-level vertices that are either not unique, or unique but the corresponding first-level vertices are not unique. Thus, there are at most \((k-3)^{2} {k-3 \choose 2} - b\) second-level vertices that coincide with some other second-level vertices, and hence at most \(\frac{1}{2}\lbrace (k-3)^{2} {k-3 \choose 2} - b\rbrace\) distinct second-level vertices each of which is non-unique and the corresponding first-level vertex is pure. This gives ussince \(b \lt \frac{k^{4}}{4}\). Suppose H is the subgraph of \(\Gamma\) comprising (i) all roots, (ii) all ground vertices, (iii) all pure first-level vertices, (iv) all second-level vertices whose corresponding first-level vertices are pure, and (v) all universal vertices whose corresponding first-level vertices are pure, and let the number of distinct such vertices be \(\mu\).
\begin{align} \widetilde{\lambda } \le b + \frac{1}{2}\left\lbrace (k-3)^{2} {k-3 \choose 2} - b\right\rbrace \lt \frac{3k^{4}}{8}, \end{align}
(3.5)
There are \({k-3 \choose 2}\) edges in H with both end-points roots and \((k-5){k-3 \choose 2}\) edges with one end-point a ground vertex and another a root. Each pure first-level vertex is adjacent to \(k-4\) roots and 1 ground vertex—thus, there are \(\widetilde{a}(k-3)\) edges in H with one end-point a pure first-level vertex and another a root or a ground vertex. The \(k-3\) second-level vertices corresponding to a single pure first-level vertex are distinct from each other. Hence, there are \(\widetilde{a}(k-3)\) edges with one end-point a second-level vertex and the other a pure first-level vertex. Each second-level vertex in H is adjacent to \(k-4\) roots and at least one ground vertex. Thus, there are at least \(\widetilde{\lambda }(k-3)\) edges in H with one end-point a second-level vertex and the other a root or a ground vertex. Each universal vertex is adjacent to \(k-3\) roots and at least one ground vertex, hence there are at least \(\mu (k-2)\) edges in H with one end-point a universal vertex and the other a root or a ground vertex. Each pure first-level vertex is adjacent to a single universal vertex, hence there are \(\widetilde{a}\) edges in H with one end-point a universal vertex and the other a pure first-level vertex. Thus,hence, as long as \(\epsilon \in (0, 1/8)\), we have \({\rho _{\max }}(\Gamma) \ge \rho (H) \gt k-2\) for all k large enough.□
\begin{align} \rho (H) & \ge \frac{{k-3 \choose 2} + (k-5){k-3 \choose 2} + \widetilde{a}(k-3) + \widetilde{a}(k-3) + \widetilde{\lambda }(k-3) + \mu (k-2) + \widetilde{a}}{(k-3) + {k-3 \choose 2} + \widetilde{a} + \widetilde{\lambda } + \mu } \nonumber \nonumber\\ &= k-2 + \frac{\widetilde{a}(k-3) - \widetilde{\lambda } - 2(k-3)^{2}}{(k-3) + {k-3 \choose 2} + \widetilde{a} + \widetilde{\lambda } + \mu } \nonumber \nonumber\\ &\gt k-2 + \frac{\left(\frac{1}{2} - \epsilon \right)k^{3}(k-3) - \frac{3k^{4}}{8} - 2(k-3)^{2}}{(k-3) + {k-3 \choose 2} + \widetilde{a} + \widetilde{\lambda } + \mu }; \end{align}
(3.6)
So far, we see that
(i)
(ii)
in Lemma 3.2, we fix any \(\epsilon \in (0,\tfrac{1}{8}) \subset (0,\tfrac{1}{2})\) and establish the claim of Theorem 3.1 when the number a of unique first-level vertices satisfies \(a \lt (\tfrac{1}{2} - \epsilon)k^{3}\). For the paragraph that follows, we simply take \(\epsilon = \tfrac{1}{16}\) for the ease of exposition.
These show that we need only consider the case where \(b \lt \tfrac{k^{4}}{4}\) and \(a \geqslant (\tfrac{1}{2} - \tfrac{1}{16})k^{3}\). This is taken care of by Lemma 3.3 and Lemma 3.4 together (notice that the number \(\widetilde{a}\) of pure first-level vertices is less than or equal to the number a of unique first-level vertices since pure first-level vertices form a subset of unique first-level vertices—this shows that when \(\widetilde{a} \geqslant (\tfrac{1}{2} - \tfrac{1}{16})k^{3}\), we have \(a \geqslant (\tfrac{1}{2} - \tfrac{1}{16})k^{3}\) as well). Thus, combining all these, we get a complete proof of Theorem 3.1.
Let \(\Sigma _{k}^{0} = \left\lbrace S_{1}, \ldots , S_{m}\right\rbrace\), for some \(m \in \mathbb {N}\) denote the subset of \(\Sigma _{k}\) comprising only those graphs whose maximal density equals \(\alpha _{0}^{-1}\) as defined in Theorem 3.1. Let \(H_{i}\) be a strictly balanced subgraph of \(S_{i}\) with \(\rho (H_{i}) = {\rho _{\max }}(S_{i}) = \alpha _{0}^{-1}\) for all \(i \in [m]\). As \(H_{1}, \ldots , H_{m}\) are non-isomorphic and strictly balanced, from Theorem 2.10 we havewhere \(\lambda _{i} = a_{i}^{-1}\), with \(a_{i}\) the number of automorphisms of \(H_{i}\), for \(i \in [m]\). For any \(S \in \Sigma _{k} \setminus \Sigma _{k}^{0}\), if H is a strictly balanced subgraph of S with \(\rho (H) = {\rho _{\max }}(S) \gt \alpha _{0}^{-1}\), then by Theorem 2.8, a.a.s. \(G\left(n, n^{-\alpha _{0}}\right)\) contains no induced copy of H and hence no induced copy of S. Thus,Since \(H_{i}\) is a subgraph of \(S_{i}\), the event \(\left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } S_{i}\right\rbrace\) implies that the event \(\left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } H_{i}\right\rbrace\) holds. Hence, we can writeso that, combining Equations (3.7) and (3.9), we conclude thatFrom Theorem 2.9, noting that \({\rho _{\max }}(S_{1}) = \alpha _{0}^{-1}\), we getas desired.
\begin{align} & {\mathbf {P}}\left[\bigcup _{i=1}^{m} \left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } H_{i}\right\rbrace \right] = 1 - {\mathbf {P}}\left[N_{H_{i}}^{n} = 0 \forall i \in [m]\right] \rightarrow 1 - \prod _{i=1}^{m} e^{-\lambda _{i}}, \end{align}
(3.7)
\begin{align} & {\mathbf {P}}\left[G\left(n, n^{-\alpha _{0}}\right) \models \varphi _{k}\right] = {\mathbf {P}}\left[\bigcup _{\Gamma \in \Sigma _{k}} \left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } \Gamma \right\rbrace \right] \nonumber \nonumber\\ \le & {\mathbf {P}}\left[\bigcup _{\Gamma \in \Sigma _{k}^{0}} \left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } \Gamma \right\rbrace \right] + \sum _{\Gamma \in \Sigma _{k} \setminus \Sigma _{k}^{0}} {\mathbf {P}}\left[G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } \Gamma \right] \nonumber \nonumber\\ =& {\mathbf {P}}\left[\bigcup _{i=1}^{m} \left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } S_{i}\right\rbrace \right] + o(1). \end{align}
(3.8)
\begin{align} {\mathbf {P}}\left[\bigcup _{i=1}^{m} \left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } S_{i}\right\rbrace \right] \le {\mathbf {P}}\left[\bigcup _{i=1}^{m} \left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } H_{i}\right\rbrace \right], \end{align}
(3.9)
\begin{align} \limsup _{n \rightarrow \infty } {\mathbf {P}}\left[\bigcup _{i=1}^{m} \left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } S_{i}\right\rbrace \right] \le 1 - \prod _{i=1}^{m} e^{-\lambda _{i}}. \end{align}
(3.10)
\begin{equation} \begin{split}\liminf _{n \rightarrow \infty } {\mathbf {P}}\left[\bigcup _{i=1}^{m} \left\lbrace G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } S_{i}\right\rbrace \right] \\ \ge \liminf _{n \rightarrow \infty } {\mathbf {P}}\left[G\left(n, n^{-\alpha _{0}}\right) \text{ contains induced } S_{1}\right] \gt 0,\end{split} \end{equation}
(3.11)
4 Lower Bound
To get a lower bound on \(\alpha _{k}\) as defined in Theorem 1.4, we consider \(\operatorname{EHR}\left[G_{1}, G_{2}, k\right]\) where \(G_{1} \stackrel{d}{=} G(m, m^{-\alpha })\) and \(G_{2} \stackrel{d}{=} G(n, n^{-\alpha })\) are generated independently, for someAssume without loss of generality that Spoiler plays on \(G_{1}\), the vertices chosen from \(G_{1}\) are denoted \(x_{i}\) and those from \(G_{2}\) denoted \(y_{i}\), \(i \in [k]\). From Lemma 2.7, when \(\alpha \lt (k-3)^{-1}\), the full level-\((k-3)\) extension property holds a.a.s. in \(G(n, n^{-\alpha })\), which Duplicator uses for the first \(k-4\) rounds to respond to Spoiler.
\begin{equation} \alpha = \left(k - 2 - t(k)\right)^{-1}, \text{ with a suitable } t(k) = \Theta (k^{-2}). \end{equation}
(4.1)
Note that Duplicator can, as such, use the level-\((k-3)\) extension property to respond to Spoiler for the first \(k-2\) rounds of the game, but this could lead to her losing the game in round \(k-1\) or round k, and we mention here an example of such a possibility. Suppose Spoiler chooses from \(G_{1}\) vertices \(x_{1}, \ldots , x_{k-2}\) in the first \(k-2\) rounds, and Duplicator, without thinking ahead, uses simply the full level-\((k-3)\) extension property to choose \(y_{1}, \ldots , y_{k-2}\) from \(G_{2}\) in the corresponding rounds, such that \(x_{i} \sim x_{j}\) iff \(y_{i} \sim y_{j}\). Since the full level-\((k-2)\) extension property is not guaranteed to hold, Spoiler may be able to find and select a vertex \(x_{k-1}\) from \(G_{1}\) that is adjacent to each of \(x_{1}, \ldots , x_{k-2}\), but there may exist no vertex \(y_{k-1}\) in \(G_{2}\) such that \(y_{k-1} \sim y_{i}\) for all \(i \in [k-2]\).
Once Spoiler chooses \(x_{k-3}\) in round \(k-3\), we obtain an ordered tuple \(\vec{e} \in \lbrace 0,1\rbrace ^{k-4}\) such that \(x_{k-3} \sim x_{i}\) iff \(e_{i} = 1\) for \(i \in [k-4]\). In what follows, we make use of this particular \(\vec{e}\).
We now outline the main steps of the argument. The plan is to consider any graph H on \(k-4\) vertices, then come up with another finite graph G, taking into account the vector \(\vec{e}\) mentioned above, such that \(H \subset G\), and such that the pair \((G, H)\) is \(\alpha\)-safe for \(\alpha\) that satisfies Equation (4.1). We then use Theorem 2.5 to conclude that \(G_{2} \stackrel{d}{=} G\left(n, n^{-\alpha }\right)\) contains an induced subgraph that is a strict \((G,H)\)-extension of the subgraph induced by \(G_{2}\) on \(\lbrace y_{1}, \ldots , y_{k-4}\rbrace\). Duplicator then selects a suitable vertex of this extension inside \(G_{2}\) as her response to Spoiler in the \((k-3)\)-rd round. We then discuss her responses in the subsequent rounds, i.e., \(k-2\), \(k-1\), and k, ensuring that she wins the game.
Suppose H is a graph on any \(k-4\) vertices \(a_{1}, \ldots , a_{k-4}\), and let a vertex \(a_{k-3}\) be adjacent to \(a_{i}\) iff \(e_{i} = 1\) for all \(i \in [k-4]\), for the \(\vec{e}\) mentioned above. Consider the graph G, with \(H \subset G\), where \(G \setminus H\) comprises the following vertices, edges and non-edges:
(A1)
\(a_{k-3}\) itself, with \(a_{k-3} \sim a_{i}\) iff \(e_{i} = 1\) for all \(i \in [k-4]\);
(A2)
\(a_{k-2}\), adjacent to all of \(a_{1}, \ldots , a_{k-3}\);
(A3)
\(a_{k-1}\), adjacent to all of \(a_{1}, \ldots , a_{k-2}\);
(A4)
\(a_{k-1,j}\), adjacent to \(a_{\ell }\) for all \(\ell \in [k-2] \setminus \lbrace j\rbrace\) and non-adjacent to \(a_{j}\) for all \(j \in [k-2]\);
(A5)
\(a_{k}\), adjacent to all of \(a_{1}, \ldots , a_{k-2}, a_{k-1}\), and non-adjacent to \(a_{k-1,j}\) for all \(j \in [k-2]\);
(A6)
\(a_{k}^{i}\), adjacent to \(a_{\ell }\) for all \(\ell \in [k-1] \setminus \lbrace i\rbrace\) and non-adjacent to \(a_{i}\), for all \(i \in [k-2]\);
(A7)
\(a_{k}^{k-1,j}\), adjacent to \(a_{1}, \ldots , a_{k-2}, a_{k-1,j}\), and non-adjacent to \(a_{k-1}\), for all \(j \in [k-2]\);
(A8)
\(a_{k,i}^{k-1,j}\), adjacent to \(a_{\ell }\) for \(\ell \in [k-2] \setminus \lbrace i\rbrace\) and to \(a_{k-1,j}\), and non-adjacent to \(a_{i}\) for \(i, j \in [k-2]\).
For any \(\vec{e} \in \lbrace 0,1\rbrace ^{k-4}\), the pair \((G, H)\) is \(\alpha\)-safe for some \(\alpha\) that satisfies Equation (4.1).
Note that, in the enumeration of the vertices above, there are four clear layers: the \((k-3)\)-rd layer comprises \(a_{k-3}\), the \((k-2)\)-nd layer comprises \(a_{k-2}\), the \((k-1)\)-st layer comprises \(a_{k-1}\) and \(a_{k-1,j}\), \(j \in [k-2]\), and the k-th layer the rest. In the proof, we assume that the vertices of any graph S with \(H \subset S \subseteq G\) are ordered such that those in a layer of smaller index appear earlier. For any vertex \(u \in S\), we say that u brings e edges if there are exactly e edges between u and the vertices in S that appear before u in the above order.
For S with \(H \subset S \subseteq G\), suppose
•
\(\mathcal {A}_{0} = S \cap \left\lbrace a_{k}, a_{k}^{k-1,j}, j \in [k-2]\right\rbrace\) and \(\gamma _{0} = \left|\mathcal {A}_{0}\right|\), and each vertex in this set brings at most \(k-1\) edges;
•
\(\mathcal {A} = \left\lbrace a_{k-1}, a_{k-1,j}: j \in [k-2]\right\rbrace \cap S\) and \(\gamma = |\mathcal {A}|\), at most one vertex from this set brings \(k-2\) edges and every other vertex brings at most \(k-3\) edges;
•
\(\beta = \left|S \cap \left\lbrace a_{k}^{i}, a_{k,i}^{k-1,j}: i, j \in [k-2]\right\rbrace \right|\), and each vertex in this set brings at most \(k-2\) edges;
•
\(c = \left|S \cap \left\lbrace a_{k-3}, a_{k-2}\right\rbrace \right|\), and each vertex brings at most \(k-3\) edges.
At most \(\gamma\) vertices out of \(\mathcal {A}_{0}\) bring \(k-1\) edges each, and each of the rest at most \(k-2\) edges. Let \(\delta = \gamma _{0} - \gamma\) if \(\gamma _{0} \ge \gamma\), and \(\delta = 0\) otherwise. When \(c = 0\), each vertex in S brings at most \(k-3\) edges, henceWhen \(c = 1\), the single vertex in the set \(S \cap \left\lbrace a_{k-3}, a_{k-2}\right\rbrace\) brings \(k-4\) edges. Thus,and as \(\delta (k-2) + \gamma (k-3) + 1 + \beta (k-2) + (k-4) \lt (k-1)\left\lbrace \gamma + \delta + \beta + 1\right\rbrace\), the fraction in Equation (4.3) is strictly increasing in \(\gamma _{0} - \delta\). As \(\gamma _{0} - \delta \le \gamma\), we haveWhen \(c = 2\), we haveso that, since \(\delta (k-2) + \gamma (k-3) + 1 + \beta (k-2) + 2(k-3) \lt (k-1)\left\lbrace \gamma + \delta + \beta + 2\right\rbrace\), the fraction in Equation (4.5) is strictly increasing in \(\gamma _{0} - \delta\). As \(\gamma _{0} - \delta \le \gamma\), hence□
\begin{equation} \frac{e(S, H)}{v(S, H)} \le k-3. \end{equation}
(4.2)
\begin{align} \frac{e(S, H)}{v(S, H)} & \le \frac{(\gamma _{0} - \delta)(k-1) + \delta (k-2) + (\gamma -1)(k-3) + (k-2) + \beta (k-2) + (k-4)}{\gamma _{0} + \gamma + \beta + 1} \nonumber \nonumber\\ &= \frac{(\gamma _{0} - \delta)(k-1) + \delta (k-2) + \gamma (k-3) + 1 + \beta (k-2) + (k-4)}{(\gamma _{0} - \delta) + \gamma + \delta + \beta + 1}, \end{align}
(4.3)
\begin{align} \frac{e(S, H)}{v(S, H)} & \le \frac{\gamma (k-1) + \delta (k-2) + \gamma (k-3) + 1 + \beta (k-2) + (k-4)}{\gamma + \gamma + \delta + \beta + 1} \nonumber \nonumber\\ &= \frac{\gamma (2k-4) + \delta (k-2) + \beta (k-2) + (k-3)}{2 \gamma + \delta + \beta + 1} \nonumber \nonumber\\ &= k - 2 - \frac{1}{2 \gamma + \delta + \beta + 1} \le k - 2 - \Theta \left(\frac{1}{k^{2}}\right). \end{align}
(4.4)
\begin{align} \frac{e(S, H)}{v(S, H)} & \le \frac{(\gamma _{0} - \delta)(k-1) + \delta (k-2) + (\gamma -1)(k-3) + (k-2) + \beta (k-2) + 2(k-3)}{\gamma _{0} + \gamma + \beta + 2} \nonumber \nonumber\\ &= \frac{(\gamma _{0} - \delta)(k-1) + \delta (k-2) + \gamma (k-3) + 1 + \beta (k-2) + 2(k-3)}{(\gamma _{0} - \delta) + \gamma + \delta + \beta + 2} \end{align}
(4.5)
\begin{align} \frac{e(S, H)}{v(S, H)} & \le \frac{\gamma (k-1) + \delta (k-2) + \gamma (k-3) + 1 + \beta (k-2) + 2(k-3)}{\gamma + \gamma + \delta + \beta + 2} \end{align}
(4.6)
\begin{align} &= \frac{\gamma (2k-4) + \delta (k-2) + \beta (k-2) + 1 + 2(k-3)}{2\gamma + \delta + \beta + 2} \end{align}
(4.7)
\begin{align} &= k - 2 - \frac{1}{2\gamma + \delta + \beta + 2} \le k - 2 - \Theta \left(\frac{1}{k^{2}}\right). \end{align}
(4.8)
We now discuss the roles that Theorem 2.5 and Lemma 4.1 together play in helping Duplicator respond to Spoiler in the \((k-3)\)-rd round. As mentioned previously, Duplicator uses the full level-\((k-3)\) extension property to choose \(y_{1}, \ldots , y_{k-4}\) from \(G_{2}\) in response to Spoiler’s choice of \(x_{1}, \ldots , x_{k-4}\) from \(G_{1}\) in the first \(k-4\) rounds. Let us define H to be a graph on vertices \(a_{1}, \ldots , a_{k-4}\), isomorphic to the subgraph induced on \(y_{1}, \ldots , y_{k-4}\) by \(G_{2}\), such that the isomorphism maps \(a_{i}\) to \(y_{i}\) for all \(i \in [k-4]\). Once Spoiler chooses \(x_{k-3}\), we define the graph G, with \(H \subset G\), on vertices \(a_{1}, \ldots , a_{k}\), \(a_{k-1,j}\) for \(j \in [k-2]\), \(a_{k}^{i}\) for \(i \in [k-2]\), \(a_{k}^{k-1,j}\) for \(j \in [k-2]\), and \(a_{k,i}^{k-1,j}\) for \(i, j \in [k-2]\), such that
From Lemma 4.1, we know that the pair \((G, H)\) is \(\alpha\)-safe for \(\alpha\) that satisfies Equation (4.1), which then yields \(f_{\alpha }(G,H) \gt 0\). Theorem 2.5 then guarantees that with probability approaching 1 as \(n \rightarrow \infty\), the random variable \(N_{(G,H)}\left(y_{1}, \ldots , y_{k-4}\right)\) is at least 1, which in turn implies that \(G_{2}\) contains at least one induced subgraph that is a strict \((G,H)\)-extension of the subgraph induced on \(\left\lbrace y_{1}, \ldots , y_{k-4}\right\rbrace\).
For the sake of notational convenience, let us name the vertices of this extension inside \(G_{2}\) same as the corresponding vertices in \(V(G) \setminus V(H)\). In other words, we have now established that with probability approaching 1, there exist in \(G_{2}\) vertices \(a_{k-3}\), \(a_{k-2}\), \(a_{k-1}\), \(a_{k}\), \(a_{k-1,j}\) for \(j \in [k-2]\), \(a_{k}^{i}\) for \(i \in [k-2]\), \(a_{k}^{k-1,j}\) for \(j \in [k-2]\), and \(a_{k,i}^{k-1,j}\) for \(i, j \in [k-2]\), such that they, along with \(a_{i} = y_{i}\) for all \(i \in [k-4]\), satisfy conditions (i)–(viii). From here onward, these vertices will play key roles in Duplicator’s responses to Spoiler in rounds \(k-3\), \(k-2\), \(k-1\), and k. To begin with, Duplicator sets \(y_{k-3} = a_{k-3}\), and the required adjacency relations are maintained because of (i).
Once Spoiler chooses \(x_{k-2}\) from \(G_{1}\) in round \(k-2\), we have to consider a few different possibilities with regard to the adjacency relations that \(x_{k-2}\) has with the previously chosen vertices \(x_{1}, \ldots , x_{k-3}\). These are addressed separately in Section 4.1 and Section 4.2. Within each of Sections 4.1 and 4.2, we further discuss Duplicator’s responses to Spoiler in rounds \(k-1\) and k.
4.1 First Possibility for Round \(k-2\)
Here, we consider the scenario where in round \(k-2\), Spoiler chooses \(x_{k-2}\) that is adjacent to all of \(x_{1}, \ldots , x_{k-3}\). Then, Duplicator selects \(y_{k-2} = a_{k-2}\), and by (ii), the desired adjacency relations are maintained. We next consider the various possibilities for Spoiler’s choice in round \(k-1\), and analyze how Duplicator responds, in round \(k-1\) as well as round k, in each scenario. Note here that the situation where Spoiler selects, in round k, a vertex \(x_{k}\) that is adjacent to at most \(k-3\) many of the previously chosen \(x_{1}, \ldots , x_{k-1}\), is discussed separately in (iv).
(Section 4.1, Case 1) Suppose in round \(k-1\), Spoiler selects \(x_{k-1}\) that is adjacent to all of \(x_{1}, \ldots , x_{k-2}\). In this case, Duplicator selects \(y_{k-1} = a_{k-1}\), and the desired adjacency relations are maintained thanks to (iii). Within this scenario, we now discuss the various ways Spoiler may choose to move in the k-th and final round of the game, and Duplicator’s response accordingly.
If Spoiler selects \(x_{k}\) adjacent to \(x_{1}, \ldots , x_{k-1}\), then Duplicator sets \(y_{k} = a_{k}\), so that by (v), the desired adjacency relations are maintained. If on the other hand, Spoiler selects \(x_{k}\) that is adjacent to \(x_{\ell }\) for all \(\ell \in [k-1] \setminus \lbrace i\rbrace\) and non-adjacent to \(x_{i}\) for some \(i \in [k-2]\), then Duplicator sets \(y_{k} = a_{k}^{i}\), and the desired adjacency relations hold due to (vi). If in round k, Spoiler selects \(x_{k}\) adjacent to \(x_{1}, \ldots , x_{k-2}\) and non-adjacent to \(x_{k-1}\), then Duplicator sets \(y_{k} = a_{k}^{k-1,1}\), and the desired adjacency relations hold thanks to (vii).
(Section 4.1, Case 2) Suppose in round \(k-1\), Spoiler selects \(x_{k-1}\) that is adjacent to \(x_{\ell }\) for all \(\ell \in [k-2] \setminus \lbrace j\rbrace\) and non-adjacent to \(x_{j}\), for some \(j \in [k-2]\). In this case, Duplicator sets \(y_{k-1} = a_{k-1,j}\), and by (iv), the desired adjacency relations are satisfied. We now consider, within this scenario, the various moves that Spoiler may make in round k, and Duplicator’s response accordingly.
If in round k, Spoiler selects \(x_{k}\) that is adjacent to \(x_{1}, \ldots , x_{k-1}\), then Duplicator sets \(y_{k} = a_{k}^{k-1,j}\), and the required adjacency relations hold due to (vii). If in round k, Spoiler selects \(x_{k}\) adjacent to \(x_{\ell }\) for all \(\ell \in [k-1] \setminus \lbrace i\rbrace\) and non-adjacent to \(x_{i}\), for some \(i \in [k-2]\), then Duplicator sets \(y_{k} = a_{k,i}^{k-1,j}\), and the required adjacency relations hold because of (viii). If in round k, Spoiler selects \(x_{k}\) adjacent to \(x_{1}, \ldots , x_{k-2}\) and non-adjacent to \(x_{k-1}\), Duplicator sets \(y_{k} = a_{k}\), and the required adjacency relations are maintained because of (v).
(Section 4.1, Case 3) Suppose in round \(k-1\), Spoiler selects \(x_{k-1}\) that is adjacent to at most \(k-4\) many vertices out of \(x_{1}, \ldots , x_{k-2}\). Let \(H^{\prime }\) be the subgraph induced by \(G_{2}\) on \(y_{1}, \ldots , y_{k-4}\), \(y_{k-3} = a_{k-3}\), \(y_{k-2} = a_{k-2}\), \(a_{k-1}\), and \(a_{k}\) (the existence of \(a_{k-1}\) and \(a_{k}\) has been established right after the proof of Lemma 4.1). Consider a graph \(G^{\prime }\) that comprises the vertices \(y_{1}, \ldots , y_{k-2}\), the vertices \(a_{k-1}\) and \(a_{k}\), and new vertices \(b_{k-1}\) and \(b_{k}^{i}\), for \(i \in [k-2]\), such that \(H^{\prime } \subset G^{\prime }\) and \(E(G^{\prime }) \setminus E(H^{\prime })\) comprises precisely the following edges and non-edges:
(B1)
\(b_{k-1} \sim y_{i}\) iff \(x_{k-1} \sim x_{i}\) for all \(i \in [k-2]\) and \(b_{k-1} \sim a_{k-1}\), but \(b_{k-1} \nsim a_{k}\);
(B2)
\(b_{k}^{i} \sim b_{k-1}\) and \(b_{k}^{i} \sim y_{\ell }\) for all \(\ell \in [k-2] \setminus \lbrace i\rbrace\), but \(b_{k}^{i} \nsim y_{i}\), for all \(i \in [k-2]\).
The pair \((G^{\prime }, H^{\prime })\) is \(\alpha\)-safe for some \(\alpha\) that satisfies Equation (4.1).
Consider S with \(H^{\prime } \subset S \subseteq G^{\prime }\). As in Lemma 4.1, there are two layers: the \((k-1)\)-st comprising \(b_{k-1}\) and the k-th one the rest. If \(b_{k-1} \in S\), it brings at most \(k-3\) edges. Let \(\gamma = |S \cap \lbrace b_{k}^{i}: i \in [k-2]\rbrace |\): each vertex in this set brings \(k-2\) edges. We then haveIf \(b_{k-1} \notin S\), then each vertex in S brings at most \(k-3\) edges, hence Equation (4.2) holds, and therefore, the final upper bound of Equation (4.9) holds as well.□
\begin{align} \frac{e(S, H^{\prime })}{v(S, H^{\prime })} \le \frac{(k-3) + (k-2)\gamma }{1 + \gamma } = k-2 - \frac{1}{\gamma +1} \le k - 2 - \Theta \left(\frac{1}{k^{2}}\right). \end{align}
By Lemma 4.2 and Theorem 2.5, the vertices \(b_{k-1}\) and \(b_{k}^{i}\), for all \(i \in [k-2]\), exist a.a.s. in \(G_{2} \stackrel{d}{=} G(n, n^{-\alpha })\) for \(\alpha\) as in Equation (4.1). In response to Spoiler’s choice of \(x_{k-1}\) in round \(k-1\), Duplicator sets \(y_{k-1} = b_{k-1}\), and (iii)a ensures that the required adjacency relations hold. We now discuss the various possibilities for Spoiler’s move in round k and Duplicator’s response accordingly.
If in round k, Spoiler selects \(x_{k}\) that is adjacent to all of \(x_{1}, \ldots , x_{k-1}\), Duplicator sets \(y_{k} = a_{k-1}\), and by (iii) and (iii)a, the required adjacency relations hold. If in round k, Spoiler selects \(x_{k}\) that is adjacent to \(x_{\ell }\) for all \(\ell \in [k-1] \setminus \lbrace i\rbrace\), and non-adjacent to \(x_{i}\), for some \(i \in [k-2]\), then Duplicator sets \(y_{k} = b_{k}^{i}\), and by (iii)b, the required adjacency relations hold. If in round k, Spoiler selects \(x_{k}\) that is adjacent to \(x_{1}, \ldots , x_{k-2}\) and non-adjacent to \(x_{k-1}\), Duplicator sets \(y_{k} = a_{k}\), so that by (v) and (iii)a, the required adjacency relations hold.
(Section 4.1, Case 4) If in any of the three scenarios (i), (ii), and (iii), Spoiler selects, in round k, a vertex \(x_{k}\) that is adjacent to at most \(k-3\) many out of \(x_{1}, \ldots , x_{k-1}\), then, denoting by \(G^{\prime \prime }\) and \(H^{\prime \prime }\), respectively, the subgraphs induced by \(G_{1}\) on \(\lbrace x_{1}, \ldots , x_{k}\rbrace\) and \(\lbrace x_{1}, \ldots , x_{k-1}\rbrace\), it is immediate that \((G^{\prime \prime }, H^{\prime \prime })\) is \(\alpha\)-safe for \(\alpha\) as in Equation (4.1). Consequently, by Theorem 2.5, a.a.s. there exists b in \(G_{2}\) such that \(b \sim y_{i}\) iff \(x_{k} \sim x_{i}\) for all \(i \in [k-1]\). Duplicator sets \(y_{k} = b\) in round k and the required adjacency relations are maintained, thus allowing her to win the game.
4.2 Second Possibility for Round \(k-2\)
Here, we consider the scenario where in round \(k-2\), Spoiler chooses \(x_{k-2}\) that is adjacent to at most \(k-4\) many vertices out of \(x_{1}, \ldots , x_{k-3}\). Let \(H^{\prime }\) be the subgraph induced by \(G_{2}\) on \(y_{1}, \ldots , y_{k-3}\). Consider the following new vertices:
(C1)
\(c_{k-2}\) with \(c_{k-2} \sim y_{i}\) iff \(x_{k-2} \sim x_{i}\) for all \(i \in [k-3]\);
(C2)
\(c_{k-1}\) which is adjacent to all of \(y_{1}, \ldots , y_{k-3}, c_{k-2}\);
(C3)
\(c_{k-1,j}\) which is adjacent to \(y_{\ell }\) for all \(\ell \in [k-3] \setminus \lbrace j\rbrace\), adjacent to \(c_{k-2}\), and non-adjacent to \(y_{j}\), for all \(j \in [k-3]\); \(c_{k-1,k-2}\) which is adjacent to \(y_{1}, \ldots , y_{k-3}\) and non-adjacent to \(c_{k-2}\);
(C4)
\(c_{k}\) which is adjacent to all of \(y_{1}, \ldots , y_{k-3}, c_{k-2}, c_{k-1}\), and non-adjacent to \(c_{k-1,j}\) for all \(j \in [k-2]\);
(C5)
\(c_{k}^{i}\) which is adjacent to \(y_{\ell }\) for all \(\ell \in [k-3] \setminus \lbrace i\rbrace\), adjacent to \(c_{k-2}\) and \(c_{k-1}\), and non-adjacent to \(y_{i}\), for all \(i \in [k-3]\); \(c_{k}^{k-2}\) which is adjacent to \(y_{1}, \ldots , y_{k-3}, c_{k-1}\) and non-adjacent to \(c_{k-2}\);
(C6)
\(c_{k}^{k-1,j}\) which is adjacent to all of \(y_{1}, \ldots , y_{k-3}, c_{k-2}, c_{k-1,j}\), and non-adjacent to \(c_{k-1}\), for all \(j \in [k-2]\);
(C7)
for each \(j \in [k-2]\), \(c_{k,i}^{k-1,j}\) which is adjacent to \(y_{\ell }\) for all \(\ell \in [k-3] \setminus \lbrace i\rbrace\), to \(c_{k-2}\) and \(c_{k-1,j}\), and non-adjacent to \(y_{i}\), for each \(i \in [k-3]\); \(c_{k,k-2}^{k-1,j}\) which is adjacent to \(y_{1}, \ldots , y_{k-3}, c_{k-1,j}\) and non-adjacent to \(c_{k-2}\).
Let \(G^{\prime }\) be the graph on \(y_{1}, \ldots , y_{k-3}, c_{k-2}, c_{k-1}, c_{k-1,j}, j \in [k-2], c_{k}, c_{k}^{i}, i \in [k-2], c_{k}^{k-1,j}, j \in [k-2], c_{k,i}^{k-1,j}, i, j \in [k-2]\), with \(H^{\prime } \subset G^{\prime }\) and \(E(G^{\prime }) \setminus E(H^{\prime })\) comprising precisely the edges and non-edges described above.
The pair \((G^{\prime }, H^{\prime })\) is \(\alpha\)-safe for some \(\alpha\) that satisfies Equation (4.1).
As in Lemma 4.1, there are three layers in which vertices can be added to a graph S with \(H^{\prime } \subset S \subseteq G^{\prime }\): the \((k-2)\)-nd layer comprising only \(c_{k-2}\), the \((k-1)\)-st comprising \(c_{k-1}\), \(c_{k-1,j}\) for \(j \in [k-2]\), and the k-th layer the rest; we also consider the same ordering of vertices in any S with \(H^{\prime } \subset S \subseteq G^{\prime }\) and the same meaning of “bringing edges” as in Lemma 4.1. Suppose
•
\(\mathcal {A}_{0} = S \cap \lbrace c_{k}, c_{k}^{k-1,j}: j \in [k-2]\rbrace\) with \(\gamma _{0} = \left|\mathcal {A}_{0}\right|\), and each vertex in this set brings at most \(k-1\) edges;
•
\(\mathcal {A} = S \cap \lbrace c_{k-1}, c_{k-1,j}: j \in [k-2]\rbrace\) with \(\gamma = |\mathcal {A}|\), and at most one vertex in this set brings at most \(k-2\) edges, and each of the others at most \(k-3\) edges;
•
\(\beta = |S \cap \lbrace c_{k}^{i}, c_{k,i}^{k-1,j}: i, j \in [k-2]\rbrace |\), and each vertex in this set brings at most \(k-2\) edges; and
•
\(c = |S \cap \lbrace c_{k-2}\rbrace |\), and if this set is non-empty, it brings at most \(k-4\) edges.
At most \(\gamma\) vertices in \(\mathcal {A}_{0}\) bring \(k-1\) edges each, and the remaining bring at most \(k-2\) edges each. Let \(\delta = \gamma _{0} - \gamma\) if \(\gamma _{0} \ge \gamma\), and \(\delta = 0\) otherwise. If \(c = 0\), each vertex in S brings at most \(k-3\) edges, hence Equation (4.2) holds. If \(c = 1\), the same analysis as the \(c = 1\) case of Lemma 4.1 applies.□
By Lemma 4.3 and Theorem 2.5, the vertices \(c_{k-2}\), \(c_{k-1}\), \(c_{k-1,j}\) for all \(j \in [k-2]\), \(c_{k}\), \(c_{k}^{i}\) for all \(i \in [k-2]\), \(c_{k}^{k-1,j}\) for all \(j \in [k-2]\), and \(c_{k,i}^{k-1,j}\) for all \(i, j \in [k-2]\) exist a.a.s. in \(G_{2}\). In response to Spoiler’s choice of \(x_{k-2}\) in round \(k-2\), Duplicator sets \(y_{k-2} = c_{k-2}\), and the required adjacency relations are satisfied due to (i). We now consider what happens in rounds \(k-1\) and k. At the very outset, we mention that if in round k, Spoiler chooses \(x_{k}\) that is adjacent to at most \(k-3\) out of \(x_{1}, \ldots , x_{k-1}\), Duplicator wins by the same argument as outlined in (iv).
(Section 4.2, Case 1) If in round \(k-1\), Spoiler selects \(x_{k-1}\) that is adjacent to \(x_{1}, \ldots , x_{k-2}\), then Duplicator sets \(y_{k-1} = c_{k-1}\), and the required adjacency relations hold due to (ii). We now discuss the various possibilities that may transpire in round k.
If in round k, Spoiler selects \(x_{k}\) that is adjacent to \(x_{1}, \ldots , x_{k-1}\), then Duplicator sets \(y_{k} = c_{k}\), and the required adjacency relations are satisfied because of (iv). If Spoiler selects \(x_{k}\) that is adjacent to \(x_{\ell }\) for all \(\ell \in [k-1] \setminus \lbrace i\rbrace\) and non-adjacent to \(x_{i}\) for some \(i \in [k-2]\), then Duplicator sets \(y_{k} = c_{k}^{i}\), and the required adjacency relations hold due to (v). If Spoiler selects \(x_{k}\) that is adjacent to \(x_{1}, \ldots , x_{k-2}\) and non-adjacent to \(x_{k-1}\), Duplicator sets \(y_{k} = c_{k}^{k-1,1}\), and the required adjacency relations hold because of (vi).
(Section 4.2, Case 2) If Spoiler selects \(x_{k-1}\) which is adjacent to \(x_{\ell }\) for all \(\ell \in [k-2] \setminus \lbrace j\rbrace\) and non-adjacent to \(x_{j}\), for some \(j \in [k-2]\), then Duplicator sets \(y_{k-1} = c_{k-1,j}\), and the required adjacency relations hold due to (iii). We now discuss the various possibilities that may transpire in round k.
If in round k, Spoiler selects \(x_{k}\) which is adjacent to \(x_{1}, \ldots , x_{k-1}\), then Duplicator sets \(y_{k} = c_{k}^{k-1,j}\), and the required adjacency relations hold due to (vi). If Spoiler selects \(x_{k}\) which is adjacent to \(x_{\ell }\) for all \(\ell \in [k-1] \setminus \lbrace i\rbrace\) and non-adjacent to \(x_{i}\) for some \(i \in [k-2]\), Duplicator sets \(y_{k} = c_{k,i}^{k-1,j}\), and the required adjacency relations hold due to (vii). If Spoiler selects \(x_{k}\) which is adjacent to \(x_{1}, \ldots , x_{k-2}\) and non-adjacent to \(x_{k-1}\), Duplicator sets \(y_{k} = c_{k}\), and the required adjacency relations hold due to (iv).
(Section 4.2, Case 3) Suppose Spoiler selects \(x_{k-1}\) that is adjacent to at most \(k-4\) many vertices out of \(x_{1}, \ldots , x_{k-2}\). By Lemma 4.2, we conclude that there exist, a.a.s. in \(G_{2}\), the following vertices, edges, and non-edges:
(D1)
\(d_{k-1}\) with \(d_{k-1} \sim y_{i}\) iff \(x_{k-1} \sim x_{i}\) for all \(i \in [k-2]\) and \(d_{k-1} \sim c_{k-1}\), but \(d_{k-1} \nsim c_{k}\);
(D2)
\(d_{k}^{i}\) which is adjacent to \(y_{\ell }\) for all \(\ell \in [k-2] \setminus \lbrace i\rbrace\), adjacent to \(d_{k-1}\), and non-adjacent to \(y_{i}\), for each \(i \in [k-2]\).
Duplicator then sets \(y_{k-1} = d_{k-1}\), and the required adjacency relations hold due to (iii)a. We now discuss how Spoiler may move in round k, and Duplicator’s responses accordingly.
If Spoiler selects \(x_{k}\) which is adjacent to all of \(x_{1}, \ldots , x_{k-1}\), then Duplicator sets \(y_{k} = c_{k-1}\), and the required adjacency relations hold due to (ii) and (iii)a. If Spoiler selects \(x_{k}\) which is adjacent to \(x_{\ell }\) for all \(\ell \in [k-1] \setminus \lbrace i\rbrace\) and non-adjacent to \(x_{i}\) for some \(i \in [k-2]\), then Duplicator sets \(y_{k} = d_{k}^{i}\), and the required adjacency relations hold due to (iii)b. If Spoiler selects \(x_{k}\) which is adjacent to \(x_{1}, \ldots , x_{k-2}\) and not to \(x_{k-1}\), then Duplicator sets \(y_{k} = c_{k}\), and the required adjacency relations hold due to (iv) and (iii)a.
5 Existential First-Order Sentences of Quantifier Depth 4
In this section, we consider the class \(\mathcal {E}_{4}\) of all existential first-order sentences with quantifier depth at most 4. From Theorem 1.3, we conclude that for all \(0 \lt \alpha \lt \frac{1}{2}\), the random graph \(G(n, n^{-\alpha })\) satisfies the zero-one law for \(\mathcal {E}_{4}\). Our goal, therefore, is to find the minimum \(\alpha _{4} \in [\tfrac{1}{2}, 1)\) such that the random graph \(G(n, n^{-\alpha })\) fails to satisfy the zero-one law for \(\mathcal {E}_{4}\).
To this end, our purpose is to come up with an \(\alpha _4 \in [\tfrac{1}{2},1)\), a finite graph \(G_{0}\), and an \(\mathcal {E}_4\)-sentence \(\varphi\) such that
•
for every \(\alpha \lt \alpha _{4}\), \(G(n,n^{-\alpha })\) obeys the zero-one law for \(\mathcal {E}_4\);
•
a.a.s., \(\varphi\) is true on \(G(n,n^{-\alpha _{4}})\) if and only if \(G(n,n^{-\alpha _{4}})\) contains an induced subgraph isomorphic to \(G_0\); and
•
\(G_0\) is strictly balanced and its density equals \(1/\alpha _4\).
Then, by Theorem 2.10, we know that the limit of the probability that \(G\left(n, n^{-\alpha _{4}}\right)\) contains a copy of \(G_{0}\) is a positive real strictly less than 1.
We first state here the sentence \(\varphi\). For any vertices \(a_{1}, a_{2}, b_{1}, b_{2}, b_{3}\), define the sentenceand for vertices \(a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, b_{4}\), define the sentenceThe sentence \(\varphi\) is now stated as follows:
\begin{equation} \begin{split} \psi _{1}(a_{1}, a_{2}, b_{1}, b_{2}, b_{3}) = [b_{1} \sim a_{1}] \wedge [b_{1} \sim a_{2}] \wedge [b_{2} \sim a_{1}] \wedge [b_{2} \nsim a_{2}] \wedge [b_{3} \nsim a_{1}] \wedge [b_{3} \sim a_{2}],\end{split} \end{equation}
(5.1)
\begin{equation} \begin{split} \psi _{2}(a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, b_{4}) = [b_{1} \sim a_{1}] \wedge [b_{1} \sim a_{2}] \wedge [b_{1} \sim a_{3}] \wedge [b_{2} \sim a_{1}] \wedge [b_{2} \sim a_{2}] \wedge [b_{2} \nsim a_{3}] \\ \wedge [b_{3} \sim a_{1}] \wedge [b_{3} \nsim a_{2}] \wedge [b_{3} \sim a_{3}] \wedge [b_{4} \nsim a_{1}] \wedge [b_{4} \sim a_{2}] \wedge [b_{4} \sim a_{3}].\end{split} \end{equation}
(5.2)
\begin{equation} \begin{split} \exists x \exists a \exists a_{1,1} \exists a_{1,0} \exists a_{0,1} \exists a_{1,1}^{1,1} \exists a^{\prime }_{1,1} \exists a_{1,1}^{1,0} \exists a_{1,1}^{0,1} \exists a_{1,0}^{1,1} \exists a^{\prime }_{1,0} \exists a_{1,0}^{1,0} \exists a_{1,0}^{0,1} \exists a_{0,1}^{1,1} \exists a^{\prime }_{0,1} \exists a_{0,1}^{1,0} \exists a_{0,1}^{0,1} \\ \exists b \exists b_{1,1} \exists b_{1,0} \exists b_{0,1} \exists b_{1,1}^{1,1} \exists b_{1,1}^{1,0} \exists b^{\prime }_{1,1} \exists b_{1,1}^{0,1} \exists b_{1,0}^{1,1} \exists b^{\prime }_{1,0} \exists b_{1,0}^{1,0} \exists b_{1,0}^{0,1} \exists b_{0,1}^{1,1} \exists b^{\prime }_{0,1} \exists b_{0,1}^{1,0} \exists b_{0,1}^{0,1} [x \sim a] \\ \wedge \left[\psi _{1}(x, a, a_{1,1}, a_{1,0}, a_{0,1})\right] \wedge \left[\psi _{2}\left(x, a, a_{1,1}, a_{1,1}^{1,1}, a^{\prime }_{1,1}, a_{1,1}^{1,0}, a_{1,1}^{0,1}\right)\right] \wedge \left[\psi _{2}\left(x, a, a_{1,0}, a_{1,0}^{1,1}, a^{\prime }_{1,0}, a_{1,0}^{1,0}, a_{1,0}^{0,1}\right)\right] \\ \wedge \left[\psi _{2}\left(x, a, a_{0,1}, a_{0,1}^{1,1}, a^{\prime }_{0,1}, a_{0,1}^{1,0}, a_{0,1}^{0,1}\right)\right] \wedge [x \nsim b] \wedge \left[\psi _{1}(x, b, b_{1,1}, b_{1,0}, b_{0,1})\right] \\ \wedge \left[\psi _{2}\left(x, b, b_{1,1}, b_{1,1}^{1,1}, b^{\prime }_{1,1}, b_{1,1}^{1,0}, b_{1,1}^{0,1}\right)\right] \wedge \left[\psi _{2}\left(x, b, b_{1,0}, b_{1,0}^{1,1}, b^{\prime }_{1,0}, b_{1,0}^{1,0}, b_{1,0}^{0,1}\right)\right] \\ \wedge \left[\psi _{2}\left(x, b, b_{0,1}, b_{0,1}^{1,1}, b^{\prime }_{0,1}, b_{0,1}^{1,0}, b_{0,1}^{0,1}\right)\right].\end{split} \end{equation}
(5.3)
We now show that the graph \(G_{0}\), shown in Figure 1, is such that
Fig. 1.
(i)
the graph \(G_{0}\) is strictly balanced;
(ii)
if a graph G contains an induced subgraph isomorphic to \(G_{0}\), then \(G \models \varphi\); if a graph \(G \models \varphi\), then G contains either an induced subgraph isomorphic to \(G_{0}\) or it contains an induced subgraph with at most 43 vertices whose maximal density is at least as large as \({\rho _{\max }}(G_{0}) = \rho (G_{0})\) (this identity follows from the observation that \(G_{0}\) is strictly balanced).
We first prove the claim in (i), in the following lemm.
The graph \(G_{0}\) in Figure 1 is strictly balanced.
Observe that \(G_{0}\) can be split into two edge-disjoint parts having only x in common, illustrated in Figure 2.
Fig. 2.
The vertices in the a part can be added in the following sequence:
(a)
in step 0, the vertex x,
(b)
in step 1, the vertex a, bringing one edge,
(c)
in step 2, the vertices \(a^{\prime }_{1,1}\) and \(a_{1,1}\), each bringing precisely two edges,
(d)
in step 3, the vertices \(a_{1,0}\) and \(a_{0,1}\), each bringing precisely two edges,
(e)
in step 4, the vertices \(a_{1,0}^{1,0}\), \(a_{0,1}^{0,1}\), \(a_{1,0}^{0,1}\), and \(a_{0,1}^{1,0}\), each bringing precisely two edges,
(f)
in step 5, the vertex \(a_{1,1}^{1,1}\), bringing three edges.
The vertices in the b part can be added in the following sequence:
(a)
in step 0, the vertex x,
(b)
in step 1, the vertex \(b_{1,1}\), bringing one edge,
(c)
in step 2, the vertices \(b_{1,1}^{1,1}\) and \(b_{1,0}\), each bringing two edges,
(d)
in step 3, the vertices b and \(b_{1,0}^{1,0}\), each bringing two edges,
(e)
in step 4, the vertices \(b_{0,1}\), \(b^{\prime }_{1,1}\), and \(b_{1,0}^{0,1}\), each bringing two edges,
(f)
in step 5, the vertices \(b_{0,1}^{1,0}\) and \(b_{0,1}^{0,1}\), each bringing two edges.
If we consider a subgraph H of \(G_{0}\) containing x, a, \(b_{1,1}\), and \(y_{i}\) vertices from step i of a part and \(z_{i}\) vertices from step i of b part for \(i \in \lbrace 2, 3, 4, 5\rbrace\), with \(y_{2}, y_{3}, z_{2}, z_{3}, z_{5} \in \lbrace 0, 1, 2\rbrace\), \(y_{4}, z_{4} \in \lbrace 0, 1, 2, 3, 4\rbrace\), and \(y_{5} \in \lbrace 0, 1\rbrace\), the number of edges in H is at most \(1 + 2 \sum _{i=2}^{4} (y_{i}+z_{i}) + 3y_{5} + 2z_{5},\) whereas the number of vertices is \(3 + \sum _{i=2}^{5}(y_{i}+z_{i})\). Letting \(y = \sum _{i=2}^{4} (y_{i}+z_{i}) + z_{5}\) and \(z = y_{5}\), \(\rho (H)\) is at mostWe note here thatwhich is positive since \(z \le 1\). Thus, the density increases with y. Similarly, the density increases with z. Thus, \(\rho (H) \lt \rho (G_{0})\) whenever H is a proper subgraph of \(G_{0}\) containing x, a, \(b_{1,1}\). When H excludes at least one of x, a, and \(b_{1,1}\), its density is even lower, since in both a and b parts, the vertex added in step 2 brings one edge, and subsequent vertices bring at most two edges each, except possibly for \(a_{1,1}^{1,1}\) if it is included in H.□
\begin{equation} \frac{1 + 2y + 3z}{3 + y + z}. \end{equation}
(5.4)
\[\begin{eqnarray*} \frac{3 + 2y + 3z}{4 + y + z} - \frac{1 + 2y + 3z}{3 + y + z} &= \frac{5-z}{(4+y+z)(3+y+z)}, \nonumber \nonumber \end{eqnarray*}\]
The first part of (ii) is trivial. The appropriate values of \(v(G_{0})\), \(e(G_{0})\), and \(\rho (G_{0})\) are given in Figure 1. We now prove the second part of (ii). For \(\varphi\) to be true on a graph G, the bare minimum we need are the following vertices, edges, and non-edges in G:
(i)
x, a, b where \(x \sim a\) and \(b \nsim x\);
(ii)
\(a_{1,1}\) with \(a_{1,1} \sim x\), \(a_{1,1} \sim a\);
(iii)
\(a_{1,0}\) with \(a_{1,0} \sim x\) and \(a_{1,0} \nsim a\);
(iv)
\(a_{1,1}^{1,1}\) with \(a_{1,1}^{1,1} \sim x\), \(a_{1,1}^{1,1} \sim a\) and \(a_{1,1}^{1,1} \sim a_{1,1}\);
(v)
\(a^{\prime }_{1,1}\) with \(a^{\prime }_{1,1} \sim x\), \(a^{\prime }_{1,1} \sim a\), \(a^{\prime }_{1,1} \nsim a_{1,1}\);
(vi)
\(a_{1,0}^{1,0}\) with \(a_{1,0}^{1,0} \sim x\), \(a_{1,0}^{1,0} \sim a_{1,0}\) and \(a_{1,0}^{1,0} \nsim a\);
(vii)
\(b_{0,1}\) with \(b_{0,1} \sim b\), \(b_{0,1} \nsim x\);
(viii)
\(b_{0,1}^{0,1}\) with \(b_{0,1}^{0,1} \sim b\), \(b_{0,1}^{0,1} \sim b_{0,1}\) and \(b_{0,1}^{0,1} \nsim x\).
Fig. 3.
The set of variables left to evaluate isIn what follows, we consider a family \(\Sigma\) of finite graphs \(\Gamma\) with at most 43 vertices, adding vertices evaluating the elements of \(S_{0}\) to H, such that if \(G \models \varphi\), it contains an induced subgraph isomorphic to some \(\Gamma \in \Sigma\). We show that \({\rho _{\max }}(\Gamma) \gt \rho (G_{0})\) for each \(\Gamma \in \Sigma \setminus G_{0}\) by considering various scenarios, the most difficult of which is discussed in Section 5.1 below, and the rest can be found in the Appendix of the version put on Arxiv, which can be found here.
\begin{equation} \begin{split} S_{0} = \left\lbrace b_{1,1}, a_{0,1}, a_{0,1}^{0,1}, a_{1,1}^{1,0}, a_{1,1}^{0,1}, a_{1,0}^{1,1}, a^{\prime }_{1,0}, a_{1,0}^{0,1}, a_{0,1}^{1,1}, a^{\prime }_{0,1}, a_{0,1}^{1,0}, b_{1,1}^{1,1}, b^{\prime }_{1,1}, b_{1,1}^{1,0}, b_{1,1}^{0,1}, b_{1,0}, b_{1,0}^{1,1}, b^{\prime }_{1,0},\right. \\ \left. b_{1,0}^{1,0}, b_{1,0}^{0,1}, b_{0,1}^{1,1}, b^{\prime }_{0,1}, b_{0,1}^{1,0}\right\rbrace .\end{split} \end{equation}
(5.5)
5.1 The Most Difficult Scenario
Here, we assume that \(a_{0,1}\) and \(a_{0,1}^{0,1}\) are added as new vertices to H, thus yielding the graph \(H_{0}\) as in Figure 4, with 17 edges and 12 vertices.
Fig. 4.
Either \(b_{1,1}\) is a new vertex added to \(H_{0}\), in which case we add edges \(\lbrace b_{1,1}, x\rbrace\) and \(\lbrace b_{1,1}, b\rbrace\), or it belongs toin which case we add \(\lbrace b_{1,1}, b\rbrace\). We denote by \(H^{\prime }_{0}\) the graph obtained after accounting for \(b_{1,1}\). We define the vertices as follows:
\begin{equation} S_{1} = \left\lbrace a, a_{1,0}, a_{1,1}, a_{1,1}^{1,1}, a^{\prime }_{1,1}, a_{1,0}^{1,0}\right\rbrace , \end{equation}
(5.6)
(i)
\(v_{1}\) is adjacent to all of x, b and \(b_{0,1}\),
(ii)
\(v_{2}\) is adjacent to all of x, b and \(b_{1,1}\),
(iii)
\(v_{3}\) is adjacent to all of x, a and \(a_{1,0}\),
(iv)
\(v_{4}\) is adjacent to all of x, a and \(a_{0,1}\),
and we call them the first-level vertices. We call a first-level vertex old if it coincides with a vertex in \(H^{\prime }_{0}\), we call it unique if it is added as a new vertex to \(H^{\prime }_{0}\) and does not coincide with any other first-level vertex, and banal otherwise. The graph obtained after we have accounted for all first-level vertices is denoted \(H_{1}\). We define the vertices as follows:
(i)
\(u_{1}\) is adjacent to x and \(b_{0,1}\), non-adjacent to b,
(ii)
\(u_{2}\) is adjacent to x and b, non-adjacent to \(b_{1,1}\),
(iii)
\(u_{3}\) is adjacent to b and \(b_{1,1}\), non-adjacent to x,
(iv)
\(u_{4}\) is adjacent to x and \(b_{1,1}\), non-adjacent to b,
(v)
\(u_{5}\) is adjacent to a and \(a_{1,0}\), non-adjacent to x,
(vi)
\(u_{6}\) is adjacent to x and \(a_{1,1}\), non-adjacent to a,
(vii)
\(u_{7}\) is adjacent to a and \(a_{1,1}\), non-adjacent to x,
(viii)
\(u_{8}\) is adjacent to x and \(a_{0,1}\), non-adjacent to a.
We call these second-level vertices. We call a second-level vertex old if it coincides with a vertex in \(H^{\prime }_{0}\), we call it banal if it coincides with a first-level vertex that is not old (in other words, coincides with a vertex in \(V(H_{1}) \setminus V(H^{\prime }_{0})\)), and we call it unique otherwise. Note that two or more unique second-level vertices are allowed to coincide with each other.
Note that we have not yet considered a vertex evaluating \(b_{1,0}\), its “extensions” which are vertices evaluating \(b_{1,0}^{1,1}\), \(b^{\prime }_{1,0}\), \(b_{1,0}^{1,0}\), \(b_{1,0}^{0,1}\), as well as \(b^{\prime }_{0,1}\), \(a^{\prime }_{0,1}\) and \(a^{\prime }_{1,0}\). As it happens, some of these end up coinciding with some of the vertices in Figure 1.
If \(v_{3}\) is old, it either coincides with a vertex inin which case we add \(\lbrace v_{3}, a_{1,0}\rbrace\), or \(v_{3} = b_{1,1}\) when \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\), in which case we add \(\lbrace b_{1,1}, a\rbrace\) and \(\lbrace b_{1,1}, a_{1,0}\rbrace\). When \(v_{4}\) is old, either \(v_{4} \in S_{2}\), in which case we add \(\lbrace v_{4}, a_{0,1}\rbrace\), or with \(b_{1,1}\) when \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\), in which case we add \(\lbrace b_{1,1}, a\rbrace\) and \(\lbrace b_{1,1}, a_{0,1}\rbrace\). When \(v_{1}\) is old and coincides with \(b_{1,1}\), we add \(\lbrace b_{1,1}, b_{0,1}\rbrace\); if \(v_{1} \in S_{1} \setminus \lbrace b_{1,1}\rbrace\), we add \(\lbrace v_{1}, b\rbrace\) and \(\lbrace v_{1}, b_{0,1}\rbrace\). When \(v_{2}\) is old, the possibilities according to \(b_{1,1}\) are as follows:
\begin{equation} S_{2} = \left\lbrace a_{1,1}, a_{1,1}^{1,1}, a^{\prime }_{1,1}\right\rbrace , \end{equation}
(5.7)
(a)
if \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\), and \(v_{2} \in S_{1}\), we add \(\lbrace v_{2}, b\rbrace\) and \(\lbrace v_{2}, b_{1,1}\rbrace\);
(b)
if \(b_{1,1} = a_{1,0}\), and \(v_{2} = a_{1,0}^{1,0}\), we add \(\lbrace a_{1,0}^{1,0}, b\rbrace\); if \(v_{2} \ne a_{1,0}^{1,0}\), we add \(\lbrace v_{2}, a_{1,0}\rbrace\) and \(\lbrace v_{2}, b\rbrace\);
(c)
if \(b_{1,1} = a_{1,0}^{1,0}\) and \(v_{2} = a_{1,0}\), we add \(\lbrace a_{1,0}, b\rbrace\); if \(v_{2} \ne a_{1,0}\), we add \(\lbrace v_{2}, a_{1,0}^{1,0}\rbrace\) and \(\lbrace v_{2}, b\rbrace\);
(d)
if \(b_{1,1} = a_{1,1}\) and \(v_{2} \in \lbrace a_{1,0}, a_{1,0}^{1,0}\rbrace\), we add \(\lbrace v_{2}, b\rbrace\) and \(\lbrace v_{2}, a_{1,1}\rbrace\); if \(v_{2} \in \lbrace a, a_{1,1}^{1,1}\rbrace\), we add \(\lbrace v_{2}, b\rbrace\);
(e)
if \(b_{1,1} = a_{1,1}^{1,1}\) and \(v_{2} \in \lbrace a_{1,0}, a^{\prime }_{1,1}, a_{1,0}^{1,0}\rbrace\), we add \(\lbrace v_{2}, b\rbrace\) and \(\lbrace v_{2}, a_{1,1}^{1,1}\rbrace\); if \(v_{2} \in \lbrace a, a_{1,1}\rbrace\), we add \(\lbrace v_{2}, b\rbrace\);
(f)
if \(b_{1,1} = a^{\prime }_{1,1}\) and \(v_{2} \in \lbrace a_{1,1}^{1,1}, a_{1,0}, a_{1,0}^{1,0}\rbrace\), we add \(\lbrace v_{2}, b\rbrace\) and \(\lbrace v_{2}, a^{\prime }_{1,1}\rbrace\); if \(v_{2} = a\), we add \(\lbrace v_{2}, b\rbrace\);
(g)
if \(b_{1,1} = a\), then \(v_{2} \in S_{2}\), and we add \(\lbrace v_{2}, b\rbrace\).
Suppose \(\nu _{1}\) is the number of new, distinct first-level vertices (including both unique and banal ones) that are added to \(H^{\prime }_{0}\). Then the number of edges that we need to add on account of all first-level vertices is at least \(2\nu _{1}+5\) when \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\) and \(v_{2}\) is old; in all other cases, this number is at least \(2\nu _{1}+4\).
When \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\) and both \(v_{2}\) and \(v_{3}\) are old, they bring edges \(\lbrace b_{1,1}, a\rbrace\), \(\lbrace b_{1,1}, a_{1,0}\rbrace\), \(\lbrace a_{1,0}, b\rbrace\) when \(v_{2} = a_{1,0}\) and \(v_{3} = b_{1,1}\), or edges \(\lbrace v_{3}, a_{1,0}\rbrace\), \(\lbrace v_{2}, b\rbrace\), \(\lbrace v_{2}, b_{1,1}\rbrace\) when \(v_{3} \ne b_{1,1}\), and four edges otherwise. If \(v_{2}\) is old and \(v_{3}\) is not, then \(v_{2}\) brings edges \(\lbrace v_{2}, b\rbrace\) and \(\lbrace v_{2}, b_{1,1}\rbrace\). If \(v_{1}\) is old, it brings \(\lbrace v_{1}, b_{0,1}\rbrace\); if \(v_{4}\) is old, it brings \(\lbrace v_{4}, a_{0,1}\rbrace\). This shows that the number of edges added due to old first-level vertices is at least one more than the number of old first-level vertices when \(v_{2}\) is old.
When \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\) but \(v_{2}\) is not old, we get \(\lbrace v_{3}, a_{1,0}\rbrace\) when \(v_{3}\) is old, \(\lbrace v_{4}, a_{0,1}\rbrace\) when \(v_{4}\) is old, \(\lbrace v_{1}, b_{0,1}\rbrace\) when \(v_{1}\) is old; when \(b_{1,1} \in V(H_{0})\), we additionally get \(\lbrace v_{2}, b\rbrace\) when \(v_{2}\) is old. Since \(\lbrace v_{1}, b_{0,1}\rbrace\), \(\lbrace v_{2}, b\rbrace\), \(\lbrace v_{3}, a_{1,0}\rbrace\), and \(\lbrace v_{4}, a_{0,1}\rbrace\) are all distinct, the number of edges added due to old first-level vertices bring is at least as large as the number of old first-level vertices here.
Whether \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\) or not, any two first-level vertices coinciding in a banal vertex bring at least four edges, any three coinciding in a banal vertex bring at least five edges, and all four coinciding in a banal vertex bring at least six edges. This concludes the proof.□
If s banal second-level vertices coincide with a first-level vertex \(v_{i}\), except for when \(u_{2}\) and \(v_{1}\) coincide, at least s additional edges are introduced due to these second-level vertices. If s many unique second-level vertices coincide with each other, they together bring at least \(s+1\) edges.
The only second-level vertices that can coincide with \(v_{1}\) are \(u_{2}\), \(u_{6}\), and \(u_{8}\): when \(v_{1} = u_{2}\), we add no edge; when \(v_{1} = u_{6}\), we add \(\lbrace v_{1}, a_{1,1}\rbrace\); when \(v_{1} = u_{8}\), we add \(\lbrace v_{1}, a_{0,1}\rbrace\). The only second-level vertices that can coincide with \(v_{2}\) are \(u_{6}\) and \(u_{8}\): when \(v_{2} = u_{6}\), we add \(\lbrace v_{2}, a_{1,1}\rbrace\); when \(v_{2} = u_{8}\), we add \(\lbrace v_{2}, a_{0,1}\rbrace\). The only second-level vertices that can coincide with \(v_{i}\), for \(i \in \lbrace 3, 4\rbrace\), are \(u_{1}\), \(u_{2}\), and \(u_{4}\): when \(v_{i} = u_{1}\), we add \(\lbrace v_{i}, b_{0,1}\rbrace\); when \(v_{i} = u_{2}\), we add \(\lbrace v_{i}, b\rbrace\); when \(v_{i} = u_{4}\), we add \(\lbrace v_{i}, b_{1,1}\rbrace\). This proves the first part of Lemma 5.4.
Some or all of \(u_{3}\), \(u_{5}\), and \(u_{7}\) may coincide (and none of them may coincide with any other second-level vertex)—\(u_{3}\) brings \(\lbrace u_{3}, b\rbrace\) and \(\lbrace u_{3}, b_{1,1}\rbrace\), \(u_{5}\) brings \(\lbrace u_{5}, a\rbrace\) and \(\lbrace u_{5}, a_{1,0}\rbrace\), and \(u_{7}\) brings \(\lbrace u_{7}, a\rbrace\) and \(\lbrace u_{7}, a_{1,1}\rbrace\). Of these, only \(\lbrace u_{5}, a\rbrace\) and \(\lbrace u_{7}, a\rbrace\) coincide if \(u_{5} = u_{7}\). Among the remaining vertices \(u_{1}\), \(u_{2}\), \(u_{4}\), \(u_{6}\), and \(u_{8}\), there are two inclusion-maximum sets \(\left\lbrace u_{1}, u_{4}, u_{6}, u_{8}\right\rbrace\) and \(\left\lbrace u_{2}, u_{6}, u_{8}\right\rbrace\) that may coincide. In the former case, \(u_{6}\) brings \(\lbrace u_{6}, a_{1,1}\rbrace\), \(u_{8}\) brings \(\lbrace u_{8}, a_{0,1}\rbrace\), \(u_{1}\) brings \(\lbrace u_{1}, b_{0,1}\rbrace\), and \(u_{4}\) brings \(\lbrace u_{4}, b_{1,1}\rbrace\), which are all distinct; additionally, the common vertex is adjacent to x. In the latter case, \(u_{6}\) brings \(\lbrace u_{6}, a_{1,1}\rbrace\), \(u_{8}\) brings \(\lbrace u_{8}, a_{0,1}\rbrace\), and \(u_{2}\) brings \(\lbrace u_{2}, b\rbrace\), which are all distinct; additionally, the common vertex is adjacent to x.□
Let \(\nu _{2}\) denote the number of unique second-level vertices we add to the graph \(H_{1}\) and e the number of edges that are added to \(H_{1}\) due to non-unique second-level vertices. Let the graph obtained after accounting for all second-level vertices be denoted \(H_{2}\).
5.1.1 First Subcase.
We consider \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\) and \(v_{2}\) not old. If the first-level vertices bring precisely \(2\nu _{1}+4\) edges together, and each distinct, unique second-level vertex brings precisely two edges, then \(\rho (H_{2})\) is at leastFor this to be strictly less than \(\frac{13}{7}\), we require \((\nu _{1} + \nu _{2}) + 7e \lt 8\). Thus, either \(e = 1\) and \(\nu _{1} + \nu _{2} = 0\), which is not possible since \(\nu _{1} + \nu _{2} = 0\) implies \(\nu _{1} = 0\), which implies that \(v_{2}\) is old, contradicting our hypothesis, or else \(e = 0\) and \(\nu _{1} + \nu _{2} \le 7\). In what follows, no two unique second-level vertices are allowed to coincide, nor any banal second-level vertex allowed to exist except when \(v_{1}\) is not old and \(v_{1} = u_{2}\), because of Lemma 5.4. We now split the analysis into a few cases depending on the value of \(\nu _{1}\), keeping in mind that \(v_{2}\) is not old:
\begin{equation} \frac{17 + 2 + (2 \nu _{1}+4) + 2\nu _{2} + e}{12 + 1 + \nu _{1} + \nu _{2}} = \frac{23 + 2(\nu _{1} + \nu _{2}) + e}{13 + (\nu _{1} + \nu _{2})}. \end{equation}
(5.8)
(i)
When \(\nu _{1} = 1\), so that \(\nu _{2} \le 6\): First, suppose all of \(v_{1}, v_{3}, v_{4}\) are old—they together bring precisely three edges only when \(v_{3}, v_{4} \in S_{2}\) and \(v_{1} = b_{1,1}\), and these edges are \(\lbrace v_{3}, a_{1,0}\rbrace\), \(\lbrace v_{4}, a_{0,1}\rbrace\), and \(\lbrace v_{1}, b_{0,1}\rbrace = \lbrace b_{1,1}, b_{0,1}\rbrace\); the edge incident on \(b_{1,1}\) and added due to \(v_{2}\) is \(\lbrace v_{2}, b_{1,1}\rbrace\). In \(H_{1}\), the only neighbours of \(a_{1,0}\) are x, \(a_{1,0}^{1,0}\), and \(v_{3}\), so that there exists no vertex that can play the role of \(u_{5}\); the only neighbours of \(b_{0,1}\) are b, \(b_{0,1}^{0,1}\), and \(v_{1}\), so that no vertex plays the role of \(u_{1}\); the only neighbours of \(a_{0,1}\) are a, \(a_{0,1}^{0,1}\) and \(v_{4}\), so that no vertex plays the role of \(u_{8}\); the only neighbours of \(b_{1,1}\) are x, b, and \(v_{2}\), so that no vertex plays the role of \(u_{4}\); the only common neighbours of x and b are \(b_{1,1}\) and \(v_{2}\), so that no vertex plays the role of \(u_{2}\). Thus \(u_{1}\), \(u_{2}\), \(u_{4}\), \(u_{5}\), \(u_{8}\) need to be added as distinct, unique second-level vertices.
When not all of \(v_{1}, v_{3}, v_{4}\) are old, in addition to \(u_{1}\), \(u_{2}\), \(u_{4}\), \(u_{5}\), \(u_{8}\), we need to add at least one of \(u_{3}\), \(u_{6}\), \(u_{7}\) as a unique, distinct second-level vertex (note that if \(v_{1}\) is not old, it coincides with \(v_{2}\) since \(\nu _{1} = 1\), and hence \(u_{2}\) cannot coincide with \(v_{1}\)).
When \(v_{1}, v_{3}, v_{4}\) are old, we have room to add one new vertex and two new edges to \(H_{2}\); when \(v_{1}, v_{3}, v_{4}\) are not all old, we can neither add a new vertex nor a new edge to \(H_{2}\). We now consider all the possibilities for \(b_{1,0}\):
•
If \(b_{1,0}\) coincides with \(a_{1,0}\), since the only neighbours of \(a_{1,0}\) are x, \(a_{1,0}^{1,0}\), and \(v_{3}\), no vertex in \(H_{2}\) can play the role of \(b_{1,0}^{1,1}\) or \(b_{1,0}^{0,1}\) without adding further edges. We thus have to add both of these as new vertices.
•
If \(b_{1,0}\) coincides with \(u_{1}\), since the only neighbours of \(u_{1}\) are x and \(b_{0,1}\), no vertex in \(H_{2}\) can play the role of \(b_{1,0}^{1,1}\) or \(b_{1,0}^{1,0}\) without adding further edges. We thus have to add both of these as new vertices.
•
If \(b_{1,0}\) coincides with \(u_{4}\), since the only neighbours of \(u_{4}\) are \(b_{1,1}\) and x, no vertex in \(H_{2}\) can play the role of \(b_{1,0}^{1,0}\) or \(b_{1,0}^{0,1}\) without adding further edges. We thus have to add both of these as new vertices.
•
If we add \(b_{1,0}\) as a new vertex, it brings precisely one edge, and we are allowed to add one more edge but no new vertices. This is not enough to account for all of \(b_{1,0}^{1,1}\), \(b_{1,0}^{1,0}\), and \(b_{1,0}^{0,1}\).
Thus, it never suffices to add a single new vertex and two new edges to \(H_{2}\), thus violating the condition \(\nu _{2} \le 6\).
(ii) When \(\nu _{1} = 2\): In this case, we need \(\nu _{2} \le 5\). If \(v_{3}\) and \(v_{4}\) are old, the only neighbours to \(b_{1,1}\) in \(H_{1}\) are x, b, and \(v_{2}\), so that no vertex in \(H_{1}\) plays the role of \(u_{3}\) nor of \(u_{4}\). If \(v_{3}\) and \(v_{1}\) are old, the only neighbours of \(a_{1,1}\) are x, a, \(a_{1,1}^{1,1}\), and possibly \(a_{1,0}\) if \(v_{3} = a_{1,1}\), so that no vertex in \(H_{1}\) plays the role of \(u_{7}\). If \(v_{4}\) and \(v_{1}\) are old, the only neighbours of \(a_{1,1}\) are x, a, \(a_{1,1}^{1,1}\), and possibly \(a_{0,1}\) if \(v_{4} = a_{1,1}\), so that no vertex in \(H_{1}\) plays the role of \(u_{6}\). Moreover, as in (i), all of \(u_{1}\), \(u_{5}\), \(u_{4}\), \(u_{8}\) need to be added as unique, distinct second-level vertices in each of the above cases; when \(v_{1}\) and \(v_{3}\) are old or \(v_{1}\) and \(v_{4}\) are old, we also need to add \(u_{2}\) as a new vertex. Clearly, this forces \(\nu _{2} \ge 6\). If less than two first-level vertices are old, even more second-level vertices need to be added as unique, distinct second-level vertices.
When \(\nu _{1} \ge 3\): In this case, we need \(\nu _{2} \le 4\). We argue as above that \(u_{1}\), \(u_{5}\), \(u_{4}\), \(u_{8}\) all need to be added as unique, distinct second-level vertices. If \(v_{1}\) is old, then both \(u_{6}\) and \(u_{7}\) need to be added as distinct, unique second-level vertices; if \(v_{3}\) or \(v_{4}\) is old, we add both \(u_{3}\) and \(u_{4}\) as new second-level vertices. All these show that \(u \le 4\) is a condition that clearly cannot be met.
5.1.2 Second Subcase.
We consider \(b_{1,1} \in V(H^{\prime }_{0}) \setminus V(H_{0})\) and \(v_{2}\) old. By Lemma 5.3, the number of edges added due to all first-level vertices is \(2\nu _{1}+5\). Since each distinct unique second-level vertex brings at least two edges, \(\rho (H_{2})\) is at leastand for this to be strictly less than \(\frac{13}{7}\), we require \(\nu _{1}+\nu _{2} + 7e \lt 1\), implying \(\nu _{1} = \nu _{2} = e = 0\). From the proof of Lemma 5.3, we note that the number of edges contributed by all four old first-level vertices is precisely five only under one of the following situations.
\begin{equation} \frac{17 + 2 + (2 \nu _{1}+5) + 2\nu _{2} + e}{12 + 1 + \nu _{1} + \nu _{2}} = \frac{24 + 2(\nu _{1} + \nu _{2}) + e}{13 + (\nu _{1} + \nu _{2})}, \end{equation}
(5.9)
If \(v_{2} = a_{1,0}\) and \(v_{3} = b_{1,1}\), the edges due to first-level vertices are \(\lbrace b_{1,1}, a\rbrace\), \(\lbrace b_{1,1}, a_{1,0}\rbrace\), \(\lbrace a_{1,0}, b\rbrace\), \(\lbrace v_{1}, b_{0,1}\rbrace\), and \(\lbrace v_{4}, a_{0,1}\rbrace\) (if \(v_{1} \ne b_{1,1}\), then we must have \(v_{1} = a_{1,0}\)). Note that the only neighbours of \(b_{0,1}\) in \(H_{1}\) are b, \(b_{0,1}^{0,1}\), and \(v_{1}\), all of which are adjacent to b, so that no vertex in \(H_{1}\) plays the role of \(u_{1}\). Thus, we have to add \(u_{1}\) as a unique second-level vertex, thus violating the required condition \(\nu _{2} = 0\).
If \(v_{3} \ne b_{1,1}\), the edges due to first-level vertices are \(\lbrace v_{3}, a_{1,0}\rbrace\), \(\lbrace v_{2}, b\rbrace\), \(\lbrace v_{2}, b_{1,1}\rbrace\), \(\lbrace v_{1}, b_{0,1}\rbrace\), and \(\lbrace v_{4}, a_{0,1}\rbrace\) (if \(v_{1} \ne b_{1,1}\), then we must have \(v_{1} = v_{2}\)). Once again, \(u_{1}\) needs to be added as a unique second-level vertex, violating \(\nu _{2} = 0\).
5.1.3 Third Subcase.
When \(b_{1,1} \in V(H_{0})\), if each unique second-level vertex brings precisely two edges, \(\rho (H_{2})\) is at leastFor this to be strictly less than \(\frac{13}{7}\), we require \((\nu _{1}+\nu _{2}) + 7e \lt 2\), forcing \(e = 0\) and \(\nu _{1}+\nu _{2} \le 1\). The only neighbours of \(a_{0,1}\) in \(H_{1}\) are a, \(a_{0,1}^{0,1}\), and \(v_{4}\), and the only neighbours to \(b_{0,1}\) are b, \(b_{0,1}^{0,1}\), and \(v_{1}\), so that there exist no vertices playing the roles of \(u_{8}\) and \(u_{1}\). Since both \(u_{1}\) and \(u_{8}\) need to be added as unique second-level vertices, they must coincide, but by Lemma 5.4, the common vertex will bring three edges instead of precisely two.
\begin{equation} \frac{17 + 1 + (2 \nu _{1}+4) + 2\nu _{2} + e}{12 + \nu _{1} + \nu _{2}} = \frac{22 + 2(\nu _{1}+\nu _{2}) + e}{12 + (\nu _{1}+\nu _{2})}. \end{equation}
(5.10)
5.2 Showing that for \(\alpha \lt \frac{7}{13}\), Zero-One Law for \(\mathcal {E}_{4}\) Holds for \(\left\lbrace G(n, n^{-\alpha })\right\rbrace\)
For \(\alpha \lt \frac{7}{13}\), when \(G_{1} \stackrel{d}{=} G(m, m^{-\alpha })\) and \(G_{2} \stackrel{d}{=} G(n, n^{-\alpha })\) are independent, we show that a.a.s. Duplicator wins \(\operatorname{EHR}[G_{1}, G_{2}, 4]\). Let Spoiler play on \(G_{1}\) and Duplicator on \(G_{2}\) without loss of generality, and the vertices picked in \(G_{1}\) are denoted \(x_{i}\) and in \(G_{2}\) by \(y_{i}\), for \(i \in [4]\). A.a.s. as \(m, n \rightarrow \infty\), both \(G_{1}\) and \(G_{2}\) contain induced subgraphs isomorphic to \(G_{0}\), and Duplicator makes use of the copy of \(G_{0}\) present inside \(G_{2}\) in her winning strategy. Given our description of \(G_{0}\), it is clear, for the most part (in particular, for the first two rounds), how Duplicator responds to Spoiler while playing on the copy of \(G_{0}\) inside \(G_{2}\). We point out here some of the less obvious responses.
A.a.s. for every subgraph of \(G_{2}\) that is isomorphic to \(G_{0}\), and whose vertices are named the same as the corresponding vertices of \(G_{0}\), there exist the following vertices, edges, and non-edges in \(G_{2}\):
(i)
vertex c that is non-adjacent to x, a and \(a^{\prime }_{1,1}\) but adjacent to \(a_{1,1}\);
(ii)
vertex \(c^{1,0}\) that is adjacent to c and x but not to a;
(iii)
vertex \(c^{0,1}\) that is adjacent to c and a but not to x;
(iv)
vertex d that is non-adjacent to x, b, and \(b^{\prime }_{1,1}\) but adjacent to \(b_{1,1}\);
(v)
vertex \(d^{1,0}\) that is adjacent to d and x but not to b;
(vi)
vertex \(d^{0,1}\) that is adjacent to d and b but not to x.
Let H be the induced subgraph on \(x, a, a_{1,1}, a^{\prime }_{1,1}\) and G that on \(x, a, a_{1,1}, a^{\prime }_{1,1}, c, c^{1,0}, c^{0,1}\) in \(G_{2}\) such that \(E(G) \setminus E(H)\) comprises precisely the edges and non-edges described in the statement of Lemma 5.5. Consider \(H \subset S \subseteq G\) with \(c \in S\). It is straightforward to see that \(e(S, H)\) is at most \(\frac{5}{3}\) times \(v(S, H)\), and hence \(f_{\alpha }(S, H) \gt 0\) for \(\alpha \lt \frac{7}{13}\). The argument is similar for the vertices d, \(d^{1,0}\), and \(d^{0,1}\). From Theorem 2.5, the rest follows.□
Suppose Spoiler picks \(x_{3}\) that is non-adjacent to \(x_{1}\) and \(x_{2}\)—then Duplicator sets \(y_{3} = c\) if \(y_{2} = a\), and \(y_{3} = d\) otherwise (i.e., if \(y_{2} = b\)). If Spoiler selects \(x_{4}\) that is adjacent to \(x_{1}, x_{2}, x_{3}\), then Duplicator sets \(y_{4} = a_{1,1}\) if \(y_{2} = a\), and \(y_{4} = b_{1,1}\) otherwise. If Spoiler selects \(x_{4}\) that is adjacent to \(x_{1}\), \(x_{2}\) but not to \(x_{3}\), Duplicator sets \(y_{4} = a^{\prime }_{1,1}\) when \(y_{2} = a\) and \(y_{4} = b^{\prime }_{1,1}\) otherwise. If Spoiler selects \(x_{4}\) that is adjacent to \(x_{1}\), \(x_{3}\) but not to \(x_{2}\), then Duplicator sets \(y_{4} = c^{1,0}\) when \(y_{2} = a\) and \(y_{4} = d^{1,0}\) otherwise. If Spoiler selects \(x_{4}\) that is adjacent to \(x_{2}\), \(x_{3}\) but not to \(x_{1}\), then Duplicator sets \(y_{4} = c^{0,1}\) when \(y_{2} = a\) and \(y_{4} = d^{0,1}\) otherwise. Finally, no matter what \(x_{1}, x_{2}, x_{3}\) may have been, suppose Spoiler selects \(x_{4}\) that is adjacent to at most one of \(x_{1}, x_{2}, x_{3}\). If G is the subgraph of \(G_{1}\) induced on \(\lbrace x_{1}, x_{2}, x_{3}, x_{4}\rbrace\) and H that on \(\lbrace x_{1}, x_{2}, x_{3}\rbrace\), the pair \((G, H)\) is \(\alpha\)-safe for all \(\alpha \lt 1\)—-hence, by Theorem 2.5, Duplicator a.a.s. finds \(y_{4}\) in \(G_{2}\) such that \(y_{4} \sim y_{i}\) iff \(x_{4} \sim x_{i}\) for \(i \in [3]\).
6 Further Remarks
Historically, it has always been the case that after having investigated convergence laws and/or zero-one laws for a given logic, mathematicians have explored these laws for their existential fragment. We note here that although we focus on zero-one laws for the existential fragment of first-order logic, this is equivalent to studying zero-one laws for the universal fragment of first-order logic, since every universal first-order sentence is merely the negation of some existential first-order sentence. It will be interesting to consider other fragments of first-order logic, such as existential positive sentences and existential sentences in prenex form, and study the corresponding zero-one laws on \(\left\lbrace G(n,p(n))\right\rbrace _{n}\).
References
[1]
Maksim Zhukovskii. 2012. Zero-one k-law. Discrete Mathematics 312, 10 (2012), 1670–1688.
[2]
Noga Alon and Joel H. Spencer. 2004. The Probabilistic Method. John Wiley & Sons.
[3]
Joel H. Spencer. 1990. Counting extensions. Journal of Combinatorial Theory Series A, 55, 2 (1990), 247–255.
[4]
Saharon Shelah and Joel H. Spencer. 1988. Zero–one laws for sparse random graphs. Journal of the American Mathematical Society 1, 1 (1988), 97–115.
[5]
Joel Spencer. 2013. The Strange Logic of Random Graphs, Vol. 22, Springer Science & Business Media.
[6]
Joel Spencer. 1991. Threshold spectra via the Ehrenfeucht game. Discrete Applied Mathematics 30, 2–3 (1991), 235–252.
[7]
Béla Bollobás and John C. Wierman. 1989. Subgraph counts and containment probabilities of balanced and unbalanced subgraphs in a large random graph. Annals of the New York Academy of Sciences 576, 1 (1989), 63–70.
[8]
Béla Bollobás. 1981. Threshold functions for small subgraphs. Mathematical Proceedings of the Cambridge Philosophical Society 90, 2 (1981), 197–206, Cambridge University Press.
[9]
Béla Bollobás. 2001. Random Graphs, Vol. 73, Cambridge University Press.
[10]
Andrzej Ehrenfeucht. 1961. An application of games to the completeness problem for formalized theories. Fundamenta Mathematicae 49, 13 (1961), 129–141.
[11]
Leonid Libkin. 2013. Elements of Finite Model Theory, Springer Science & Business Media.
[12]
Neil Immerman. 2012. Descriptive Complexity, Springer Science & Business Media.
[13]
David Marker. 2006. Model Theory, Vol. 217, Springer Science & Business Media.
[14]
Svante Janson, Tomasz Luczak, and Andrzej Rucinski. 2011. Random Graphs, Vol. 45, John Wiley & Sons.
[15]
Matt Kaufmann. 1987. A counterexample to the \(0\text{--}1\) law for existential monadic second-order logic. CLI Internal Note 32, Computational Logic Inc.
[16]
Jean-Marie Le Bars. 2001. The 0–1 law fails for monadic existential second-order logic on undirected graphs. Information Processing Letters 77, 1 (2001), 43–48.
[17]
Monica McArthur. 1995. The asymptotic behavior of \(L_{\infty , \omega }^{k+2}\) on sparse random graphs. Logic and Random Structures 53–64.
[18]
A. S. Razafimahatratra and M. Zhukovskii. 2020. Zero–one laws for k-variable first-order logic of sparse random graphs. Discrete Applied Mathematics 276, 121–128.
[19]
Paul Erdős and Alfréd Rényi. 1960. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences 5, 1 (1960), 17–60.
[20]
Michał Karoński and Andrezj Ruciński. 1983. On the number of strictly balanced subgraphs of a random graph. Graph Theory. Springer, 79–83.
[21]
Michał Karoński and Andrezj Ruciński. 1997. The origins of the theory of random graphs. The Mathematics of Paul Erdős I. Springer, 311–336.
[22]
Andrzej Ruciński. 1988. When are small subgraphs of a random graph normally distributed? Probability Theory and Related Fields 78, 1 (1988), 1–10.
[23]
Andrzej Ruciński and Andrew Vince. 1986. Strongly balanced graphs and random graphs. Journal of Graph Theory 10, 2 (1986), 251–264.
[24]
Michał Karoński and Andrzej Ruciński. 1987. Poisson convergence and semi-induced properties of random graphs. Mathematical Proceedings of the Cambridge Philosophical Society 101, 2 (1987), 291–300, Cambridge University Press.
[25]
Andrew D. Barbour, Svante Janson, Michal Karoński, and Andrzej Ruciński. 1990. Small cliques in random graphs. Random Structures & Algorithms 1, 4 (1990), 403–434.
[26]
Y. V. Glebskii, D. I. Kogan, M. I. Liogon’kiI, and V. A. Talanov. 1969. Range and degree of realizability of formulas in the restricted predicate calculus. Cybernetics 5, 2 (1969), 142–154.
[27]
Ronald Fagin. 1976. Probabilities on finite models I. The Journal of Symbolic Logic 41, 1 (1976), 50–58.
[28]
Béla Bollobás and Arthur G. Thomason. 1987. Threshold functions. Combinatorica 7, 1 (1987), 35–38.
Index Terms
- Zero-One Laws for Existential First-Order Sentences of Bounded Quantifier Depth
Recommendations
Program schemes, arrays, Lindström quantifiers and zero-one laws
We characterize the class of problems accepted by a class of program schemes with arrays, NPSA, as the class of problems defined by the sentences of a logic formed by extending first-order logic with a particular uniform (or vectorized) sequence of ...
On the complexity of entailment in existential conjunctive first-order logic with atomic negation
We consider the entailment problem in the fragment of first-order logic (FOL) composed of existentially closed conjunctions of literals (without functions), denoted by FOL(@__ __,@__ __,@__ __"a). This problem can be recast as several fundamental ...
Succinctness of Order-Invariant Logics on Depth-Bounded Structures
We study the expressive power and succinctness of order-invariant sentences of first-order (FO) and monadic second-order (MSO) logic on structures of bounded tree-depth. Order-invariance is undecidable in general and, thus, one strives for logics with a ...
Comments
Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 January 2022
Accepted: 01 September 2021
Revised: 01 September 2021
Received: 01 November 2020
Published in TOCL Volume 23, Issue 2
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Funding Sources
- NSF
- Russian Science Foundation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 364Total Downloads
- Downloads (Last 12 months)201
- Downloads (Last 6 weeks)39
Reflects downloads up to 23 Oct 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatGet Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in