The history of degenerate (bipartite) extremal graph problems
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
and
Abstract
This paper is a survey on Extremal Graph Theory, primarily focusing on the case when one of the excluded graphs is bipartite. On one hand we give an introduction to this field and also describe many important results, methods, problems, and constructions. ^{1}^{1}1 Research supported in part by the Hungarian National Science Foundation OTKA 104343, and by the European Research Council Advanced Investigators Grant 267195 (ZF) and by the Hungarian National Science Foundation OTKA 101536, and by the European Research Council Advanced Investigators Grant 321104. (MS).
Contents
 1 Introduction
 2 The general theory, classification

3 Excluding complete bipartite graphs
 3.1 Bipartite free graphs and the Zarankiewicz problem
 3.2 Finite Geometries and the free graphs
 3.3 Excluding : Exact results
 3.4 Excluding ,
 3.5 Excluding , and improving the upper bound
 3.6 Further applications of Algebraic Methods
 3.7 The coefficient in the KőváriT. SósTurán bound
 3.8 Excluding large complete subgraphs

4 Excluding Cycles :
 4.1 Girth and Turán numbers, upper bounds
 4.2 Excluding a single , upper bounds
 4.3 Eliminating short cycles, a promising attempt
 4.4 A lower bound for : The Benson Construction
 4.5 Girth 12 graphs by Benson and by Wenger
 4.6 Short cycles, and
 4.7 Bipartite hosts with extreme sides
 4.8 The effect of odd cycles
 4.9 Large girth: Ramanujan graphs
 4.10 The girth problem: the LazebnikUstimenko approach
 4.11 Cycle length distribution
 5 Paths and long cycles
 6 Excluding trees
 7 More complex excluded subgraphs
 8 Eigenvalues and extremal problems
 9 Excluding topological subdivisions
 10 Hypergraph Extremal Problems
 11 Supersaturated graphs
 12 Ordered structures
 13 Applications in Geometry
 14 Further connections and problems
 15 Acknowledgements
1 Introduction
This survey describes the theory of Degenerate Extremal Graph Problems, the main results of the field, and its connection to the surrounding areas.
Extremal graph problems we consider here are often called Turán type extremal problems, because Turán’s theorem and his questions were the most important roots of this huge area [244], [245].
Generally, we have a Universe of graphs, , where this universe may be the family of ordinary graphs, or digraphs, or hypergraphs, or ordered graphs, or bipartite graphs, etc and a property , saying, e.g., that does not contain some subgraphs , or that it is Hamiltonian, or it is at most 3chromatic, and we have some parameters on , say and , the number of vertices and edges. Our aim is to maximize the second parameter under the condition that has property and its first parameter is given.
We call such a problem Turán type extremal problem if we are given a family of graphs from our universe, is a graph of vertices, denotes the number of edges of and we try to maximize under the condition that contains no , where “contains” means “not necessarily induced subgraph”. (Here graph may equally mean digraph, or multigraph, or hypergraph).
The maximum will be denoted by and the graphs attaining this maximum without containing subgraphs from are called extremal graphs. The family of extremal graphs is denoted by and is called the Turán number of the family .
Speaking of we shall always assume that , otherwise the problem is trivial.
Definition 1.1.
If the Universe is the family of uniform hypergraphs^{2}^{2}2 included, moreover, mostly we think of ., then we shall call the problem degenerate if the maximum,
Otherwise we shall call it nondegenerate
Below we shall mention several open problems. Yet to get more problems, we refer the reader to the
Erdős homepage: www.renyi.hu/~p_erdos
where the papers of Erdős can be found [61]. Also, many open problems can be found in ChungGraham [49].
1.1 Some central theorems of the field
We start with some typical theorems of the field and two conjectures. The aim of this “fast introduction” is to give a feeling for what are the crucial types of results here.
Theorem 1.2 (Kővári–T. Sós–Turán, [166]).
Let denote the complete bipartite graph with and vertices in its colorclasses. Then
We use this theorem with , since that way we get a better estimate.
Theorem 1.4 (Erdős, Bondy and Simonovits [34]).
Theorem 1.5 (Erdős–Simonovits, Cube Theorem [92]).
Let denote the cube graph defined by the vertices and edges of a 3dimensional cube. Then
Conjecture 1.6 (Erdős and Simonovits, Rational exponents).
For any finite family of graphs, if there is a bipartite , then there exists a rational and a such that
Conjecture 1.8 (Erdős).
^{3}^{3}3This conjecture is mentioned in [72] but it is definitely older, see e.g. Brown, [39] .We close this part with a famous result of Ruzsa and Szemerédi:
Theorem 1.9 (Solution of the (6,3) problem, [212]).
If is a 3uniform hypergraph not containing 6 vertices determining (at least) 3 hyperedges, then this hypergraph has hyperedges.
The above theorems will be discussed in more details below.
1.2 The structure of this paper
The area is fairly involved. Figure 1 shows a complicated – but not complete – map of the interactions of some subfields of the field discussed here. We start with describing the Extremal problems in general, then move to the Degenerate problems, also describing why they are important. Among the most important degenerate extremal problems we mention are the extremal problem of , and also , where – to classify the extremal problems – we shall need the Random Graph Method to get a lower bound in the problem of . These results are enough to give a good classification of degenerate extremal graph problems.

The origins of this field are

an early, singular result of Mantel,

the multiplicative Sidon Problem (see Section 1.5)

Turán’s theorem and his systematic approach to the field.
So the origins come – in some sense – from Number Theory, are strongly connected to Finite Geometry, and in this way also to ordinary geometry (Turán’s theorem comes from the ErdősSzekeres version of Ramsey Theorem, which they invented to solve the Esther Klein problem from Geometry.)


To understand the field we start with a very short description of the general theory, and then – skipping most of the hypergraph theory – we move to the main area of this paper: to the questions where we consider ordinary extremal graphs, and exclude some bipartite : therefore, by Theorem 1.2, we have .

One important phenomenon is that many extremal graph problems can be “reduced” to some degenerate extremal graph problems that we also call sometimes bipartite extremal problems.

The upper bounds in the simpler cases are obtained by some double counting, Jensen type inequalities, or applying some supersaturated graph theorems.^{4}^{4}4Lovász and Szegedy had a beautiful conjecture, which we formulate here only in a restricted form: Any (valid) extremal theorem can be proven by applying the Cauchy–Schwarz inequality finitely many times. This conjecture was killed in this strong form – by Hatami and Norine [144] – but proven in a weaker, “approximationform”.

There are also much more complicated cases, where the above simple approach is not enough, we need some finer arguments. Perhaps the first such case was treated by Füredi: Section 7.3 and [109]. Also such an approach is the application of the general Dependent Random Choice Method, (see the survey of Fox and Sudakov [103]).

The lower bounds are sometimes provided by random graphs (see Section 2.5) but these are often too weak. So we often use some finite geometric constructions, (see Section 3.2) or their generalizations – coming from commutative algebras (see Sections 3.6, 4.9, 8), etc., and they occasionally provide matching upper and lower bounds. Again, there is an important general method with many important results, which we shall call the LazebnikUstimenko method but will treat only very superficially in Section 3.6.
1.3 Extremal problems
We shall almost entirely restrict ourselves to Turán type extremal problems for ordinary simple graphs, i.e. loops, multiple edges are excluded.
To show the relation of the areas described here, we start with a list of some related areas.

Ramsey Theory

Problems not connected to density problems; in some sense these are the real Ramsey Problems

Problems connected to density problems, i.e. cases, where we do not really use the Ramsey Condition, only that some color class is large.


Ordinary extremal graph theory

Excluding bipartite graphs (degenerate problems)

Excluding topological subgraphs (very degenerate extremal problems)

Matrix problems, ordered and not ordered;

Nondegenerate case, and its relation to degenerate problems


Theory of extremal digraph problems

RamseyTurán Problems

Connection to Random Graphs

Hypergraph extremal problems

Connection of Number Theoretical problems to Extremal Graph Theory

Continuous problems

Applications
There are several surveys on these fields, see e.g., T. Sós [234], Füredi [110], [112], Simonovits [226], [230], [229], [224], Simonovits and Sós [232], [157]. Perhaps the first survey on this topic was Vera Sós’ paper [234], discussing connections between extremal graph problems, finite geometries, block designs, etc. and, perhaps, the nearest to this survey is [227], Bollobás, [30] Sidorenko [219], [103], and also some books, e.g., Bollobás [28]. Of course, a lot of information is hidden in the papers of Erdős, among others, in [72], [75], [78].
So, here we shall concentrate on Case 2, but to position this area we shall start with some related fields, among others, with the general asymptotic in Case 2.
Problem 1.10 (General Hostgraphs).
In a more general setting we have a sequence of “host” graphs and the question is, how many edges can a subgraph have under the condition that it does not contain any forbidden subgraph . The maximum will be denoted by .
For we get back the ordinary extremal graph problems. There are several further important subcases of this question:
(a) when for ;
(b) when the hostgraph is the dimensional cube, ; see Section 14.3.
(c) when is a random graph on vertices, see e.g. [211].
Notation. Given some graphs , , , ,... the (first) subscript will almost always denote the number of vertices.^{5}^{5}5One important exception is the complete bipartite graph , see below. Another exception is, when we list some excluded subgraphs, like . So is the complete graph on vertices, the path on vertices, is the cycle of vertices, while will denote the family of cycles of length at least . denotes the degree of the vertex .
The complete bipartite graph with vertices in its first class and in its 2nd class will be crucial in this paper. Often, we shall denote it by , and its partite generalization by . If and , then is the Turán graph on vertices and classes.
Given two graphs and , their product graph is the one obtained from vertexdisjoint copies of these two graphs by joining each vertex of to each vertex of . This will be denoted by .^{6}^{6}6This product is often called also the joint of the two graphs.
Given a graph , is its number of vertices, its number of edges and its chromatic number, and denote the minimum and maximum degrees of , respectively.
We shall write if Occasionally denote the set of first integers, .
The Overlap. Some twenty years ago Simonovits wrote a survey [229] on the influence of Paul Erdős in the areas described above, Manymany features of these areas changed drastically since that. Jarik Nešetřil and Ron Graham were the editors of that surveyvolume, and now they decided to republish it. Fortunately, the authors had the option to slightly rewrite their original papers. Simonovits has rewritten his original paper [230], basically keeping everything he could but indicating many new developments, and adding remarks and many new references to it.
To make this paper readable and selfcontained, we shall touch on some basic areas also treated there, or in other survey papers of ours, Here, however, we shall explain manymany results and phenomena just mentioned in other survey papers.
Remark 1.11.
There is also a third new survey to be mentioned here: Simonovits gave a lecture at the conference on Turán’s anniversary, in 2011. His lecture tried to cover the whole influence of Paul Turán in Discrete Mathematics. In the volume of this conference Simonovits wrote a survey [231] covering his lecture, except that the area called Statistical Group Theory is discussed in a survey of Pálfy and Szalay [202] and some parts of the applications of Extremal Graph Theory, primarily in Probability Theory are covered by Katona [155], in the same volume.
1.4 Other types of extremal graph problems
Above we still tried to maximize the number of edges, hyperedges, etc. More generally, instead of maximizing , we may maximize something else:

Mindegree problems (or Dirac type problems): How large mindegree can have without containing subgraphs from .

Median problems which will be called here LoeblKomlósSós type problems: Given a graph , which and ensure that if has at least vertices of degree , then contains some .

Eigenvalueextremal problems ^{7}^{7}7As usual, given a graph , an matrix is associated to it, having eigenvalues. The largest and the second largest is what we are mostly interested in.: maximize the maximum eigenvalue under the condition that does not contain any . (These are sharper forms of some extremal results, since the maximum eigenvalue
see Section 8.)

Subgraph count inequalities, which assert that if contains many copies of some subgraphs , then we have at least one (or maybe “many”) subgraphs .

Combined extremal problems: There are many–many further types of extremal problems. Here we mention, as an example, the results of Balister, Bollobás, Riordan and Schelp [19], where an odd cycle is excluded, and at the same time an upper bound is fixed on the degrees and the number of edges are to be maximized.
The approach 4 is very popular in the theory of Graph Limits [179]. We mention a breakthrough in this area in connection with Erdős’ combinatorial problems, of type 4. A famous conjecture of Erdős was
Conjecture 1.12 (Erdős [76]).
A free contains at most copies of ’s.
The motivation of this is that the blownup^{8}^{8}8Given a graph , its blownup version is defined as follows: we replace each vertex of by independent new vertices and we join two new vertices coming from distinct vertices iff was an edge of . , i.e. has no triangles and has copies of . Erdős conjectured that no trianglefree can have more ’s than this. The first “approximation” was due to Ervin Győri:
Theorem 1.13 (Győri [135]).
A free contains at most ’s.
1.5 Historical remarks
Erdős in 1938 [62] considered the following ‘‘multiplicative Sidon Problem’’^{9}^{9}9For a longer description of the number theoretical parts see [230]. Erdős also refers to his “blindness” overlooking the general problem in [72]..
Problem 1.14.
How many integers, can we find so that does not hold for any , unless .
To get an upper bound in Problem 1.14, Erdős proved
Theorem 1.15.
Let be a bipartite graph with vertices in both classes. If it does not contain , then ,
Much later this problem was asked in a more general setting: find an upper bound on if . Zarankiewicz [256] posed the following question:
Problem 1.16 (Zarankiewicz problem).
Determine the largest integer for which there is an 01 matrix containing ’s without an submatrix consisting entirely of ’s.
Hartman, Mycielski and RyllNardzevski [141] gave upper and lower bounds for the case , weaker than the ErdősKlein^{10}^{10}10In [72] Erdős (again) attributes the finite geometric construction to Eszter (Esther) Klein. result, and Kővári, T. Sós and Turán (see Theorem 1.2) provided a more general upper bound. We shall discuss these problems and results in details in Sections 2.4 and 3.2.
While exact values of are known for infinitely many parameter values, mostly only asymptotic bounds are known in the general case. Even is not sufficiently well known.
2 The general theory, classification
In many ordinary extremal problems the minimum chromatic number plays a decisive role. The subchromatic number of is defined by
(2.1) 
Recall that the Turán graph is the largest graph on vertices and classes.
Claim 2.1.
(2.2) 
Indeed, does not contain any . An easy consequence of the ErdősStone theorem [97] provides the asymptotic value of , at least if .
Theorem 2.2 (ErdősSimonovits [91]).
If is a family of graphs with subchromatic number , then
This means that depends only very loosely on ; up to an error term of order ; it is already determined by . ^{11}^{11}11Better error terms are proved e.g. in [220], however, this will not be discussed here. The question is whether the structure of the extremal graphs is also almost determined by , and (therefore) it must be very similar to that of ^{12}^{12}12Actually, this was the original question; Theorem 2.2 was a partial answer to it.. The answer is YES. This is expressed by the following results of Erdős and Simonovits [68], [69], [220]:
Theorem 2.3 (The Asymptotic Structure Theorem).
Let be a family of forbidden graphs with subchromatic number . If , (i.e, is extremal for , then it can be obtained from by deleting and adding edges. Furthermore, if is finite, then the minimum degree
Further, the almostextremal graphs are similar to .
Theorem 2.4 (The First Stability Theorem).
Let be a family of forbidden graphs with subchromatic number . For every , there exist a and an such that, if contains no , and if, for ,
(2.3) 
then can be obtained from by changing^{13}^{13}13deleting and adding at most edges.
Remark 2.5.
For ordinary graphs () we often call the degenerate extremal graph problems bipartite extremal problems. This is the case when contains some bipartite graphs. There is a slight problem here: we shall also consider the case when not only some is bipartite but is as well.
2.1 The importance of the Degenerate Case
There are several results showing that if we know sufficiently well the extremal graphs for the degenerate cases, then we can also reduce the nondegenerate cases to these problems.
Exact Turán numbers, product conjecture
We start with an illustration. Let be the octahedron graph. Erdős and Simonovits proved that
Theorem 2.6 (Octahedron Theorem [93]).
If is an extremal graph for the octahedron for sufficiently large, then there exist extremal graphs and for the circuit and the path such that and , .
If does not contain and does not contain , then does not contain . Thus, if we replace by any in and by any in , then is also extremal for .
More generally,
Theorem 2.7 (Erdős–Simonovits [93]).
Let be a complete partite graph, , where and . There exists an such that if and , then , where

, for .

is extremal for

.
It follows that this theorem is indeed a reduction theorem.
Conjecture 2.8 (The Product Conjecture, Simonovits).
Assume that . If for some constants and
(2.4) 
then there exist forbidden families , with
such that for any , , where are extremal for .
This means that the extremal graphs are products of extremal graphs for some degenerate extremal problems (for ), and therefore we may reduce the general case to degenerate extremal problems.
Remarks 2.9.
(a) If we allow infinite families , then one can easily find counterexamples to this conjecture.
(b) If we allow linear errorterms, i.e. do not assume (2.4), then one can also find counterexamples, using a general theorem of Simonovits [223]; however, this is not trivial at all, see [225].
(c) A weakening of the above conjecture would be the following: for arbitrary large , in Conjecture 2.8 there are several extremal graphs, and for each , some of them are of product form, (but maybe not all of them) and the families also may depend on a little.
2.2 The asymmetric case of Excluded Bipartite graphs
The degenerate extremal graph problems have three different forms:
Problem 2.10 (Three versions).
(a) Ordinary extremal graph problems, where some bipartite or nonbipartite sample graphs are excluded, and we try to maximize under this conditions.
(b) The bipartite case, where the host graph is and we maximize under the conditions that and contains no . (Here we may assume that all are bipartite.) In this case we often use the notation . If but for some constant , then the answer to this problems and to the problem of are the same, up to a constant. If, however, we assume that is much larger than , then some surprising new phenomena occur, see Section 14.2.
(c) The asymmetric case. Color the vertices of the sample graphs in REDBLUE and exclude only those where the RED vertices of some are in the FIRST class of : maximize over the remaining graphs .
Denote the maximum number of edges in this third case by .
Remark 2.11.
We have seen Zarankiewicz’ problem (i.e. Problem 1.16). That corresponds to an asymmetric graph problem, (c). If we exclude in an matrix both a and an submatrices of 1’s, that will correspond to a bipartite graph problem, (b).
Conjecture 2.12 (Erdős, Simonovits [227]).
The simplest case when we cannot prove this is .
Remark 2.13 (Matrix problems).
Case (c) has also a popular matrix form where we consider 01 matrices and consider an matrix not containing a submatrix . The question is: how many s can be in such a matrix. This problem has (at least) two forms: the unordered and ordered one. We return to the Ordered Case in Subsection 12.4.
2.3 Reductions: Host graphs
The following simple but important observation shows that there is not much difference between considering any graph as a “host” graph or only bipartite graphs.
Lemma 2.14 (Erdős’ bipartite subgraph lemma).
Every graph contains a bipartite subgraph with
This lemma shows that there is not much difference between considering or as a host graph.
Corollary 2.15.
If denotes the maximum number of edges in an free bipartite graph, then
Assume now that we wish to have an upper bound on , where . One way to get such an upper bound is to partition the vertices into subsets of size . If, e.g, we know that , then we obtain that
(2.5) 
This often helps, however, occasionally it is too weak. Erdős formulated
Conjecture 2.16.
If then
Later this conjecture was made more precise, by Erdős, A. Sárközy and T. Sós, and proved by Győri, see Section 14.2 and [136].
We start with a trivial lemma.
Lemma 2.17.
Let be the average degree in , i.e. . Then contains a with .
To solve the cubeproblem, Erdős and Simonovits used two reductions. The first one was a reduction to bipartite graphs, see Section 2.14. The other one eliminates the degrees are much higher than the average.
Definition 2.18 (almostregularity).
is almostregular if .
Theorem 2.19 (almostregularization [92]).
Let , and . Then there is a almostregular for which
unless is too small.
This means that whenever we wish to prove that , we may restrict ourselves to bipartite almostregular graphs.
It would be interesting to understand the limitations of this lemma better. The next remark and problem are in this direction.
Remark 2.20.
By the method of random graphs one can show [92] that for every and and , there is with which does not have a almostregular subgraph with .
Problem 2.21 (ErdősSimnovits [92]).
Is it true that for every there exists an such that every , with , contains a almostregular subgraph , with where when ?
2.4 Excluding complete bipartite graphs
Certain questions from topology (actually, Kuratowski theorem on planar graphs) led to Zarankiewicz problem [256]. After some weaker results Kővári, T. Sós and Turán proved the following theorem, already mentioned in Section 1.1.
Theorem 2.22 (Kővári–T. Sós–Turán, [166]).
Let denote the complete bipartite graph with and vertices in its colorclasses. Then
(2.6) 
Remarks 2.23.
(a) If then (2.6) is better if we apply it with .
Sketch of proof of Theorem 2.22. The number of stars in a graph is where are the degrees in . If contains no then at most of these stars can share the same set of endpoints. We obtain
(2.7) 
Extending to all by
we have a convex function. Then Jensen’s Inequality implies that, the left hand side in (2.7) is at least and the result follows by an easy calculation.
Remark 2.25.
Slightly changing the above proof we get analogous upper bounds on in all three cases of Problem 2.10.
2.5 Probabilistic lower bound
The theory of random graphs is an interesting, important, and rapidly developing subject. The reader wishing to learn more about it should either read the original papers of Erdős, e.g., [63], [64], Erdős and Rényi, e.g., [86], or some books, e.g., Bollobás, [29], Janson, Łuczak and Ruciński, [151], Molloy and Reed [194].
Theorem 2.26 (ErdősRényi First Moment method).
Let be a family of graphs, and let
(2.8) 
where the minimum is taken only for subgraphs where the denominator is positive. (a) Let be a graph of order chosen uniformly, at random, from graphs with edges. For every there exists a such that if , then the probability that contains at least one is at most . (b) If we know only , then the probability that contains at least copies of is at most .
This implies that
(2.9) 
with defined above.
Remarks 2.27.
(a) A graph is called balanced if the minimum in (2.8), for , is achieved for . Erdős and Rényi formulated their result containing Theorem 2.26(a) only for balanced graphs . The part we use is trivial from their proof.
(b) Later Bollobás extended the ErdősRényi theorem to arbitrary .
(c) Győri, Rothschild and Ruciński achieved the generality by embedding any graph into a balanced graph [138].
Corollary 2.28.
If a finite contains no trees,^{14}^{14}14neither forests then for some , .
Mostly the weaker Theorem 2.26(a) implies Corollary 2.28: it does, whenever is finite and each contains at least two cycles in the same component. However, for cycles we need the stronger Theorem 2.26(b).
For example, for we have . Then, for sufficiently small, the probability that a graph with edges does not contain is positive. Hence
Comparing this with the KőváriT. SósTurán theorem (Theorem 2.22), we see that the exponent is sharp there, in some sense, if is fixed while .
Proof of Theorem 2.26. Consider the random graph with labeled vertices, in which each edge occurs independently, with the same probability . For each , choose a subgraph which attains the inner minimum for , in (2.8). Let , , and let denote the number of copies of in , and denote the expected number of copies of in .
Clearly, contains copies of . For each copy of , define a random “indicator” variable if , and otherwise. Since the number of copies of in is just , therefore, if denote the expected value, then
Summing over and taking , (for some ) we get
Now let . Then, for sufficiently small, the expected value is
Hence there exists a with . Delete an edge from each in this . The resulting graph contains no , and has at least
Remarks 2.29 (How did the probabilistic methods start?).
Mostly we write that applications of the Random Graphs (probabilistic method) started when Erdős (disproving a conjecture of Turán on the Ramsey Numbers) proved the existence of graphs without complete subgraphs of order and without independent sets of size .

Perhaps the earliest case of applying probabilistic methods was that of Paul Turán’s proof of the HardyRamanujan Theorem [243], where – reading the paper – it is obvious that Turán gave a probabilistic proof of a beautiful and important theorem, using the Chebishev inequality. However, either Turán did not realize that this is an application of the probabilistic method or he did not wish to burden the reader with that.

An important application of the probabilistic methods was that of Claude Shannon, when he constructed random codes.
Applying Theorem 2.26 to some families of cycles we obtain
Corollary 2.30.
For some constant ,
Erdős’ even cycles theorem asserts that , and this upper bound is probably sharp. ^{15}^{15}15The reference is missing here, since Erdős did formulate this theorem but never have published a proof of it, as far as we know. The random method (that is, Theorem 2.26) yields a lower bound of , a weaker result. Simonovits thinks that it is unlikely that Theorem 2.26 ever yields a sharp bound for a finite family. ^{16}^{16}16Some related results of G. Margulis, and A. Lubotzky, R. Phillips and P. Sarnak will be discussed in Section 4.9.
Corollary 2.30 is used in the next section to prove that if and only if contains a tree or forest.
2.6 Classification of extremal problems
The extremal graph problems can be classified in several ways. Here we shall speak of (a) nondegenerate, (b) degenerate and (c) linear extremal problems.
For Case (a) Theorem 2.3 provides an appropriately good description of the situation. In Case (b) . Here the “main term” disappears, ; therefore “the error terms dominate”. Case (c) will be discussed here shortly and in Sections 6 and 9 in more details.
The classification immediately follows from the following theorems:
Theorem 2.31.
if and only if contains a bipartite graph. Actually, if contains a bipartite graph then for, e.g., for any bipartite . If does not contain bipartite graphs, then .
Theorem 2.32.
For finite , if and only if contains a tree, or a forest. If is a tree or a forest, then, for ,
(2.10) 
Theorem 2.34 (Erdős [64], Bondy and Simonovits [34]).
Given an integer , for some constants ,
(2.11) 
Proof of Theorems 2.31, 2.32, and 2.33. If there is a bipartite , then Theorem 2.22 implies the sharper upper bound of Theorem 2.31. Indeed, for , by , we have,
If the minimum chromatic number , then contains no forbidden . Therefore
Actually, . This completes the proof of Theorem 2.31.
It is easy to show that if has minimum degree at least , then it contains every tree (by induction on ). An induction on yields (2.10), implying half of Theorem 2.32, when contains a tree (or a forest). If is finite and contains no trees, i.e., all the forbidden graphs contain some cycles, then we use Theorem 2.34, or simply Corollary 2.28, proved by probabilistic methods.^{17}^{17}17There are also deterministic proofs of Corollary 2.28, e.g., via the Margulis–Lubotzky–Phillips–Sarnak construction of Ramanujan graphs, see Construction 4.43.
Remark 2.35 (Infinite families).
For infinite families the situation is different: if e.g. is the family of all cycles, then : all graphs but the forests are excluded. There are many further families without trees where the extremal number is linear, see Section 9.
Proof of Theorem 2.34. The lower bound comes from a random graph argument of Erdős. Concentrate on the upper bound. If we are not interested in the value of the constant, then we can basically use the following argument: Take a graph with edges. Delete its minimum degree vertex, then the minimum degree vertex in the remaining graph, etc. At the end we get a with minimum degree at least . In the obtained graph fix a vertex and denote by the set of vertices at distance from . If , – as we assumed – then basically . Hence . So .∎
Assume for a second that itself is asymptotically regular:
Then the previous argument asserts that Therefore
We shall return to the case of excluded trees, namely, to the ErdősSós conjecture on the extremal number of trees, and to the related KomlósSós conjecture in Section 6. One final question could be if can be sublinear. This is answered by the following trivial result.
Theorem 2.36.
If is finite and , then .
Proof. Consider independent edges: this must contain an . Hence, there is an contained in the union of independent edges, for some . Also, there exists an . Hence an extremal graph has bounded degrees and bounded number of independent edges. This proves 2.36.∎
Theorem 2.36 easily extends to hypergraphs.
2.7 General conjectures on bipartite graphs
We have already formulated Conjecture 1.6 on the rational exponents. We have to remark that for hypergraphs this does not hold: the Behrend construction [23] is used to get lower bounds in the Ruzsa–Szemerédi Theorem, (Thm 1.9), showing that there is no rational exponent in that case. Yet, Erdős and Simonovits conjectured that for ordinary graphs there is. One could also conjecture the inverse extremal problem:
Conjecture 2.37.
For every rational there is a finite for which , for some constants .
The third conjecture to be mentioned here is on “compactness” [95]:
Conjecture 2.38.
For every finite there is an for which , for some constants .
3 Excluding complete bipartite graphs
3.1 Bipartite free graphs and the Zarankiewicz problem
Turán type extremal results (and Ramsey results as well) can often be applied in Mathematics, even outside of Combinatorics. Turán himself explained this applicability by the fact that – in his opinion – the extremal graph results were generalizations of the Pigeon Hole Principle.
Recall that denotes the maximum number of 1’s in an matrix not containing an minor consisting exclusively of 1’s. In 1951 Zarankiewicz [256] posed the problem of determining for , and the general problem has also become known as the problem of Zarankiewicz.^{18}^{18}18In Graph Theory two problems are connected to Zarankiewicz’ name: the extremal problem for matrices that we shall discuss here and the Crossing Number conjecture which is not our topic. Actually, the crossing number problem comes from Paul Turán, see [246]. Obviously, (for ). Observe that (where was defined following Remark 2.10.) Considering the adjacency matrix of a free graph on vertices we get . We will use this upper bound many times.
We will see that the easy upper bound in Theorem 2.22 is pretty close to the truth for . Actually, Kővári, T. Sós and Turán [166] proved an upper bound for the Zarankiewicz function
(3.1) 
which was slightly improved by Znám [259], [258], (he halved the last term to in the case of ) and Guy [130].
A bipartite graph where , is free if its “bipartite” adjacency matrix contains no full 1 submatrix.^{19}^{19}19Here the “bipartite adjacency matrix” is defined for a bipartite graph and if is joined to , otherwise . In other terminology, the hypergraph defined by the rows of this matrix is linear, and their hyperedges pairwise meet in at most one element. There is an important class of such hypergraphs, the Steiner systems . A family of subsets of an set is a Steiner system if every pair of elements is covered exactly once. For such an , clearly, . Such families are known to exists for (called finite projective planes of order ), and (affine planes) whenever is a power of a prime. Also for any given there exists an such that exists for all admissible , i.e., when and are integers (Wilson’s existence theorem [250]).
Kővári, T. Sós and Turán [166] proved that
Theorem 3.1.
, and
(3.2) 
Further, if is a prime, then
Theorem 3.2 (Reiman [208]).
(3.3) 