Forbidden subgraph problem

'Turán's theorem'. For positive integers ${\displaystyle n,r}$ satisfying ${\displaystyle n\geq r\geq 3}$,[3] ${\textstyle \operatorname {ex} (n,K_{r})=\left(1-{\frac {1}{r-1}}\right){\frac {n^{2}}{2}}.}$

This solves the forbidden subgraph problem for ${\displaystyle G=K_{r}}$. Equality cases for Turán's theorem come from the Turán graph ${\displaystyle T(n,r-1)}$.

This result can be generalized to arbitrary graphs ${\displaystyle G}$ by considering the chromatic number ${\displaystyle \chi (G)}$ of ${\displaystyle G}$. Note that ${\displaystyle T(n,r)}$ can be colored with ${\displaystyle r}$ colors and thus has no subgraphs with chromatic number greater than ${\displaystyle r}$. In particular, ${\displaystyle T(n,\chi (G)-1)}$ has no subgraphs isomorphic to ${\displaystyle G}$. This suggests that the general equality cases for the forbidden subgraph problem may be related to the equality cases for ${\displaystyle G=K_{r}}$. This intuition turns out to be correct, up to ${\displaystyle o(n^{2})}$ error.

'Erdős–Stone theorem'. For all positive integers ${\displaystyle n}$ and all graphs ${\displaystyle G}$,[4]${\textstyle \operatorname {ex} (n,G)=\left(1-{\frac {1}{\chi (G)-1}}+o(1)\right){\frac {n^{2}}{2}}.}$

When ${\displaystyle G}$ is not bipartite, this gives us a first-order approximation of ${\displaystyle \operatorname {ex} (n,G)}$.

For bipartite graphs ${\displaystyle G}$, the Erdős–Stone theorem only tells us that ${\displaystyle \operatorname {ex} (n,G)=o(n^{2})}$. The forbidden subgraph problem for bipartite graphs is known as the Zarankiewicz problem, and it is unsolved in general.

Progress on the Zarankiewicz problem includes following theorem:

Kővári–Sós–Turán theorem. For every pair of positive integers ${\displaystyle s,t}$ with ${\displaystyle t\geq s\geq 1}$, there exists some constant ${\displaystyle C}$ (independent of ${\displaystyle n}$) such that ${\textstyle \operatorname {ex} (n,K_{s,t})\leq Cn^{2-{\frac {1}{s}}}}$ for every positive integer ${\displaystyle n}$.[5]

Another result for bipartite graphs is the case of even cycles, ${\displaystyle G=C_{2k},k\geq 2}$. Even cycles are handled by considering a root vertex and paths branching out from this vertex. If two paths of the same length ${\displaystyle k}$ have the same endpoint and do not overlap, then they create a cycle of length ${\displaystyle 2k}$. This gives the following theorem.

Theorem (Bondy and Simonovits, 1974). There exists some constant ${\displaystyle C}$ such that ${\textstyle \operatorname {ex} (n,C_{2k})\leq Cn^{1+{\frac {1}{k}}}}$ for every positive integer ${\displaystyle n}$ and positive integer ${\displaystyle k\geq 2}$.[6]

A powerful lemma in extremal graph theory is dependent random choice. This lemma allows us to handle bipartite graphs with bounded degree in one part:

Theorem (Alon, Krivelevich, and Sudakov, 2003). Let ${\displaystyle G}$ be a bipartite graph with vertex parts ${\displaystyle A}$ and ${\displaystyle B}$ such that every vertex in ${\displaystyle A}$ has degree at most ${\displaystyle r}$. Then there exists a constant ${\displaystyle C}$ (dependent only on ${\displaystyle G}$) such that ${\textstyle \operatorname {ex} (n,G)\leq Cn^{2-{\frac {1}{r}}}}$for every positive integer ${\displaystyle n}$.[7]

In general, we have the following conjecture.:

Rational Exponents Conjecture (Erdős and Simonovits). For any finite family ${\displaystyle {\mathcal {L}}}$ of graphs, if there is a bipartite ${\displaystyle L\in {\mathcal {L}}}$, then there exists a rational ${\displaystyle \alpha \in [0,1)}$ such that ${\displaystyle \operatorname {ex} (n,{\mathcal {L}})=\Theta (n^{1+\alpha })}$.[8]

A survey by Füredi and Simonovits describes progress on the forbidden subgraph problem in more detail.[8]

For any graph ${\displaystyle G}$, we have the following lower bound:

Proposition. ${\displaystyle \operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}}$ for some constant ${\displaystyle c}$.[9]

Proof. We use a technique of the probabilistic method, the "method of alterations". Consider an Erdős–Rényi random graph ${\displaystyle G(n,p)}$, that is, a graph with ${\displaystyle n}$ vertices and between any two vertices, an edge is drawn with probability ${\displaystyle p}$, independently. We can find the expected number of copies of ${\displaystyle G}$ in ${\displaystyle G(n,p)}$ by linearity of expectation. Then removing one edge from each such copy of ${\displaystyle G}$, we are left with a ${\displaystyle G}$-free graph. The expected number of edges remaining can be found to be ${\displaystyle \operatorname {ex} (n,G)\geq cn^{2-{\frac {v(G)-2}{e(G)-1}}}}$ for some constant ${\displaystyle c}$. Therefore, at least one ${\displaystyle n}$-vertex graph exists with at least as many edges as the expected number.

For specific cases, improvements have been made by finding algebraic constructions.

Theorem (Erdős, Rényi, and Sős, 1966). ${\displaystyle \operatorname {ex} (n,K_{2,2})\geq \left({\frac {1}{2}}-o(1)\right)n^{3/2}.}$[10]

Proof.[11] First, suppose that ${\displaystyle n=p^{2}-1}$ for some prime ${\displaystyle p}$. Consider the polarity graph ${\displaystyle G}$ with vertices elements of ${\displaystyle \mathbb {F} _{p}^{2}-\{0,0\}}$ and edges between vertices ${\displaystyle (x,y)}$ and ${\displaystyle (a,b)}$ if and only if ${\displaystyle ax+by=1}$ in ${\displaystyle \mathbb {F} _{p}}$. This graph is ${\displaystyle K_{2,2}}$-free because a system of two linear equations in ${\displaystyle \mathbb {F} _{p}}$ cannot have more than one solution. A vertex ${\displaystyle (a,b)}$ (assume ${\displaystyle b\neq 0}$) is connected to ${\displaystyle \left(x,{\frac {1-ax}{b}}\right)}$ for any ${\displaystyle x\in \mathbb {F} _{p}}$, for a total of at least ${\displaystyle p-1}$ edges (subtracted 1 in case ${\displaystyle (a,b)=\left(x,{\frac {1-ax}{b}}\right)}$). So there are at least ${\displaystyle {\frac {1}{2}}(p^{2}-1)(p-1)=\left({\frac {1}{2}}-o(1)\right)p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{3/2}}$ edges, as desired. For general ${\displaystyle n}$, we can take ${\displaystyle p=(1-o(1)){\sqrt {n}}}$ with ${\displaystyle p\leq {\sqrt {n+1}}}$ (which is possible because there exists a prime ${\displaystyle p}$ in the interval${\displaystyle [k-k^{0.525},k]}$ for sufficiently large ${\displaystyle k}$[12]) and construct a polarity graph using such ${\displaystyle p}$, then adding ${\displaystyle n-p^{2}+1}$ isolated vertices, which do not affect the asymptotic value.

Theorem (Brown, 1966). ${\displaystyle \operatorname {ex} (n,K_{3,3})\geq \left({\frac {1}{2}}-o(1)\right)n^{5/3}.}$[13]

Proof outline.[14] Like in the previous theorem, we can take ${\displaystyle n=p^{3}}$ for prime ${\displaystyle p}$ and let the vertices of our graph be elements of ${\displaystyle \mathbb {F} _{p}^{3}}$. This time, vertices ${\displaystyle (a,b,c)}$ and ${\displaystyle (x,y,z)}$ are connected if and only if ${\displaystyle (x-a)^{2}+(y-b)^{2}+(z-c)^{2}=u}$ in ${\displaystyle \mathbb {F} _{p}}$, for some specifically chosen ${\displaystyle u}$. Then this is ${\displaystyle K_{3,3}}$-free since at most two points lie in the intersection of three spheres. Then since the value of ${\displaystyle (x-a)^{2}+(y-b)^{2}+(z-c)^{2}}$ is almost uniform across ${\displaystyle \mathbb {F} _{p}}$, each point should have around ${\displaystyle p^{2}}$ edges, so the total number of edges is ${\displaystyle \left({\frac {1}{2}}-o(1)\right)p^{2}\cdot p^{3}=\left({\frac {1}{2}}-o(1)\right)n^{5/3}}$.

However, it remains an open question to tighten the lower bound for ${\displaystyle \operatorname {ex} (n,K_{t,t})}$ for ${\displaystyle t\geq 4}$.

Theorem (Alon et al., 1999) For ${\displaystyle t\geq (s-1)!+1}$, ${\displaystyle \operatorname {ex} (n,K_{s,t})=\Theta (n^{2-{\frac {1}{s}}}).}$[15]