Forbidden subgraph problem

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

{{See also|Turán's theorem}}

Turán's theorem states that for positive integers $n,r$ satisfying $n\backslash geq\; r\; \backslash geq\; 3$,{{Cite journal|last=Turán|first=Pál|date=1941|title=On an extremal problem in graph theory|journal=Matematikai és Fizikai Lapok|language=hu|volume=48|pages=436–452}} $\backslash operatorname\{ex\}(n,K\_r)=\backslash left(1-\backslash frac\{1\}\{r-1\}+o(1)\backslash right)\backslash frac\{n^2\}\{2\}.$

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

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

{{See also|Erdős–Stone theorem}}

Erdős–Stone theorem states that for all positive integers $n$ and all graphs $G$,{{Cite journal|last1=Erdős|first1=P.|author-link=Paul Erdős|last2=Stone, A. H.|author-link2=Arthur Stone (mathematician)|date=1946|title=On the structure of linear graphs|journal=Bulletin of the American Mathematical Society|volume=52|issue=12|pages=1087–1091|doi=10.1090/S0002-9904-1946-08715-7|doi-access=free|url=http://www.math-inst.hu/~p_erdos/1963-11.pdf}} $\backslash operatorname\{ex\}(n,G)=\backslash left(1-\backslash frac\{1\}\{\backslash chi(G)-1\}+o(1)\backslash right)\backslash binom\{n\}\{2\}.$

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

For bipartite graphs $G$, the Erdős–Stone theorem only tells us that $\backslash 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 $s,t$ with $t\backslash geq\; s\; \backslash geq\; 1$, there exists some constant $C$ (independent of $n$) such that $\backslash operatorname\{ex\}(n,K\_\{s,t\})\backslash le\; Cn^\{2-\backslash frac\{1\}\{s\}\}$ for every positive integer $n$.{{citation|last1=Kővári|first1=T.|title=On a problem of K. Zarankiewicz|url=http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3110.pdf|journal=Colloq. Math. |volume=3|pages=50–57|year=1954|mr=0065617|last2=T. Sós|first2=V.|last3=Turán|first3=P.|author2-link=Vera T. Sós|author3-link=Pál Turán|doi=10.4064/cm-3-1-50-57|doi-access=free}}

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

:Theorem (Bondy and Simonovits, 1974). There exists some constant $C$ such that $\backslash operatorname\{ex\}(n,C\_\{2k\})\backslash le\; Cn^\{1+\backslash frac\{1\}\{k\}\}$ for every positive integer $n$ and positive integer $k\backslash ge2$.{{Cite journal|last1=Bondy|first1=J. A.|author-link=John Adrian Bondy|last2=Simonovits|first2=M.|author-link2=Miklós Simonovits|title=Cycles of even length in graphs.|journal=Journal of Combinatorial Theory | series=Series B|volume=16|issue=2|date=April 1974|pages=97–105|doi=10.1016/0095-8956(74)90052-5|doi-access=free|mr=340095}}

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 $G$ be a bipartite graph with vertex parts $A$ and $B$ such that every vertex in $A$ has degree at most $r$. Then there exists a constant $C$ (dependent only on $G$) such that $\backslash operatorname\{ex\}(n,G)\backslash le\; Cn^\{2-\backslash frac\{1\}\{r\}\}$for every positive integer $n$.{{Cite journal|last1=Alon|first1=Noga|author-link=Noga Alon|last2=Krivelevich|first2=Michael|author-link2=Michael Krivelevich|last3=Sudakov|first3=Benny|author-link3=Benny Sudakov|title=Turán numbers of bipartite graphs and related Ramsey-type questions|journal=Combinatorics, Probability and Computing|mr=2037065}}

In general, we have the following conjecture.:

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

A survey by Füredi and Simonovits describes progress on the forbidden subgraph problem in more detail.{{Cite arXiv|last1=Füredi|first1=Zoltán|last2=Simonovits|first2=Miklós|date=2013-06-21|title=The history of degenerate (bipartite) extremal graph problems|eprint=1306.5167|class=math.CO}}

There are various techniques used for obtaining the lower bounds.

While this method mostly gives weak bounds, the theory of random graphs is a rapidly developing subject. It is based on the idea that if we take a graph randomly with a sufficiently small density, the graph would contain only a small number of subgraphs of $G$ inside it. These copies can be removed by removing one edge from every copy of $G$ in the graph, giving us a $G$ free graph.

The probabilistic method can be used to prove $\backslash operatorname\{ex\}(n,G)\backslash ge\; cn^\{2-\backslash frac\{v(G)-2\}\{e(G)-1\}\}$where $c$ is a constant only depending on the graph $G$.{{cite web|last=Zhao|first=Yufei|title=Graph Theory and Additive Combinatorics|url=http://yufeizhao.com/gtac/fa17/gtac.pdf|access-date=2 December 2019|pages=32{{ndash}}37}} For the construction we can take the Erdős-Rényi random graph $G(n,p)$, that is the graph with $n$ vertices and the edge been any two vertices drawn with probability $p$, independently. After computing the expected number of copies of $G$ in $G(n,p)$ by linearity of expectation, we remove one edge from each such copy of $G$ and we are left with a $G$-free graph in the end. The expected number of edges remaining can be found to be $\backslash operatorname\{ex\}(n,G)\backslash ge\; cn^\{2-\backslash frac\{v(G)-2\}\{e(G)-1\}\}$ for a constant $c$ depending on $G$. Therefore, at least one $n$-vertex graph exists with at least as many edges as the expected number.

This method can also be used to find the constructions of a graph for bounds on the girth of the graph. The girth, denoted by $g(G)$, is the length of the shortest cycle of the graph. Note that for $g(G)>2\; k$, the graph must forbid all the cycles with length less than equal to $2k$. By linearity of expectation,the expected number of such forbidden cycles is equal to the sum of the expected number of cycles $C\_i$ (for $i=3,...,n-1,n$.). We again remove the edges from each copy of a forbidden graph and end up with a graph free of smaller cycles and $g(G)>2k$, giving us $c\_0\; n^\{1+\; \backslash frac\{1\}\{2k-1\}\}$ edges in the graph left.

For specific cases, improvements have been made by finding algebraic constructions. A common feature for such constructions is that it involves the use of geometry to construct a graph, with vertices representing geometric objects and edges according to the algebraic relations between the vertices. We end up with no subgraph of $G$, purely due to purely geometric reasons, while the graph has a large number of edges to be a strong bound due to way the incidences were defined. The following proof by Erdős, Rényi, and Sős{{Cite journal|last1=Erdős|first1=P.|last2=Rényi|first2=A.|last3=Sós|first3=V. T.|date=1966|title=On a problem of graph theory|journal=Studia Sci. Math. Hungar. 1|pages=215{{ndash}}235|mr=223262}} establishing the lower bound on $\backslash operatorname\{ex\}(n,K\_\{2,2\})$ as$\backslash left(\backslash frac\{1\}\{2\}-o(1)\backslash right)n^\{3/2\}.$, demonstrates the power of this method.

First, suppose that $n=p^2-1$ for some prime $p$. Consider the polarity graph $G$ with vertices elements of $\backslash mathbb\{F\}\_p^2-\backslash \{0,0\backslash \}$ and edges between vertices $(x,y)$ and $(a,b)$ if and only if $ax+by=1$ in $\backslash mathbb\{F\}\_p$. This graph is $K\_\{2,2\}$-free because a system of two linear equations in $\backslash mathbb\{F\}\_p$ cannot have more than one solution. A vertex $(a,b)$ (assume $b\backslash neq\; 0$) is connected to $\backslash left(x,\backslash frac\{1-ax\}\{b\}\backslash right)$ for any $x\backslash in\; \backslash mathbb\{F\}\_p$, for a total of at least $p-1$ edges (subtracted 1 in case $(a,b)=\backslash left(x,\backslash frac\{1-ax\}\{b\}\backslash right)$). So there are at least $\backslash frac\{1\}\{2\}(p^2-1)(p-1)=\backslash left(\backslash frac\{1\}\{2\}-o(1)\backslash right)p^3=\backslash left(\backslash frac\{1\}\{2\}-o(1)\backslash right)n^\{3/2\}$ edges, as desired. For general $n$, we can take $p=(1-o(1))\backslash sqrt\{n\}$ with $p\backslash le\; \backslash sqrt\{n+1\}$ (which is possible because there exists a prime $p$ in the interval$[k-k^\{0.525\},k]$ for sufficiently large $k${{citation|last1=Baker|first1=R. C.|title=The difference between consecutive primes. II.|journal=Proc. London Math. Soc.|volume=83|issue=3|pages=532–562|year=2001|series=Series 3|doi=10.1112/plms/83.3.532|mr=1851081|last2=Harman|first2=G.|last3=Pintz|first3=J.|s2cid=8964027 }}) and construct a polarity graph using such $p$, then adding $n-p^2+1$ isolated vertices, which do not affect the asymptotic value.

The following theorem is a similar result for $K\_\{3,3\}$.

:Theorem (Brown, 1966). $\backslash operatorname\{ex\}(n,K\_\{3,3\})\backslash ge\; \backslash left(\backslash frac\{1\}\{2\}-o(1)\backslash right)n^\{5/3\}.${{Cite journal|last1=Brown|first1=W. G.|date=1966|pages=281{{ndash}}285|title=On graphs that do not contain a Thomsen graph|journal=Canad. Math. Bull. | volume=9 |issue=3| doi=10.4153/CMB-1966-036-2 | doi-access=free |mr=200182}}

:Proof outline.{{cite web |url=http://yufeizhao.com/gtac/fa17/gtac.pdf |title=Graph Theory and Additive Combinatorics|last=Zhao |first=Yufei |pages=32{{ndash}}37|access-date=2 December 2019}} Like in the previous theorem, we can take $n=p^3$ for prime $p$ and let the vertices of our graph be elements of $\backslash mathbb\{F\}\_p^3$. This time, vertices $(a,b,c)$ and $(x,y,z)$ are connected if and only if $(x-a)^2+(y-b)^2+(z-c)^2=u$ in $\backslash mathbb\{F\}\_p$, for some specifically chosen $u$. Then this is $K\_\{3,3\}$-free since at most two points lie in the intersection of three spheres. Then since the value of $(x-a)^2+(y-b)^2+(z-c)^2$ is almost uniform across $\backslash mathbb\{F\}\_p$, each point should have around $p^2$ edges, so the total number of edges is $\backslash left(\backslash frac\{1\}\{2\}-o(1)\backslash right)p^2\backslash cdot\; p^3=\backslash left(\backslash frac\{1\}\{2\}-o(1)\backslash right)n^\{5/3\}$.

However, it remains an open question to tighten the lower bound for $\backslash operatorname\{ex\}(n,K\_\{t,t\})$ for $t\backslash ge\; 4$.

:Theorem (Alon et al., 1999) For $t\backslash ge\; (s-1)!+1$, $\backslash operatorname\{ex\}(n,K\_\{s,t\})=\; \backslash Theta(n^\{2-\backslash frac\{1\}\{s\}\}).${{Cite journal|last1=Alon|first1=Noga|last2=Rónyai|first2=Lajos|last3=Szabó|first3=Tibor|date=1999|pages=280{{ndash}}290|title=Norm-graphs: variations and applications|journal=Journal of Combinatorial Theory | series=Series B |volume=76|issue=2|mr=1699238|doi=10.1006/jctb.1999.1906|doi-access=free}}

This technique combines the above two ideas. It uses random polynomial type relations when defining the incidences between vertices, which are in some algebraic set. Using this technique to prove the following theorem.

Theorem: For every $s\backslash geq\; 2$, there exists some $t$ such that $\backslash operatorname\{ex\}(n,K\_\{s,t\})\; \backslash geq\; \backslash left(\; \backslash frac\{1\}\{2\}\; -\; o(1)\; \backslash right)\; n^\{2-\backslash frac\{1\}\{s\}\}$.

Proof outline: We take the largest prime power $q$ with $q^s\; \backslash leq\; n$. Due to the prime gaps, we have $q=(1-o(1))n^\{\backslash frac\{1\}\{s\}\}$. Let $f\; \backslash in\; \backslash mathbb\{F\}\_q[x\_1,x\_2,\backslash cdots,x\_s,y\_1,y\_2,\backslash cdots,\; y\_s]\_\{\backslash le\; d\}$ be a random polynomial in $\backslash mathbb\{F\}\_q$ with degree at most $d=s^2$ in $X=(X\_1,X\_2,...,X\_s)$ and $Y=(Y\_1,Y\_2,...,Y\_s)$ and satisfying $f(X,Y)=f(Y,X)$. Let the graph $G$ have the vertex set $\backslash mathbb\{F\}\_q^s$ such that two vertices $x,y$ are adjacent if $f(x,y)=0$.

We fix a set $U\; \backslash subset\; \backslash mathbb\{F\}\_q^s$, and defining a set $Z\_U$ as the elements of $\backslash mathbb\{F\}\_q^s$ not in $U$ satisfying $f(x,u)=0$ for all elements $u\; \backslash in\; U$. By the Lang–Weil bound, we obtain that for $q$ sufficiently large enough, we have $|Z\_U|\backslash leq\; C$ or $|Z\_U|>\backslash frac\{q\}\{2\}$ for some constant $C$.Now, we compute the expected number of $U$ such that $Z\_U$ has size greater than $C$, and remove a vertex from each such $U$. The resulting graph turns out to be $K\_\{s,C+1\}$ free, and at least one graph exists with the expectation of the number of edges of this resulting graph.

Supersaturation refers to a variant of the forbidden subgraph problem, where we consider when some $h$-uniform graph $G$ contains many copies of some forbidden subgraph $H$. Intuitively, one would expect this to once $G$ contains significantly more than $\backslash operatorname\{ex\}(n,H)$ edges. We introduce Turán density to formalize this notion.

The Turán density of a $h$-uniform graph $G$ is defined to be

: $\backslash pi(G)\; =\; \backslash lim\_\{n\; \backslash to\; \backslash infty\}\; \backslash frac\{\backslash operatorname\{ex\}(n,G)\}\{\backslash binom\{n\}\{h\}\}.$

It is true that $\backslash frac\{\backslash operatorname\{ex\}(n,G)\}\{\backslash binom\{n\}\{h\}\}$ is in fact positive and monotone decreasing, so the limit must therefore exist. {{cite web |url=https://old.renyi.hu/~miki/ErdSimSupersatCCA.pdf |title=Supersaturated Graphs and Hypergraphs|last1=Erdős|first1=Paul|last2=Simonovits|first2=Miklós|pages=3|access-date=27 November 2021}}

As an example, Turán's Theorem gives that $\backslash pi(K\_\{r+1\})\; =\; 1\; -\; \backslash frac\{1\}\{r\}$, and the Erdős–Stone theorem gives that $\backslash pi(G)\; =\; 1\; -\; \backslash frac\{1\}\{\backslash chi(H)-1\}$. In particular, for bipartite $G$, $\backslash pi(G)\; =\; 0$. Determining the Turán density $\backslash pi(H)$ is equivalent to determining $\backslash operatorname\{ex\}(n,G)$ up to an $o(n^2)$ error.{{cite web |url=http://yufeizhao.com/gtac/fa17/gtac.pdf |title=Graph Theory and Additive Combinatorics|last=Zhao |first=Yufei |pages=16{{ndash}}17|access-date=2 December 2019}}

Consider an $h$-uniform hypergraph $H$ with $v(H)$ vertices. The supersaturation theorem states that for every $\backslash epsilon\; >\; 0$, there exists a $\backslash delta\; >\; 0$ such that if $G$ is an $h$-uniform hypergraph on $n$ vertices and at least $(\backslash pi(H)\; +\; \backslash epsilon)\; \backslash binom\{n\}\{h\}$ edges for $n$ sufficiently large, then there are at least $\backslash delta\; n^\{v(H)\}$ copies of $H$. {{cite web |url=https://users.renyi.hu/~miki/waterloo.pdf |title=Extremal Graph Problems, Degenerate Extremal Problems, and Supersaturated Graphs|last=Simonovits |first=Miklós|pages=17|access-date=25 November 2021}}

Equivalently, we can restate this theorem as the following: If a graph $G$ with $n$ vertices has $o(n^\{v(H)\})$ copies of $H$, then there are at most $\backslash pi(H)\; \backslash binom\{n\}\{2\}\; +\; o(n^2)$ edges in $G$.

We may solve various forbidden subgraph problems by considering supersaturation-type problems. We restate and give a proof sketch of the Kővári–Sós–Turán theorem below:

:Kővári–Sós–Turán theorem. For every pair of positive integers $s,t$ with $t\backslash geq\; s\; \backslash geq\; 1$, there exists some constant $C$ (independent of $n$) such that $\backslash operatorname\{ex\}(n,K\_\{s,t\})\backslash le\; Cn^\{2-\backslash frac\{1\}\{s\}\}$ for every positive integer $n$.{{citation|last1=Kővári|first1=T.|title=On a problem of K. Zarankiewicz|url=http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3110.pdf|journal=Colloq. Math. |volume=3|pages=50–57|year=1954|mr=0065617|last2=T. Sós|first2=V.|last3=Turán|first3=P.|author2-link=Vera T. Sós|author3-link=Pál Turán|doi=10.4064/cm-3-1-50-57|doi-access=free}}

:Proof. Let $G$ be a $2$-graph on $n$ vertices, and consider the number of copies of $K\_\{1,s\}$ in $G$. Given a vertex of degree $d$, we get exactly $\backslash binom\{d\}\{s\}$ copies of $K\_\{1,s\}$ rooted at this vertex, for a total of $\backslash sum\_\{v\; \backslash in\; V(G)\}\; \backslash binom\{\backslash operatorname\{deg\}(v)\}\{s\}$ copies. Here, $\backslash binom\{k\}\{s\}\; =\; 0$ when . By convexity, there are at total of at least $n\; \backslash binom\{2e(G)/n\}\{s\}$ copies of $K\_\{1,s\}$. Moreover, there are clearly $\backslash binom\{n\}\{s\}$ subsets of $s$ vertices, so if there are more than $(t-1)\; \backslash binom\{n\}\{s\}$ copies of $K\_\{1,s\}$, then by the Pigeonhole Principle there must exist a subset of $s$ vertices which form the set of leaves of at least $t$ of these copies, forming a $K\_\{s,t\}$. Therefore, there exists an occurrence of $K\_\{s,t\}$ as long as we have $n\; \backslash binom\{2e(G)/n\}\{s\}\; >\; (t-1)\; \backslash binom\{n\}\{s\}$. In other words, we have an occurrence if $\backslash frac\{e(G)^s\}\{n^\{s-1\}\}\; \backslash ge\; O(n^s)$, which simplifies to $e(G)\; \backslash ge\; O(n^\{2\; -\; \backslash frac\{1\}\{s\}\})$, which is the statement of the theorem. {{cite web |url=https://users.renyi.hu/~miki/waterloo.pdf|title=Extremal Graph Problems, Degenerate Extremal Problems, and Supersaturated Graphs|last=Simonovits|first=Miklós|access-date=27 November 2021}}

In this proof, we are using the supersaturation method by considering the number of occurrences of a smaller subgraph. Typically, applications of the supersaturation method do not use the supersaturation theorem. Instead, the structure often involves finding a subgraph $H\text{'}$ of some forbidden subgraph $H$ and showing that if it appears too many times in $G$, then $H$ must appear in $G$ as well. Other theorems regarding the forbidden subgraph problem which can be solved with supersaturation include:

{{bulleted list

|$\backslash operatorname\{ex\}(n,\; C\_\{2t\})\; \backslash le\; O(n^\{1\; +\; 1/t\})$. {{cite web |url=https://users.renyi.hu/~miki/CompactnessCCA.pdf|title=Compactness Results in Extremal Graph Theory|last1=Erdős|first1=Paul|last2=Simonovits|first2=Miklós|access-date=27 November 2021}}

|For any $t$ and $k\; \backslash ge\; 2$, $\backslash operatorname\{ex\}(n,\; C\_\{2k\},\; C\_\{2k-1\})\; \backslash le\; O\; \backslash left(\; \backslash left(\; \backslash frac\{n\}\{2\}\; \backslash right)^\{1\; +\; 1/t\}\; \backslash right)$.

|If $Q$ denotes the graph determined by the vertices and edges of a cube, and $Q^*$ denotes the graph obtained by joining two opposite vertices of the cube, then $\backslash operatorname\{ex\}(n,\; Q)\; \backslash le\; \backslash operatorname\{ex\}(n,\; Q^*)\; =\; O(n^\{8/5\})$. }}

The problem may be generalized for a set of forbidden subgraphs $S$: find the maximal number of edges in an $n$-vertex graph which does not have a subgraph isomorphic to any graph from $S$.Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels [https://books.google.com/books?id=C3tJsmWRQvkC&pg=PA590&dq=%22turan+number%22#PPA590,M1 p. 590]

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 $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 $V\_1,\; V\_2,\; V\_3$, and connect vertices $x,y,z$ by a 3-edge if they are all in different $V\_i$s, or if two of them are in $V\_i$ and the third is in $V\_\{i+1\}$ (where $V\_4=V\_1$). This is tetrahedron-free, and the edge density is $5/9$. However, the best known upper bound is 0.562, using the technique of flag algebras.{{cite web |url=http://people.maths.ox.ac.uk/keevash/papers/turan-survey.pdf|title=Hypergraph Turán Problems|last=Keevash |first=Peter|access-date=2 December 2019}}

• Biclique-free graph
• Erdős–Hajnal conjecture
• Turán number
• Subgraph isomorphism problem
• Forbidden graph characterization

{{reflist}}

Category:Extremal graph theory