Forbidden subgraph problem

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph , find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph.[1]

An equivalent problem is how many edges in an -vertex graph guarantee that it has a subgraph isomorphic to ?[2]

Definitions

edit

The extremal number   is the maximum number of edges in an  -vertex graph containing no subgraph isomorphic to  .   is the complete graph on   vertices.   is the Turán graph: a complete  -partite graph on   vertices, with vertices distributed between parts as equally as possible. The chromatic number   of   is the minimum number of colors needed to color the vertices of   such that no two adjacent vertices have the same color.

Upper bounds

edit

Turán's theorem

edit

Turán's theorem states that for positive integers   satisfying  ,[3]  

This solves the forbidden subgraph problem for  . Equality cases for Turán's theorem come from the Turán graph  .

This result can be generalized to arbitrary graphs   by considering the chromatic number   of  . Note that   can be colored with   colors and thus has no subgraphs with chromatic number greater than  . In particular,   has no subgraphs isomorphic to  . This suggests that the general equality cases for the forbidden subgraph problem may be related to the equality cases for  . This intuition turns out to be correct, up to   error.

Erdős–Stone theorem

edit

Erdős–Stone theorem states that for all positive integers   and all graphs  ,[4]  

When   is not bipartite, this gives us a first-order approximation of  .

Bipartite graphs

edit

For bipartite graphs  , the Erdős–Stone theorem only tells us that  . 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   with  , there exists some constant   (independent of  ) such that   for every positive integer  .[5]

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

Theorem (Bondy and Simonovits, 1974). There exists some constant   such that   for every positive integer   and positive integer  .[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   be a bipartite graph with vertex parts   and   such that every vertex in   has degree at most  . Then there exists a constant   (dependent only on  ) such that  for every positive integer  .[7]

In general, we have the following conjecture.:

Rational Exponents Conjecture (Erdős and Simonovits). For any finite family   of graphs, if there is a bipartite  , then there exists a rational   such that  .[8]

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

Lower bounds

edit

There are various techniques used for obtaining the lower bounds.

Probabilistic method

edit

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   inside it. These copies can be removed by removing one edge from every copy of   in the graph, giving us a   free graph.

The probabilistic method can be used to prove  where   is a constant only depending on the graph  .[9] For the construction we can take the Erdős-Rényi random graph  , that is the graph with   vertices and the edge been any two vertices drawn with probability  , independently. After computing the expected number of copies of   in   by linearity of expectation, we remove one edge from each such copy of   and we are left with a  -free graph in the end. The expected number of edges remaining can be found to be   for a constant   depending on  . Therefore, at least one  -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  , is the length of the shortest cycle of the graph. Note that for  , the graph must forbid all the cycles with length less than equal to  . By linearity of expectation,the expected number of such forbidden cycles is equal to the sum of the expected number of cycles   (for  .). We again remove the edges from each copy of a forbidden graph and end up with a graph free of smaller cycles and  , giving us   edges in the graph left.

Algebraic constructions

edit

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  , 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[10] establishing the lower bound on   as , demonstrates the power of this method.

First, suppose that   for some prime  . Consider the polarity graph   with vertices elements of   and edges between vertices   and   if and only if   in  . This graph is  -free because a system of two linear equations in   cannot have more than one solution. A vertex   (assume  ) is connected to   for any  , for a total of at least   edges (subtracted 1 in case  ). So there are at least   edges, as desired. For general  , we can take   with   (which is possible because there exists a prime   in the interval  for sufficiently large  [11]) and construct a polarity graph using such  , then adding   isolated vertices, which do not affect the asymptotic value.

The following theorem is a similar result for  .

Theorem (Brown, 1966).  [12]
Proof outline.[13] Like in the previous theorem, we can take   for prime   and let the vertices of our graph be elements of  . This time, vertices   and   are connected if and only if   in  , for some specifically chosen  . Then this is  -free since at most two points lie in the intersection of three spheres. Then since the value of   is almost uniform across  , each point should have around   edges, so the total number of edges is  .

However, it remains an open question to tighten the lower bound for   for  .

Theorem (Alon et al., 1999) For  ,  [14]

Randomized Algebraic constructions

edit

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  , there exists some   such that  .

Proof outline: We take the largest prime power   with  . Due to the prime gaps, we have  . Let   be a random polynomial in   with degree at most   in   and   and satisfying  . Let the graph   have the vertex set   such that two vertices   are adjacent if  .

We fix a set  , and defining a set   as the elements of   not in   satisfying   for all elements  . By the Lang–Weil bound, we obtain that for   sufficiently large enough, we have   or   for some constant  .Now, we compute the expected number of   such that   has size greater than  , and remove a vertex from each such  . The resulting graph turns out to be   free, and at least one graph exists with the expectation of the number of edges of this resulting graph.

Supersaturation

edit

Supersaturation refers to a variant of the forbidden subgraph problem, where we consider when some  -uniform graph   contains many copies of some forbidden subgraph  . Intuitively, one would expect this to once   contains significantly more than   edges. We introduce Turán density to formalize this notion.

Turán density

edit

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

 

It is true that   is in fact positive and monotone decreasing, so the limit must therefore exist. [15]


As an example, Turán's Theorem gives that  , and the Erdős–Stone theorem gives that  . In particular, for bipartite  ,  . Determining the Turán density   is equivalent to determining   up to an   error.[16]

Supersaturation Theorem

edit

Consider an  -uniform hypergraph   with   vertices. The supersaturation theorem states that for every  , there exists a   such that if   is an  -uniform hypergraph on   vertices and at least   edges for   sufficiently large, then there are at least   copies of  . [17]

Equivalently, we can restate this theorem as the following: If a graph   with   vertices has   copies of  , then there are at most   edges in  .

Applications

edit

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   with  , there exists some constant   (independent of  ) such that   for every positive integer  .[18]
Proof. Let   be a  -graph on   vertices, and consider the number of copies of   in  . Given a vertex of degree  , we get exactly   copies of   rooted at this vertex, for a total of   copies. Here,   when  . By convexity, there are at total of at least   copies of  . Moreover, there are clearly   subsets of   vertices, so if there are more than   copies of  , then by the Pigeonhole Principle there must exist a subset of   vertices which form the set of leaves of at least   of these copies, forming a  . Therefore, there exists an occurrence of   as long as we have  . In other words, we have an occurrence if  , which simplifies to  , which is the statement of the theorem. [19]

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   of some forbidden subgraph   and showing that if it appears too many times in  , then   must appear in   as well. Other theorems regarding the forbidden subgraph problem which can be solved with supersaturation include:

  •  . [20]
  • For any   and  ,  . [20]
  • If   denotes the graph determined by the vertices and edges of a cube, and   denotes the graph obtained by joining two opposite vertices of the cube, then  . [19]

Generalizations

edit

The problem may be generalized for a set of forbidden subgraphs  : find the maximal number of edges in an  -vertex graph which does not have a subgraph isomorphic to any graph from  .[21]

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  -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  , and connect vertices   by a 3-edge if they are all in different  s, or if two of them are in   and the third is in   (where  ). This is tetrahedron-free, and the edge density is  . However, the best known upper bound is 0.562, using the technique of flag algebras.[22]

See also

edit

References

edit
  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" (PDF). 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), Colloq. Math., 3: 50–57, doi:10.4064/cm-3-1-50-57, MR 0065617
  6. ^ Bondy, J. A.; Simonovits, M. (April 1974). "Cycles of even length in graphs". Journal of Combinatorial Theory. Series B. 16 (2): 97–105. doi:10.1016/0095-8956(74)90052-5. 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. ^ a b 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. ^ 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, S2CID 8964027
  12. ^ Brown, W. G. (1966). "On graphs that do not contain a Thomsen graph". Canad. Math. Bull. 9 (3): 281–285. doi:10.4153/CMB-1966-036-2. MR 0200182.
  13. ^ Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). pp. 32–37. Retrieved 2 December 2019.
  14. ^ Alon, Noga; Rónyai, Lajos; Szabó, Tibor (1999). "Norm-graphs: variations and applications". Journal of Combinatorial Theory. Series B. 76 (2): 280–290. doi:10.1006/jctb.1999.1906. MR 1699238.
  15. ^ Erdős, Paul; Simonovits, Miklós. "Supersaturated Graphs and Hypergraphs" (PDF). p. 3. Retrieved 27 November 2021.
  16. ^ Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). pp. 16–17. Retrieved 2 December 2019.
  17. ^ Simonovits, Miklós. "Extremal Graph Problems, Degenerate Extremal Problems, and Supersaturated Graphs" (PDF). p. 17. Retrieved 25 November 2021.
  18. ^ Kővári, T.; T. Sós, V.; Turán, P. (1954), "On a problem of K. Zarankiewicz" (PDF), Colloq. Math., 3: 50–57, doi:10.4064/cm-3-1-50-57, MR 0065617
  19. ^ a b Simonovits, Miklós. "Extremal Graph Problems, Degenerate Extremal Problems, and Supersaturated Graphs" (PDF). Retrieved 27 November 2021.
  20. ^ a b Erdős, Paul; Simonovits, Miklós. "Compactness Results in Extremal Graph Theory" (PDF). Retrieved 27 November 2021.
  21. ^ Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels p. 590
  22. ^ Keevash, Peter. "Hypergraph Turán Problems" (PDF). Retrieved 2 December 2019.