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\));
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 include
\[\exists x [\forall y [\lnot x \sim y]],\]
which expresses the property of a graph that it contains an isolated vertex, and
\[\exists x [\exists y [[x \sim y] \wedge \forall z [x \sim z \Rightarrow z = y]]],\]
which 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.
Neither of the examples above is an existential first-order sentence; an example of such a sentence would be
\[\exists x [\exists y \exists z [[x \sim y] \wedge [x \sim z] \wedge [\lnot y = z]]],\]
which 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.
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\).
In [4], the following well-known theorem was established.
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.
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, if
\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)
then \(\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\).
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.
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\).
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]).
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\).
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)\).
Setting \(v(G, H) = |V(G) \setminus V(H)|\) and \(e(G, H) = |E(G) \setminus E(H)|\), for \(\alpha \gt 0\), we define
We 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\).
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
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.
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.
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))\).
From Theorem 2.9 and [14], Section 3.3, we conclude that
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.
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})\).
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.
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.
So far, we see that
(i)
in the paragraphs following the statement of Theorem 3.1, we establish the claim of Theorem 3.1 when the number b of unique second-level vertices whose corresponding first-level vertices are also unique satisfies the condition \(b \geqslant \tfrac{k^{4}}{4}\);
(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 have
where \(\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 write
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 some
\begin{equation} \alpha = \left(k - 2 - t(k)\right)^{-1}, \text{ with a suitable } t(k) = \Theta (k^{-2}). \end{equation}
(4.1)
Assume 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.
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]\).
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 ubrings e edges if there are exactly e edges between u and the vertices in S that appear beforeu in the above order.
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
(i)
\(a_{k-3} \sim a_{i}\) iff \(x_{k-3} \sim x_{i}\) for all \(i \in [k-4]\) and
(ii)
G contains the edges and non-edges as described in (i)–(viii).
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]\).
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.
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 sentence
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 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}\);
In 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.
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.
Fig. 4. The graph \(H_0\).
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 to
in 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:
(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.
Remark 5.2.
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 in
in 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:
(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\).
Lemma 5.3.
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\).
Proof.
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.□
Lemma 5.4.
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.
Proof.
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 least
For 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:
(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 least
and 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.
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 least
For 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.
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.
Lemma 5.5.
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.
Proof.
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}\).
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.
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.
Andrzej Ehrenfeucht. 1961. An application of games to the completeness problem for formalized theories. Fundamenta Mathematicae 49, 13 (1961), 129–141.
Matt Kaufmann. 1987. A counterexample to the \(0\text{--}1\) law for existential monadic second-order logic. CLI Internal Note 32, Computational Logic Inc.
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.
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.
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.
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.
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.
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.
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 ...
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 ...
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 ...
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].
Moscow Institute of Physics and Technology, Laboratory of AdvancedCombinatorics and Network Applications, Russian Federation and Adyghe State University, Caucasus Mathematical Center, ul. Pervomayskaya, Russian Federation and The Russian Presidential Academy of National Economy and Public Administration, Prospect Vernadskogo, Moscow, Russian Federation