Theorem 4.6.1. Erdős and Simonovits [101].
\(\ex(n,Q_3)=O(n^{8/5})\text{.}\)
Section 4.6 A Brief Return to Bipartite Extremal Numbers
In Section 3.4, we obtained an upper bound on the extremal numbers of bipartite graphs and, in Section 3.5, we discussed a theorem of Bondy and Simonovits (Theorem 3.5.1) which gives a better bound for even cycles. The problem of estimating extremal numbers of bipartite graphs is very difficult in general. In this section, we combine Theorem 3.5.1 with a slight modification of Theorem 4.2.7 to prove the following theorem of Erdős and Simonovits [101] on the extremal number of the \(3\)-dimensional cube graph. Recall that, for \(d\geq 1\text{,}\) the \(d\)-dimensional hypercube , denoted \(Q_d\text{,}\) is the graph with vertex set \(\{0,1\}^d\) where two vertices are adjacent if they differ in a unique coordinate. By Corollary 3.4.2, we know that \(\ex(n,Q_3)=O(n^{7/4})\text{.}\) The following theorem reduces the exponent by a wee bit.
Most of the tools that we need to prove this have already been developed in earlier sections. The last thing that we need is the following lemma which allows us to restrict our attention to graphs which are “almost regular.”
Lemma 4.6.2. Erdős and Simonovits [101].
Let \(0<\delta\leq 1\) and \(C>0\) and suppose that \(\varepsilon<\frac{\delta}{4-\delta}\) and \(n\geq \max\left\{C^{-2/\delta},2^{\frac{4-\delta}{\delta-(4-\delta)\varepsilon}}, 2^{\frac{1}{\varepsilon}+\frac{16}{\delta\varepsilon}}\right\}\text{.}\) If \(G\) is a graph with \(n\) vertices and at least \(Cn^{1+\delta}\) edges, then \(G\) contains a subgraph \(G'\) such that
- \(|V(G')|\geq n^{\varepsilon}\text{,}\)
- \(G'\) has at least \((C/2)|V(G')|^{1+\delta}\) edges and
- every vertex of \(G'\) has degree at most \(2^{5+\frac{16}{\delta}}|E(G')|/|V(G')|\text{.}\)
Proof.
Define \(p=2^{4+\frac{16}{\delta}}\) and, for all \(i\geq0\text{,}\) let \(n_i=(16/p)^in\) and \(e_i=C(1/p)^i n^{1+\delta}\text{.}\) We construct graphs \(G_0,G_1,\dots, G_t\) iteratively in such a way that, for all \(i\geq0\text{,}\)
- \(G_{i+1}\) is a subgraph of \(G_{i}\text{,}\)
- \(G_i\) has at most \(n_i\) vertices and
- \(G_i\) has at least \(e_i\) edges.
We start by initiating \(G_0=G\) and note that the statements in the second and third bullet points above hold in the case \(i=0\) by the hypotheses of the lemma.
For \(i\geq 0\text{,}\) suppose that the graph \(G_i\) has already been constructed. Our goal in this step of the algorithm is to either produce a subgraph \(G'\) of \(G_i\) with the properties described in the lemma statement, or a subgraph \(G_{i+1}\) of \(G_i\) with at most \(m_{i+1}\) vertices and at least \(e_{i+1}\) edges. Before describing the procedure for doing this, we take a detour to prove a lower bound on \(n_i\text{.}\) Of course, we must have
\begin{equation*}
e_i\leq |E(G_i)|\leq |V(G_i)|^2\leq n_i^2.
\end{equation*}
Plugging in the values for \(e_i\) and \(n_i\) yields
\begin{equation*}
C(1/p)^i n^{1+\delta}\leq (16/p)^{2i}n^{2}.
\end{equation*}
After a bit of rearranging, we get
\begin{equation*}
(p/256)^i \leq n^{1-\delta}/C\leq n^{1-\delta/2}
\end{equation*}
where the last inequality uses that \(n\geq C^{-2/\delta}\text{.}\) Note that
\begin{equation*}
\frac{p}{256} = 2^{-4+\frac{16}{\delta}} = 2^{\left(\frac{4-\delta}{4}\right)\left(\frac{16}{\delta}\right)} = (p/16)^{\frac{4-\delta}{4}}.
\end{equation*}
Combining this with the previous inequality yields
\begin{equation*}
(p/16)^i \leq n^{\frac{2-\delta}{2}\cdot \frac{4}{4-\delta}} =n^{1-\frac{\delta}{4-\delta}}
\end{equation*}
and so
\begin{equation*}
n_i = (16/p)^i n \geq n^{\frac{\delta}{4-\delta}} = n^{\frac{\delta}{4-\delta} - \varepsilon} n^\varepsilon \geq 2 n^{\varepsilon}
\end{equation*}
where the last inequality uses the lower bound on \(n\) in the hypotheses of the lemma.
Let \(q=\lceil p/4\rceil\) and let \(V_0,\dots,V_{q-1}\) be a partition of \(V(G_i)\) into sets of cardinality \(\lfloor n_i/q\rfloor\) or \(\lceil n_i/q\rceil\) such that \(V_0\) contains the \(\lfloor n_i/q\rfloor\) vertices of highest degree. We divide into cases.
Case 1: At least half of the edges of \(G_i\) are incident to a vertex in \(V_0\text{.}\)
In this case, choose \(1\leq i\leq q-1\) so that the number of edges from \(V_0\) to \(V_i\) is maximized. We let \(G_{i+1}\) be the subgraph of \(G_i\) obtained by deleting all vertices except for those in \(V_0\cup V_i\text{.}\) By pigeonhole and the fact that at least half of the edges of \(G_i\) are incident to a vertex in \(V_0\text{,}\) the number of edges in \(G_{i+1}\) is at least
\begin{equation*}
e_i/2q\geq e_i/p=e_{i+1}.
\end{equation*}
Also, the number of vertices of \(G_{i+1}\) is at most
\begin{equation*}
2\lceil n_i/q\rceil \leq 2\lceil 4n_i/p\rceil\leq 2(4n_i/p) + 2 \leq (16/p)n_i =n_{i+1}
\end{equation*}
where the last inequality uses the bound \(n_i\geq 2 n^{\varepsilon}\) established earlier and the lower bound on \(n\) from the hypotheses of the lemma. Thus, \(G_{i+1}\) has the desired properties.
Case 2: At most half of the edges of \(G_i\) are incident to a vertex in \(V_0\text{.}\)
In this case, let \(G'\) be the subgraph of \(G_i\) obtained by deleting the vertices of \(V_0\text{.}\) Then
\begin{equation*}
|V(G')| \geq n_i - |V_0| \geq n_i\left(1-\frac{1}{q}\right) \geq 2 n^{\varepsilon}\left(1-\frac{4}{p}\right) > n^{\varepsilon}.
\end{equation*}
Also, by definition of \(p\text{,}\) we have \(1/p\geq (16/p)^{1+\delta}\) and so
\begin{equation*}
|E(G')| \geq |E(G_i)|/2\geq e_i/2 = (C/2)(1/p)^i n^{1+\delta} \geq (C/2)(16/p)^{i(1+\delta)} n^{1+\delta} =(C/2)n_i^{1+\delta} \geq (C/2)|V(G')|^{1+\delta}.
\end{equation*}
Finally, suppose that \(G'\) has a vertex of degree greater than \(2p|E(G')|/|V(G')|\text{.}\) By definition of \(V_0\text{,}\) this means that all of the vertices of \(V_0\) have degree greater than \(2p|E(G')|/|V(G')|\) in \(G_i\text{.}\) Thus, by handshaking,
\begin{equation*}
2|E(G_i)|\geq \left(|V_0|+1\right)2p|E(G')|/|V(G')| \geq \left(n_i/q\right)2p|E(G')|/n_i = (2p/q)|E(G')|> 4|E(G')|.
\end{equation*}
However, this contradicts the assumption that at most half of the edges of \(G_i\) are incident to a vertex in \(V_0\text{.}\) Therefore, \(G'\) has the desired properties and the proof is complete.
We will also need the following variation of Theorem 4.2.7.
Lemma 4.6.3.
For every graph \(G\) with \(n\) vertices and at least \(n^{3/2}\) edges, the number of injective homomorphisms from \(C_4\) to \(G\) is at least \(|E(G)|^4/n^4\text{.}\)
Proof.
Let \(Q_3^+\) be the graph obtained from \(Q_3\) by adding an edge between vertices \((0,0,0)\) and \((1,1,1)\text{.}\) We will actually obtain the following stronger theorem.
Theorem 4.6.4. Erdős and Simonovits [101].
\(\ex(n,Q_3^+)=O(n^{8/5})\text{.}\)
Proof.
Using Theorem 3.5.1, we let \(a\) be a constant so that \(\ex(n,C_6)\leq an^{4/3}\) for all \(n\text{;}\) note that we may assume that \(a\geq1\text{.}\)
Let \(n\geq 2^{300}\) and let \(G\) be a graph with \(n\) vertices and at least \(a^{3/5}2^{28} n^{8/5}\) edges. Our goal is to show that \(G\) contains a copy of \(Q_3^+\text{.}\) By Lemma 3.5.3, we can let \(G'\) be a bipartite subgraph of \(G\) with \(n\) vertices and at least \(a^{3/5}2^{27}n^{8/5}\) edges.
Next, define \(C=a^{3/5}2^{27}\text{,}\) \(\delta=3/5\) and \(\varepsilon=1/10\text{.}\) Note that \(\varepsilon<\frac{\delta}{4-\delta}\text{.}\) Also, \(\max\{C^{-2/\delta},2^{\frac{4-\delta}{\delta-(4-\delta)\varepsilon}},2^{\frac{1}{\varepsilon}+\frac{16}{\delta\varepsilon}}\}= 2^{830/3}\leq n\text{.}\) Therefore, \(G'\) satisfies the hypotheses of Lemma 4.6.2 and so we can take \(G''\) to be a subgraph of \(G'\) with at least \(n^{1/10}\) vertices and at least \(a^{3/5}2^{26}|V(G'')|^{8/5}\) edges in which every vertex has degree at most \(2^{95/3}|E(G'')|/|V(G'')|\text{.}\) For the sake of simplicity, let \(N:=|V(G'')|\) and \(M=|E(G'')|\text{.}\) Define \(b=M/N^{8/5}\text{.}\) Note that \(b\geq a^{3/5}2^{26}\) and that every vertex has degree at most \(2^{95/3}b N^{3/5}\text{.}\)
By Lemma 4.6.3, there are at least \(M^4/N^4\) injective homomorphisms from \(C_4\) to \(G''\text{.}\) Therefore, there must exist an edge \(uv\) which is contained in at least \(8M^3/N^4\) such homomorphisms. Let \(A=N(u)\setminus\{v\}\) and \(B=N(v)\setminus\{u\}\) and note that, since \(G''\) is bipartite, these sets are disjoint. Let \(G'''\) be the subgraph of \(G''\) induced by \(A\cup B\text{.}\) Note that every edge \(A\) to \(B\) corresponds to \(8\) injective homomorphisms from \(C_4\) to \(G''\) which use the edge \(uv\text{.}\) Thus, \(G'''\) has at least \(M^3/N^4\) edges. Also, the number of vertices of \(G'''\) is less than the sum of the degrees of \(u\) and \(v\text{,}\) which is at most \(2^{98/3}b N^{3/5}\text{.}\) We claim that \(G'''\) contains a copy of \(C_6\) due to having more than the extremal number of edges. To see this, we have
\begin{equation*}
a\left(2^{98/3}b N^{3/5}\right)^{4/3} = a2^{380/9}b^{4/3}N^{4/5}\leq a2^{130/3}b^{4/3}N^{4/5} \leq b^3N^{4/5}=\frac{\left(bN^{8/5}\right)^3}{N^4} = \frac{M^3}{N^4}.
\end{equation*}
Thus, \(G'''\) contains a \(C_6\text{.}\) Putting this cycle together with the vertices \(u\) and \(v\) gives us a copy of \(Q_3^+\text{.}\) Thus, the proof is complete.
Here is a YouTube video related to the Turán number of the cube:
