Turán's theorem states that for positive integers
colors and thus has no subgraphs with chromatic number greater than
This suggests that the general equality cases for the forbidden subgraph problem may be related to the equality cases for
Progress on the Zarankiewicz problem includes following theorem: Another result for bipartite graphs is the case of even cycles,
have the same endpoint and do not overlap, then they create a cycle of length
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.
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
by linearity of expectation, we remove one edge from each such copy of
The expected number of edges remaining can be found to be
-vertex graph exists with at least as many edges as the expected number.
, the graph must forbid all the cycles with length less than equal to
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.
, 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
However, it remains an open question to tighten the lower bound for
It uses random polynomial type relations when defining the incidences between vertices, which are in some algebraic set.
Proof outline: We take the largest prime power
Supersaturation refers to a variant of the forbidden subgraph problem, where we consider when some
We introduce Turán density to formalize this notion.
is in fact positive and monotone decreasing, so the limit must therefore exist.
We restate and give a proof sketch of the Kővári–Sós–Turán theorem below: In this proof, we are using the supersaturation method by considering the number of occurrences of a smaller subgraph.
Other theorems regarding the forbidden subgraph problem which can be solved with supersaturation include: The problem may be generalized for a set of forbidden subgraphs
[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
The analog of the Turán construction would be to partition the vertices into almost equal subsets
However, the best known upper bound is 0.562, using the technique of flag algebras.