Forbidden subgraph problem

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph ${\displaystyle G}$, find the maximal number of edges ${\displaystyle \operatorname {ex} (n,G)}$ in an ${\displaystyle n}$-vertex graph which does not have a subgraph isomorphic to ${\displaystyle G}$. In this context, ${\displaystyle G}$ is called a forbidden subgraph.[1]

An equivalent problem is how many edges in an ${\displaystyle n}$-vertex graph guarantee that it has a subgraph isomorphic to ${\displaystyle G}$?[2]

Definitions

The extremal number ${\displaystyle \operatorname {ex} (n,G)}$ is the maximum number of edges in an ${\displaystyle n}$-vertex graph containing no subgraph isomorphic to ${\displaystyle G}$. ${\displaystyle K_{r}}$ is the complete graph on ${\displaystyle r}$ vertices. ${\displaystyle T(n,r)}$ is the Turán graph: a complete ${\displaystyle r}$-partite graph on ${\displaystyle n}$ vertices, with vertices distributed between parts as equally as possible. The chromatic number ${\displaystyle \chi (G)}$ of ${\displaystyle G}$ is the minimum number of colors needed to color the vertices of ${\displaystyle G}$ such that no two adjacent vertices have the same color.

Results

Non-bipartite graphs

'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)}$.

Bipartite graphs

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 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]

Lower bounds

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]

Generalizations

The problem may be generalized for a set of forbidden subgraphs ${\displaystyle S}$: find the maximal number of edges in an ${\displaystyle n}$-vertex graph which does not have a subgraph isomorphic to any graph from ${\displaystyle S}$.[16]

There are also hypergraph versions of forbidden subgraph problems that are much more difficult. For instance, Turán's problem may be generalized to asking for the largest number of edges in an ${\displaystyle n}$-vertex 3-uniform hypergraph that contains no tetrahedra. The analog of the Turán construction would be to partition the vertices into almost equal subsets ${\displaystyle V_{1},V_{2},V_{3}}$, and connect vertices ${\displaystyle x,y,z}$ by a 3-edge if they are all in different ${\displaystyle V_{i}}$s, or if two of them are in ${\displaystyle V_{i}}$ and the third is in ${\displaystyle V_{i+1}}$ (where ${\displaystyle V_{4}=V_{1}}$). This is tetrahedron-free, and the edge density is ${\displaystyle 5/9}$. However, the best known upper bound is 0.562, using the technique of flag algebras.[17]

See also

• Biclique-free graph
• Erdős–Hajnal conjecture
• Turán's theorem
• Turán number
• Subgraph isomorphism problem
• Forbidden graph characterization
• Erdős-Stone theorem
• Zarankiewicz problem
• Extremal graph theory

References

1. Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics, Béla Bollobás, 1986, ISBN 0-521-33703-8, p. 53, 54
2. "Modern Graph Theory", by Béla Bollobás, 1998, ISBN 0-387-98488-7, p. 103
3. Turán, Pál (1941). "On an extremal problem in graph theory". Matematikai és Fizikai Lapok (in Hungarian). 48: 436–452.
4. Erdős, P.; Stone, A. H. (1946). "On the structure of linear graphs". Bulletin of the American Mathematical Society. 52 (12): 1087–1091. doi:10.1090/S0002-9904-1946-08715-7.
5. Kővári, T.; T. Sós, V.; Turán, P. (1954), "On a problem of K. Zarankiewicz" (PDF), Colloquium Math., 3: 50–57, doi:10.4064/cm-3-1-50-57, MR 0065617
6. Bondy, J. A.; Simonovits, M. "Cycles of even length in graphs". Journal of Combinatorial Theory. Series B. MR 0340095.
7. Alon, Noga; Krivelevich, Michael; Sudakov, Benny. "Turán numbers of bipartite graphs and related Ramsey-type questions". Combinatorics, Probability and Computing. MR 2037065.
8. Füredi, Zoltán; Simonovits, Miklós (2013-06-21). "The history of degenerate (bipartite) extremal graph problems". arXiv:1306.5167 [math.CO].
9. Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). pp. 32–37. Retrieved 2 December 2019.
10. Erdős, P.; Rényi, A.; Sós, V. T. (1966). "On a problem of graph theory". Studia Sci. Math. Hungar. 1: 215–235. MR 0223262.
11. Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). pp. 32–37. Retrieved 2 December 2019.
12. Baker, R. C.; Harman, G.; Pintz, J. (2001), "The difference between consecutive primes. II.", Proc. London Math. Soc., Series 3, 83 (3): 532–562, doi:10.1112/plms/83.3.532, MR 1851081
13. Brown, W. G. (1966). "On graphs that do not contain a Thomsen graph". Canad. Math. Bull. 9: 281–285. MR 0200182.
14. Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). pp. 32–37. Retrieved 2 December 2019.
15. Alon, Noga; Rónyai, Lajos; Szabó, Tibor (1999). "Norm-graphs: variations and applications". J. Combin. Theory Ser. B. 76 (2): 280–290. doi:10.1006/jctb.1999.1906. MR 1699238.
16. Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels p. 590
17. Keevash, Peter. "Hypergraph Turán Problems" (PDF). Retrieved 2 December 2019.