Forbidden subgraph problem


In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph, find the maximal number of edges in an -vertex graph which does not have a subgraph isomorphic to. In this context, is called a forbidden subgraph.
An equivalent problem is how many edges in an -vertex graph guarantee that it has a subgraph isomorphic to ?

Definitions

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.

Results

Non-bipartite graphs

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.
When is not bipartite, this gives us a first-order approximation of.

Bipartite graphs

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:
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.
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:
In general, we have the following conjecture.:
A survey by Füredi and Simonovits describes progress on the forbidden subgraph problem in more detail.

Lower bounds

For any graph, we have the following lower bound:
For specific cases, improvements have been made by finding algebraic constructions.
However, it remains an open question to tighten the lower bound for for.

Generalizations

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.
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 . This is tetrahedron-free, and the edge density is. However, the best known upper bound is 0.562, using the technique of flag algebras.