On the Turán Number for the Hexagon

Zoltan Füredi ^{∗}  Assaf Naor ^{†}  Jacques Verstraëte ^{‡}

Abstract

A long-standing conjecture of Erdős and Simonovits is that ex(n, C_{2k}), the maximum number of edges in an n-vertex graph without a 2k-gon is asymptotically \frac{1}{2}n^{1+1/k} as n tends to infinity. This was known almost forty years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that

ex(n, C_{6}) > \frac{3(\sqrt{5} − 2)}{(\sqrt{5} − 1)^{4/3}} n^{4/3} + O(n) > 0.5338n^{4/3}.

We also show that ex(n, C_{6}) ≤ λn^{4/3} + O(n) < 0.6272n^{4/3} if n is sufficiently large, where λ is the real root of 16λ^{3} − 4λ^{2} + λ − 3 = 0. This yields the best known upper bound for the number of edges in a hexagon-free graph. The same methods are applied to find a tight bound for the maximum size of a hexagon-free 2n by n bipartite graph.

1 Introduction

The forbidden subgraph problem involves the determination of the maximum number of edges that an n-vertex graph may have if it contains no isomorphic copy of a fixed graph H. This number is called the Turán number for H, and denoted ex(n, H). In this paper, we study the Turán problem for the hexagon, that is, the cycle of length six, C_{6}.

The densest constructions of 2k-cycle-free graphs for certain small values of k arise from the existence of rank two geometries called generalized k-gons, first introduced by Tits [18]. These may be defined as rank two geometries whose bipartite incidence graphs are regular graphs of diameter k and girth 2k, and are known to exist only when k is three, four or six. This fact is a consequence of a fundamental theorem of Feit and Higman [11]. It is therefore of interest to examine the extremal problem for cycles of length four, six and ten.

∗Department of Mathematics University of Illinois at Urbana-Champaign 1409 W. Green Street Urbana, Illinois 61801-2975 E-mail: z-furedi@math.uiuc.edu Research supported in part by a Hungarian National Science Foundation grant OTKA T 032452, and by a National science Foundation grant DMS 0140692.

†Theory Group, Microsoft Research, One Microsoft Way, Redmond, WA 98052, United States. E-mail:

anaor@microsoft.com

‡Department of Combinatorics and Optimization, University of Waterloo, Math Faculty 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada. E-mail: jverstra@math.uwaterloo.ca.

In these cases, Lazebnik, Ustimenko and Woldar [15] used the existence of polarities of generalized polygons to construct dense 2k-cycle-free graphs when k ∈ {2, 3, 5}. In particular, for k = 3, their construction shows that

ex(n, C_{6}) ≥ \frac{1}{2}n^{4/3} + O(n)

for infinitely many n. Erdős and Simonovits [10] conjectured the asymptotic optimality of these graphs, asking whether ex(n, C_{2k}) is asymptotic to \frac{1}{2}n^{1+1/k} as n tends to infinity. This was known to hold for quadrilaterals almost forty years ago, as proved by Erdős, Rényi and Sós [9], and independently by Brown [4], but was recently disproved in [15] for cycles of length ten. The only remaining case allowed by the Feit-Higman theorem is that of hexagons. In this paper, we refute the Erdős-Simonovits conjecture for hexagons:

Theorem 1.1 For infinitely many positive integers n, there exists an n-vertex hexagon-free graph of size at least

\frac{3(\sqrt{5} − 2)}{(\sqrt{5} − 1)^{4/3}} n^{4/3} + O(n) > 0.5338n^{4/3}.

For all n, ex(n, C_{6}) ≤ λn^{4/3} + O(n) < 0.6272n^{4/3} if n is sufficiently large, where λ is the real root of 16λ^{3} − 4λ^{2} + λ − 3 = 0.

This theorem gives the best known upper bound for ex(n, C_{6}). The proof of Theorem 1.1 requires a statement about hexagon-free bipartite graphs, which is interesting in its own right (see de Caen and Székely [6]). Let ex(m, n, C_{6}) be the maximum number of edges amongst all m by n bipartite hexagon-free graphs. We are able to determine ex(m, 2m, C_{6}) asymptotically for all m:

Theorem 1.2 Let m, n be positive integers. Then

ex(m, n, C_{6}) < 2^{1/3}(mn)^{2/3} + 16(m + n).

Furthermore, if n = 2m then as n tends to infinity,

ex(m, n, C_{6}) = \{ \begin{matrix}2^{1/3}(mn)^{2/3} + O(n) & for infinitely many m \\ 2^{1/3}(mn)^{2/3} + o(n^{4/3}) & for all m. \end{matrix}

Another natural question is the maximum number of edges in a quadrilateral-free subgraph of a hexagon-free graph. We answer this question completely, generalizing a theorem of Györi [12] and of Kühn and Osthus [14]:

Theorem 1.3 Let G be a hexagon-free graph. Then there exists a subgraph of G of girth at least five, containing at least half the edges of G. Furthermore, equality holds if and only if G is a union of edge-disjoint complete graphs of order four or five.

Throughout the paper, G = (V, E) denotes a graph with vertex set V = V (G) and edge set E = E(G). We write uv ∈ E instead of {u, v} ∈ E. If uv is assigned an orientation, then u → v means the edge uv is oriented from u to v. A sequence (x_{1}, x_{2}, …, x_{k+1}) of distinct vertices of G is used to denote a path of length k or, if x_{k+1} = x_{1}, a cycle of length k. The vertices x_{1} and x_{k+1} are referred to as endvertices of the path. If A is a set of vertices of G, then G[A] = {uv ∈ E(G) : u, v ∈ A} is the subgraph of G induced by A. Finally, d_{G}(v) and Γ_{G}(v) denote the degree and neighbourhood of a vertex v ∈ V in the graph G. In general, the subscript G is omitted.

2 Constructions

The aim of this section is to give a construction of hexagon-free graphs achieving the lower bound in Theorem 1.1, and bipartite hexagon-free graphs achieving the lower bound in Theorem 1.2. We start with a known construction of generalized quadrangles, and then modify it.

Bipartite construction

It is known that there exist (q + 1)-regular bipartite graphs H = H_{q}, with q^{3} + q^{2} + q + 1 vertices in each part, and girth eight, where q is a prime power. These are the incidence graphs of certain rank two geometries known as generalized quadrangles. Let L and R be the parts of H. To construct m by 2m bipartite graphs achieving the lower bound in Theorem 1.2, we add a new set L^{∗} of |L| vertices to H, and let ϕ : L^{∗} ↔ L be a bijection. Define a bipartite graph H_{q}^{∗} = H^{∗} with parts R and L ∪ L^{∗} as follows:

E(H^{∗}) = E(H) ∪ {uv : u ∈ L^{∗}, v ∈ R, ϕ(u)v ∈ E(H)}.

In words, we take two edge-disjoint copies of H and identify them on the vertices in R. To see that H^{∗} contains no hexagons, suppose C = (v_{1}, v′_{2}, v_{3}, v′_{4}, v_{5}, v′_{6}, v_{1}) is a hexagon in H^{∗}. By symmetry, we may assume C contains at least four edges of H. Form the closed walk ω = (v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{1}) in H, where v_{i} = v′_{i} if v′_{i} ∈ L and v_{i} = ϕ(v′_{i}) if v′_{i} ∈ L^{∗}. Since H contains no cycles of length at most six, ω traverses each edge of a tree T ⊂ H twice. However, T has at least four edges, since C contains at least four edges of H. This implies ω has length at least eight, which is a contradiction. Therefore H^{∗} contains no hexagons. Also, H^{∗} has 2(q + 1)(q^{3} + q^{2} + q + 1) edges and, with n = 2(q^{3} + q^{2} + q + 1) and m = q^{3} + q^{2} + q + 1, we have

|E(H^{∗})| > 2^{1/3}(mn)^{2/3} + \frac{2}{3}n − O(n^{2/3}).

It is known that there is a prime number in the interval {n, n + 1, …, n + cn^{θ}} for some θ ∈ [\frac{1}{2}, 1). The most recent advance is due to Baker, Harman and Pintz [2], who proved that θ = 21/40 works. Then the infinite sequence of graphs H_{q}^{∗} shows that for all m and n = 2m,

ex(m, n, C_{6}) > 2^{1/3}(mn)^{2/3} − O(n^{θ+5/6}).

This shows Theorem 1.2 is asymptotically optimal when n = 2m.

Non-bipartite construction

A polarity of a bipartite graph is a bijection between the parts of the bipartite graph which is an involutary automorphism of the graph. The existence of polarities for incidence graphs of certain rank two geometries, known as generalized polygons, was used by Lazebnik, Ustimenko and Woldar to construct dense graphs without cycles of length 2k for k ∈ {2, 3, 5}. In particular, it is known that the bipartite graphs H_{q} possess a polarity (see Peykre [16]) if and only if q = 2^{2α+1}, for some positive integer α. This was used in [15] to construct from H_{q} a graph G_{q} with N = q^{3}+q^{2}+q+1 vertices, \frac{1}{2}[(q+1)(q^{3}+q^{2}+q+1)−q^{2}−1] edges, and no cycles of length three, four or six. For our construction, we start with the graph G_{q} = G = (V, E). Let (A, B) be a partition of V into two sets, A and B, let G[A] be the subgraph of G induced by A, and suppose that each edge in G[A] is given an orientation. Let W be a new set of vertices, disjoint from V, with |W | = |A|, let ϕ be a bijection W ↔ A, and let G^{∗} be the graph on V ∪ W defined as follows:

E(G^{∗}) = E ∪ {uv : uϕ(v) ∈ E, u ∈ B, v ∈ W } ∪ {uv : u ∈ A, v ∈ W, ϕ(v) → u}.

We claim that G^{∗} is hexagon-free. To see this, suppose C = (v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{1}) is a hexagon in G^{∗}, and form the closed walk

ω = (u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, u_{6}, u_{1}),

where u_{i} = v_{i} if v_{i} ∈ V and u_{i} = ϕ(v_{i}) if v_{i} ∈ W. Note that ω is a closed walk in G. Since G contains no cycles of length three, four or six, ω is a walk on a tree T ⊂ G. Now C contains at least two vertices in W, otherwise T contains four edges of C and ω has length at least eight. So there are two vertices u, v ∈ W of C, each incident with two edges of E(G^{∗})\E(G), since W is an independent set in G^{∗}. The four edges of C incident with u and v correspond to two subpaths of ω of length two whose center vertices are ϕ(u) and ϕ(v), by construction. These subpaths must share an edge, otherwise T has at least four edges, and ω has length at least eight, which is not possible. Furthermore, the edge they have in common must be ϕ(u)ϕ(v) ∈ G[A], by construction. However, this implies both ϕ(u) → ϕ(v) and ϕ(v) → ϕ(u), which is impossible, since ϕ(u)ϕ(v) was given only one orientation. This contradiction completes the proof.

We now choose A so as to maximize |E(G^{∗})|. Fix a positive integer K < N and let A ⊂ V be a subset of size K, chosen uniformly at random among all such subsets. Observe that in expectation, the number of edges incident with A is at least

\frac{\binom{N−2}{K−2} + 2\binom{N−2}{K−1}}{\binom{N}{K}} = \frac{K}{N} · (2 − \frac{K − 1}{N − 1}) |E|.

Therefore we can choose such an A ⊂ V for which

|E(G^{∗})| ≥ |E| + \frac{K}{N} (2 − \frac{K − 1}{N − 1}) |E|.

The number of vertices in G^{∗} is n = N + K. Choosing K = ⌊(\sqrt{5} − 2)N⌋ we find

|E(G^{∗})| ≥ \frac{3(\sqrt{5} − 2)}{(\sqrt{5} − 1)^{4/3}} n^{4/3} + \frac{2(\sqrt{5} − 2)}{(\sqrt{5} − 1)}n − O(n^{2/3}).

This completes the construction for the lower bound in Theorem 1.1.

3 The Structure of Hexagon-Free Graphs

The quadrilateral relation on the edge-set of a hexagon-free graph G = (V, E) is the symmetric relation ϕ under which two edges are related if some quadrilateral in G contains both of them. In bounding ex(n, C_{6}), we require a description of the components of ϕ. In this section, we give a complete description of these components. The set of edges in each component of ϕ is the edge-set of a subgraph of G. We let Φ(G) denote the set of all subgraphs of G formed in this way. Let us say that a subgraph H of G is strongly induced if every path of length at most four with both endvertices in H is contained in H. A maximal complete bipartite subgraph of G is a complete bipartite subgraph of G which contains a cycle and is not contained in any other complete bipartite subgraph of G. Since G is hexagon-free, these consist of a pair of vertices and all their common neighbours in G. We say that a collection of subgraphs of a graph G decomposes G if the subgraphs are pairwise edge-disjoint and every edge of G is in one of the subgraphs. The main theorem we prove is as follows:

Theorem 3.1 Let G be a hexagon-free graph. Then Φ(G) decomposes G into single edges, maximal complete bipartite graphs and strongly induced subgraphs of types (1), (2) or (3).

Type (3) Type (1)

Type (2)

We give a description of the graphs in the illustrations. A subgraph of G of type (1) is a subgraph of G consisting of a complete graph with vertex set {a, b, c} (the vertices a, b and c are shown as white squares in the leftmost drawing), such that a and b have at least two common neighbours, a and c have at least two common neighbours, and the set of common neighbours of a and b is disjoint from the set of common neighbours of a and c. A subgraph of type (2) is a subgraph consisting of a complete graph with vertex set {a, b, c, d}, together with all common neighbours of {b, c} (the vertices b and c are shown as white squares in the center figure above). Finally, a subgraph of type (3) is a graph of minimum degree at least three on exactly five vertices.

Proof of Theorem 3.1. One observes that if V is the vertex set of a subgraph of G of type (i), then G[V] is of type (j) for some j ≥ i. Let us prove that J = G[V] is a strongly induced subgraph of G. Let P be a shortest path, with both endpoints in V, such that P ⊄ J. Then P has length at least two, since J is an induced subgraph of G. Let k be the length of P. By inspection, any pair of vertices of V is joined by a path of length two, three, and four in J, excepting those pairs of vertices (drawn as white squares in the illustration), all of whose common neighbours are already included in J. If k ≤ 4, then we find a path P′ ⊂ J, of length 6 − k, with the same pair of endvertices as P. However, P ∪ P′ is a hexagon in G. This contradiction shows k ≥ 5, so J is a strongly induced subgraph of G. In particular, if J ⊂ H for some H ∈ Φ(G), then H = J: since J is strongly induced, there can be no quadrilateral in G containing an edge in E(J) and an edge in E(G)\E(J).

Now we complete the proof. Suppose H ∈ Φ(G) is not a complete bipartite graph (in particular, not a single edge). Then H contains quadrilaterals, Q_{1} and Q_{2}, such that E(Q_{1}) ∩ E(Q_{2}) ≠ ∅ and Q_{1} ∪ Q_{2} is non-bipartite. For if Q_{1} ∪ Q_{2} is bipartite, then Q_{1}ΔQ_{2} is a cycle of length six. Let V consist of the union of V (Q_{1}) ∪ V (Q_{2}) and all vertices of G with at least two neighbours in V (Q_{1}) ∪ V (Q_{2}). Since G is hexagon-free, Q_{1} and Q_{2} share at least three vertices. If V (Q_{1}) = V (Q_{2}), then Q_{1} ∪ Q_{2} is a complete graph on four vertices. It follows that G[V] contains a subgraph, J, of type (2) or (3). By the first part of the proof, H = J. Now suppose Q_{1} and Q_{2} share three vertices. Then Q_{1} ∪ Q_{2} is of type (1), so G[V] contains a subgraph J of type (1), (2) or (3). By the first part of the proof, H = J. Therefore H has type (1), (2) or (3).

3.1 Quadrilateral-Free Subgraphs

In this section, we prove Theorem 1.3, that every hexagon-free graph contains a subgraph of girth at least five containing at least half its edges.

Proof of Theorem 1.3. By Theorem 3.1, Φ(G) decomposes G into single edges, maximal complete bipartite graphs and strongly induced subgraphs of types (1), (2) and (3). Let F be the subgraph consisting of all single edges in the decomposition given by Φ(G). By inspection, each H ∈ Φ(G) of type (1)-(3) has a subgraph T_{H} of girth at least five containing more than half the edges of H, except if H is a complete graph of order four or five in which case |E(T_{H})| = \frac{1}{2}|E(H)|. If F is non-empty, then we can choose a bipartite subgraph of F of girth at least five with a least \frac{1}{2}|E(F)| + 1 edges. It remains to deal with those components of Φ(G) which are complete bipartite graphs.

Let K be such a component. A triangle in G is defined to be a K-triangle if it contains an edge of K. We claim that there is an edge e_{K} ∈ E(G) joining two vertices of K such that every K-triangle in G contains e_{K}. One checks the claim using the fact that every quadrilateral in G is either contained in K or edge-disjoint from K, which follows since K is a component of Φ(G). We now define a tree T_{K} ⊂ K so that every triangle containing at least one edge of K also contains an edge of E(K)\E(T_{K}). Then the graph consisting of the union over K of all trees T_{K} has girth at least five. The tree T_{K} is chosen according to the location of the edge e_{K}, as shown in the figure below (the tree T_{K} is shown in bold and the edge e_{K} is dotted). In all cases except one, T_{K} has \frac{1}{2}|E(K)| + 1 edges. The exceptional case is when e_{K} joins two vertices of degree \frac{1}{2}|E(K)| in K (the figure on the right in the illustration below).

\begin{aligned}& T_{K} & T_{K} \\ T_{K} \end{aligned} ; e_{K} ; e_{K} ; e_{K}

Let J be the union of all the subgraphs T_{H} and T_{K}, together with F. Then J contains no quadrilateral (each is contained in an element of Φ(G)) and no triangle, since a triangle not contained in a type (1), (2) or (3) subgraph and not contained in F consists of at least one edge of a maximal complete bipartite subgraph of G. Finally, J has size at least

∑_{H∈Φ(G)} \frac{1}{2}|E(H)| = \frac{1}{2}|E(G)|.

Equality holds only if every element of Φ is a complete graph of order four or five (which are subgraphs of types (2) and (3), respectively) or a maximal complete bipartite graph K with two vertices of degree \frac{1}{2}|E(K)| joined in G, and E(F) = ∅. Now suppose every subgraph of G of girth at least five has size at most \frac{1}{2}|E(G)|. We claim that all components of Φ(G) are complete graphs of order four or five. Suppose this is not true. Then there is a component of Φ(G) which is a maximal complete bipartite graph with two vertices of degree \frac{1}{2}|E(K)|, joined by the edge e_{K}. Note that there is no triangle in G containing e_{K} with is not already contained in E(K)∪\{e_{K}\}. Since E(F) = ∅ and |E(J)∪\{e_{K}\}| > \frac{1}{2}|E(G)|, e_{K} is contained in a quadrilateral in E(J)∪{e_{K}}, and this quadrilateral is contained in a complete bipartite component L of Φ(G). It follows that e_{L} = e_{K} and so the tree T_{L} ⊂ L has size \frac{1}{2}|E(L)| + 1. Therefore |E(J)| > \frac{1}{2}|E(G)|, which is a contradiction. So all components of Φ(G) are complete graphs of order four or five.

In fact, for bipartite graphs, the following stronger statement is true.

Theorem 3.2 Let G = (V, E) be a bipartite hexagon-free graph. Then G contains a subgraph F, of girth at least eight, such that d_{F} (v) ≥ \frac{1}{2}d_{G}(v) for every vertex v ∈ V.

Proof. By Theorem 3.1, each H ∈ Φ(G) is either a complete bipartite graph containing a quadrilateral, or a single edge. For each H ∈ Φ(G) containing a quadrilateral, we choose a spanning tree T_{H} in H containing at least half the edges on each vertex of H. The union of all these trees together with all single edges in Φ(G) is the required subgraph of G.

Corollary 3.1 Let G be a hexagon-free bipartite graph with parts A and B. Suppose every vertex of A has degree at least δ(A) and every vertex of B has degree at least δ(B), and G has maximum degree Δ. Then

Δ(δ(A) − 2)(δ(B) − 2) ≤ 8 max{|A|, |B|}.

For any n-vertex hexagon-free graph of minimum degree δ and maximum degree Δ, the inequality Δ(δ − 4)^{2} ≤ 64n holds.

Proof. Let F be a subgraph of G as in the last theorem. Then every vertex of A has degree at least δ(A)/2 in F and every vertex of B has degree at least δ(B)/2 in F. Let v be a vertex of maximum degree in F. Then d_{F} (v) ≥ Δ/2. We assume v ∈ A, as similar arguments are applied in the case v ∈ B. Since F has girth at least eight, the number of vertices of F at distance three from v is at least

\frac{Δ}{2} · (\frac{δ(A)}{2} − 1) (\frac{δ(B)}{2} − 1) .

As all these vertices are distinct, this expression is at most |B|. For the second statement of the corollary, we use an observation of Erdős [7]: any graph G contains a bipartite subgraph F such that d_{F} (v) ≥ \frac{1}{2}d_{G}(v) for all vertices v of G. By the first part of the corollary,

\frac{Δ}{2} (\frac{δ}{2} − 2)^{2} ≤ 8n.

This completes the proof.

4 Matrix Inequalities

A very general Hölder-type inequality for matrices was proved by Blakley and Roy [3] : they showed that if A is an n × n symmetric pointwise non-negative matrix and v is a non-negative unit vector, then

⟨A^{k}v, v⟩ ≥ ⟨Av, v⟩^{k} .

In the current context, we note that the Blakley-Roy inequality implies that ∥A^{k}∥_{1} ≥ (∥A∥_{1})^{k}, where ∥A∥_{1} is the sum of the entries of the matrix A divided by n. If A is the adjacency matrix of an n-vertex graph, then ∥A^{k}∥_{1} is precisely the (normalized) number of walks of length k in the graph, where the walks (ω_{0}, ω_{1}, ω_{2}, …, ω_{k}) and (ω_{k}, ω_{k−1}, …, ω_{1}, ω_{0}) are considered distinct. It is not hard to deduce that the number of paths of length three in a graph G = (V, E) with n vertices is at least

\frac{1}{2}(W_{3} − 6T − 4P_{2} − 2P_{1}) ≥ \frac{4|E|^{3}}{n^{2}} − 3Δ|E|  (1)

where Δ is the maximum degree of G, P_{i} is the number of paths of length i in G, W_{3} is the number of walks of length three in G, and T is the number of triangles in G. The above inequality follows from the fact that G contains at most (Δ − 1)|E|/3 triangles, at most (Δ − 1)|E| paths of length two, and |E| paths of length one. The inequality (1) may also be deduced from a Moore-type bound, established recently by Alon, Hoory and Linial [1].

In the case of bipartite graphs, Sidorenko [17] proved a similar statement to (1) for matrices which are not necessarily symmetric. Extending the results in [1], Hoory [13] gave a tight lower bound on the number of paths of length k in an m by n bipartite graph with prescribed average degree. A consequence of these inequalities is that the number of paths of length three in an m by n bipartite graph G = (V, E) with maximum degree Δ is at least

\frac{1}{2}(W_{3} − 4P_{2} − P_{1}) ≥ \frac{|E|^{3}}{mn} − 2Δ|E|.  (2)

These inequalities will be used in the proofs of Theorems 1.1 and 1.2.

5 Degenerate and Nondegenerate Pairs

Throughout this section, G = (V, E) is a fixed hexagon-free graph and π is a pair of vertices of G. We denote by |π| the number of paths of length three in G with both endvertices in π. Suppose P_{1}, P_{2}, …, P_{k} are the paths of length three joining the two vertices of π. We say that π is degenerate if the distance between the vertices of π in P_{1} ∪ P_{2} ∪ … ∪ P_{k} is two, and π is non-degenerate otherwise. We emphasize that the distance in the definition of degeneracy is taken in P_{1} ∪ P_{2} ∪ … ∪ P_{k}, and not in G.

Lemma 5.1 Let π ∈ \binom{V}{2} with |π| ≥ 2, and let P_{1}, P_{2}, …, P_{k} be the paths of length three with both endvertices in π. Then π is non-degenerate if and only if

K_{π} = ⋃_{i,j=1}^{k} E(P_{i}) Δ E(P_{j})

is a complete bipartite graph, and E(P_{1}) ∩ E(P_{2}) ∩ … ∩ E(P_{k}) consists of a single edge, e_{π}, incident with a vertex of maximum degree in K_{π}.

\begin{matrix}K_{π} & π \\ π \end{matrix} ; e_{π}

Proof. It is clear that if K_{π} is a complete bipartite subgraph of G, then the distance between the vertices of π in P_{1} ∪ P_{2} ∪ … ∪ P_{k} is three, so π is non-degenerate. Now suppose π is non-degenerate. Let E_{π} be the set of edges of P_{1} ∪ P_{2} ∪ … ∪ P_{k} which are not incident with π. Since G is hexagon-free, E_{π} is an intersecting family, so E_{π} is a star or a triangle. In the latter case it is not hard to see that π is degenerate. Therefore E_{π} is a star. Let w be the center of E_{π}. Then exactly one vertex v of π is adjacent to w. If the other vertex u of π is not adjacent to some endvertex x of E_{π}, then the edge wx is not in any of the paths P_{i}, which is a contradiction. Therefore u is adjacent to all endvertices of E_{π}, which means that the union of all E(P_{i}) Δ E(P_{j}) is a complete bipartite subgraph of G. Furthermore,

E(P_{1}) ∩ E(P_{2}) ∩ … ∩ E(P_{k}) = {vw},

so we take the edge e_{π} to be vw.

We define a graph H to be central if some vertex of H is adjacent to all other vertices in H. In other words, H has a spanning star.

Lemma 5.2 Let π be a pair of vertices of G with |π| ≥ 2, and suppose P_{1}, P_{2}, …, P_{k} are the paths of length three in G joining the vertices in π. Then π is degenerate if and only if the graph P_{1} ∪ P_{2} ∪ … ∪ P_{k} is central.

Proof. Suppose J = P_{1} ∪ P_{2} ∪ … ∪ P_{k} is central. Since π is not an edge of any P_{i}, π is certainly degenerate. Now suppose π is degenerate, and let E_{π} be the set of edges of J which are not incident with a vertex of π. Then E_{π} is an intersecting family, so E_{π} is a star or a triangle. If E_{π} is a triangle, then J has five vertices, and it is straightforward to verify that J is central. Suppose E_{π} is a star with center w. Since π is degenerate, there is a path (u, x, v) in J with both endvertices in π = {u, v}. If x = w, then u and v are adjacent to w, so w is central. If x ≠ w, then since E_{π} is a star with center w, (u, x, w, v) and (v, x, w, u) are paths of length three in J, so u and v are adjacent to w. It follows that J is central.

6 Counting Paths : Bipartite Graphs

We now prove that very few pairs of vertices in a bipartite hexagon-free graph are joined by at least three paths of length three. More precisely:

Lemma 6.1 Let G = (V, E) be a hexagon-free bipartite graph of maximum degree Δ, and let Π be the set of pairs π for which |π| ≥ 2 and π ∈ E, or |π| ≥ 3. Then

∑_{π∈Π} |π| ≤ Δ|E|.

Proof. A complete bipartite subgraph of G is called maximal if it is not properly contained in any other complete bipartite subgraph, and contains a cycle. By Theorem 3.1, Φ(G) is a decomposition of G into maximal complete bipartite graphs and single edges. Moreover, every maximal complete bipartite graph in G is a component of Φ(G), since every two edges of this subgraph are related in ϕ. Now let π ∈ Π. By Lemma 5.2, the union of all paths of length three with endvertices in a degenerate pair is a central graph, and such a graph cannot be bipartite. So every pair π ∈ Π is non-degenerate. Now we use the notation K_{π} and e_{π} of Lemma 5.1. By this lemma, for each π ∈ Π, K_{π} is a complete bipartite graph, and all paths of length three with both endvertices in π comprise a subpath of K_{π} of length two, together with a fixed edge e_{π}, incident with a vertex of maximum degree in K_{π}. For π ∈ Π, define

h(π) = \{ \begin{matrix}K_{π} ∪ \{π, e_{π}\} & if π ∈ E \\ K_{π} & if π ∉ E. \end{matrix}

Note that h(π) is a complete bipartite subgraph of G, with exactly two vertices of degree at least three. We claim that h(π) is a maximal complete bipartite subgraph of G. Suppose, for a contradiction, that this is false for some π ∈ Π. Then there is a path P ⊂ G, of length two, such that P ⊄ h(π), and P joins the two vertices of h(π) of degree at least three. However, P ∪ {e_{π}} is a path of length three with both endvertices in π, which contradicts Lemma 5.1. This proves the claim, and we conclude that h(π) ∈ Φ(G). Let Φ^{∘}(G) consist of all elements of Φ(G) which are not single edges. Now define

h^{⊣} : Φ^{∘}(G) → Π where h^{⊣}(H) = {π ∈ Π : h(π) = H}.

Thus h^{⊣} is the inverse image of h. Our next claim is |h^{⊣}(H)| ≤ 2Δ for all H ∈ Φ^{∘}(G). For a fixed H ∈ Φ^{∘}(G), if h(π) = H and π ∈ E, then π ∈ E(H), by definition of h(π). So the equation h(π) = H has |E(H)| solutions π ∈ E. The equation h(π) = H has at most 2Δ−|E(H)| solutions π ∉ E, since K_{π} = H in this case, and there are at most 2Δ−|E(H)| choices of the edge e_{π} ∈ E(G)\E(H). We conclude that |h^{⊣}(H)| ≤ 2Δ for all H ∈ Φ^{∘}(G), proving the claim.

Finally, for all π ∈ Π, we have 2|π| = |K_{π}|, so |π| ≤ \frac{1}{2}|E(H)| for all π ∈ h^{⊣}(H). Therefore

∑_{π∈Π} |π| = ∑_{H∈Φ^{∘}(G)} ∑_{π∈h^{⊣}(H)} |π|

≤ ∑_{H∈Φ^{∘}(G)} ∑_{π∈h^{⊣}(H)} \frac{1}{2}|E(H)|
= ∑_{H∈Φ^{∘}(G)} |h^{⊣}(H)| · \frac{1}{2}|E(H)|
≤ ∑_{H∈Φ^{∘}(G)} Δ|E(H)|.

This is at most Δ|E|, since the subgraphs in Φ^{∘}(G) are pairwise edge-disjoint.

Remark. The condition π ∈ Π in this lemma is necessary. For example, the bipartite graph H^{∗}, defined in Section 2, has maximum degree 2(q + 1) and 2(q + 1)(q^{3} + q^{2} + q + 1) edges, and

∑_{{|π|=2 \atop π∉Π}} |π| = ∑_{{|π|=2 \atop π∉E}} |π| ∼ 4q^{6} ∼ qΔ|E|.

The reason the lemma does not apply to pairs π ∉ Π with |π| = 2 is that if two non-adjacent vertices π with |π| = 2 are joined by paths P and Q of length three, then P ∪ Q contains a quadrilateral by Lemma 5.1, but this quadrilateral (the subgraph h(π) in the proof above) might not be a maximal complete bipartite subgraph of G.

7 Proof of Theorem 1.2

We prove, by induction on m + n, that if G = (V, E) is a bipartite graph with parts A and B of sizes m ≥ 3 and n ≥ 3 respectively, and |E| ≥ 2^{1/3}(mn)^{2/3} + 16(m + n), then G contains a hexagon. Let f(m, n) = 2^{1/3}(mn)^{2/3} + 16(m + n). First note that the statement of the induction hypothesis is vacuously true if m + n ≤ 16, since f(m, n) > mn in this case. Now let m + n > 16, and suppose, for a contradiction, that some m by n bipartite graph G = (V, E), with |E| ≥ f(m, n), contains no hexagon. Let

δ(A) = \frac{2}{3} · 2^{1/3}m^{−1/3}n^{2/3} + 16
δ(B) = \frac{2}{3} · 2^{1/3}n^{−1/3}m^{2/3} + 16.

Note that δ(A) ≤ f(m, n) − f(m − 1, n) and δ(B) ≤ f(m, n) − f(m, n − 1). It follows that every vertex of A has degree at least δ(A), otherwise we remove a vertex of degree less than δ(A) to obtain an (m − 1) by n bipartite graph with at least f(m − 1, n) edges, and this graph contains a hexagon, by induction. Similarly, every vertex of B has degree at least δ(B). By Corollary 3.1,

Δ · \frac{4}{9}(m^{1/3}n^{1/3}) < Δ(δ(A) − 2)(δ(B) − 2) ≤ 8n.

It follows that Δ < 18 · 2^{1/3}n^{2/3}m^{−1/3}. Now the number of paths of length three in G is ∑ |π|, where the sum is over all pairs π ∈ \binom{V}{2}. By Lemma 6.1 and inequality (2),

\frac{|E|^{3}}{mn} − 2Δ|E| ≤ ∑ |π| ≤ 2mn + 2Δ|E|.

Let g(x) = x^{3}/mn − 4Δx − mn and z = 27(mn)^{2} + 3\sqrt{(3mm)^{4} − 192(Δmn)^{3}}. Then g(x) has a unique real root x_{0} given by

x_{0} = \frac{1}{3}z^{\frac{1}{3}} + 4Δmnz^{− \frac{1}{3}}
< 2^{\frac{1}{3}} (mn)^{\frac{2}{3}} + 4Δmn(27mn)^{− \frac{2}{3}}
< 2^{\frac{1}{3}} (mn)^{\frac{2}{3}} + \frac{4 · 18 · 2^{\frac{1}{3}}}{27^{\frac{2}{3}}} n
< 2^{\frac{1}{3}} (mn)^{\frac{2}{3}} + 16n

In this calculation we used the upper bound Δ < 18 · 2^{1/3}n^{2/3}m^{−1/3}. The above expression is an upper bound for |E|, which contradicts the lower bound |E| ≥ f(m, n).

8 Counting Paths : Nonbipartite Graphs

In the case of non-bipartite hexagon-free graphs, we prove that ∑ |π| ≤ 35Δ|E| where the sum is over all pairs π of vertices which have |π| ≥ 3 or |π| ≥ 2 and π ∈ E or |π| ≥ 2 and π is degenerate:

Lemma 8.1 Let G = (V, E) be a hexagon-free graph of maximum degree Δ, and let Π^{∗} be the set of degenerate pairs π ∈ \binom{V}{2} with |π| ≥ 2. Then

∑_{π∈Π∪Π^{∗}} |π| ≤ 35Δ|E|.

Proof. We first consider the contribution of pairs π ∈ Π^{∗} to the sum on the left. Let p[v] denote the number of paths of length three in G consisting only of vertices in A = Γ(v)∪{v}. By Lemma 5.2, for π ∈ Π^{∗}, the union of all the paths of length three with endvertices in π is a central subgraph of G. Therefore

∑_{π∈Π^{∗}} |π| ≤ ∑_{v∈V} p[v]

Let e[v] be the number of edges of G[A]. If we choose a pair of disjoint edges in G[A], then there are at most four choices for a path of length three containing these edges. Therefore p[v] < 2e[v]^{2}. Now since G is hexagon free, no path of length four consists entirely of edges in Γ(v). By the Erdős-Gallai theorem [8], there are then at most 3d(v)/2 edges in Γ(v), so e[v] ≤ 5d(v)/2. It follows that

∑_{π∈Π^{∗}} |π| < ∑_{v∈V} 2e[v]^{2} ≤ ∑_{v∈V} \frac{25Δ}{2}d(v) ≤ 25Δ|E|.

This takes care of the sum over Π^{∗}.

Now let π ∈ Π and define h(π) = K_{π} if π ∉ E and h(π) = K_{π} ∪ {e_{π}, π} if π ∈ E, as in the proof of Lemma 6.1. Recall that a maximal complete bipartite subgraph of G is a complete bipartite subgraph of G which contains a cycle and it not properly contained in any other complete bipartite subgraph of G. Following the proof of Lemma 6.1, h(π) is a maximal complete bipartite subgraph of G. By Theorem 3.1, h(π) is contained in a unique subgraph H_{π} ∈ Φ^{∘}(G), where Φ^{∘}(G) is the set of subgraphs of G in Φ(G) which contain a cycle. By inspection, using Theorem 3.1, each H ∈ Φ^{∘}(G) contains at most ten maximal complete bipartite subgraphs of G. Define

g : Φ^{∘}(G) → Π by g(H) = {π : H_{π} = H}.

Fix H ∈ Φ^{∘}(G). Then the equation g(π) = H with π ∈ E has at most |E(H)| solutions, since π ∈ E implies π ∈ E(H_{π}). The equation g(π) = H with π ∉ E has at most 20Δ solutions, since there are ten choices for h(π), which is a maximal complete bipartite subgraph of H, and then at most 2Δ choices for e_{π}, which is incident with one of the two vertices of h(π) of maximum degree. Finally, |π| ≤ \frac{1}{2}|E(H)| for all π ∈ g(H). Therefore

∑_{π∈Π} |π| = ∑_{H∈Φ^{∘}(G)} ∑_{π∈g(H)} |π|
≤ ∑_{H∈Φ^{∘}(G)} |g(H)| · \frac{1}{2}|E(H)| ≤ ∑_{H∈Φ^{∘}(G)} 10Δ|E(H)|.

This is at most 10Δ|E|, by Theorem 3.1.

8.1 Maximum Directed Cuts

A maximum directed cut in an oriented graph G is a partition of the vertex set into two sets X and Y such that the number of directed edges from X to Y is as large as possible. This maximum is denoted mdc(G).

Lemma 8.2 Let G = (V, E) be an oriented graph on n vertices, and suppose that mdc(G) ≤ γ|E|. Then G contains at least (1 − γ)^{2}|E|^{2}/n directed paths of length two.

The proof of Lemma 8.2 is based on the following numerical inequality:

Lemma 8.3 For n ≥ 1 let V be an n-point set and f, g : V → [0, ∞) be two functions such that ∑ f(v) = ∑ g(v). Then

∑_{v∈V} f(v)g(v) ≥ \frac{1}{n} [ ∑_{v∈V} min\{2f(v) − g(v), f(v)\} ]^{2}

Proof. If f = g, then the inequality becomes the Cauchy-Schwartz inequality

∑_{v∈V} f(v)^{2} ≥ \frac{1}{n}(∑_{v∈V} f(v))^{2}.

Suppose, therefore, that there exist u, v ∈ V such that f(u) > g(u) and f(v) < g(v), and let ε = min{|f(u)−g(u)|, |f(v)−g(v)|}. Then define functions f′ and g′ which are identical to f and g on V \{u, v} and such that f′(u) = f(u)−ε and g′(v) = g(v)−ε, and f′(v) = f(v) and g′(u) = g(u). Then f′ and g′ are non-negative functions with the same sum. Furthermore, the left hand side of the inequality decreases, whereas the right hand side stays the same. Repeating the transformation f → f′ and g → g′ finitely many times, we arrive at the Cauchy-Schwartz inequality. Since the inner product ∑ f(v)g(v) only decreased under the transformation, this completes the proof.

Proof of Lemma 8.2. We assume the vertex set of G is V. For a vertex v ∈ V, let f(v) and g(v) be the number of edges incident with v which are oriented into v, and the number of edges oriented out of v, respectively. The number of directed paths of length two is exactly ∑ f(v)g(v). The restriction on the size of the maximum directed cut implies that for some a ≤ γ|E|,

∑_{v∈I} [g(v) − f(v)] = a where I = {v : g(v) > f(v)}.

Also ∑ f(v) = |E| = ∑ g(v). By Lemma 8.3,

∑_{v∈V} f(v)g(v) ≥ \frac{1}{n}(|E| − a)^{2} ≥ \frac{1}{n}(1 − γ)^{2}|E|^{2}.

Therefore the number of directed paths of length two in G is at least (1 − γ)^{2}|E|^{2}/n.

8.2 Pairs Joined by a Unique Path

Lemma 8.1 shows that less than 18Δ|E| pairs of vertices of a hexagon-free graph G are joined by at least three paths of length three. The question remains: does there exist an extremal n-vertex hexagon-free graph for which almost all pairs are joined by two paths of length three? In this section, we prove a lemma which shows that such graphs are far from extremal. This should be compared with the bipartite construction in Section 2.

An oriented path of length three is a forward path if it contains a directed path of length two from one of its endvertices. For example, u → v → w ← x and u → v ← w ← x are forward paths, whereas u → v ← w → x is not. For a given orientation of a graph G, let Π^{∗∗} denote the set of pairs of vertices joined by at least one forward path and at least two paths of length three.

Lemma 8.4 Let G = (V, E) be a hexagon-free graph of maximum degree Δ. Then there is an orientation of G such that

∑_{π∈Π^{∗∗}} |π| < 43Δ|E|.

Proof. The orientation is described as follows. For subgraph H ∈ Φ(G) which is not a quadrilateral and not a single edge, we orient the edges of E(H) so that each vertex of degree two in H has indegree two. The remaining edges of G are oriented arbitrarily. By Theorem 3.1, since Φ(G) decomposes G, this orientation is consistent. Then, by Lemma 8.1,

∑_{π∈Π^{∗}∪Π} |π| ≤ 35Δ|E|.

For the rest of the proof, π ∈ Π^{∗∗}\(Π^{∗} ∪ Π), so that |π| = 2 and π is non-degenerate. If P = P_{π} and Q = Q_{π} are the paths of length three with endvertices in π, then E(P)ΔE(Q) is a quadrilateral, K_{π}, by Lemma 5.1. By Theorem 3.1, K_{π} is contained in a unique subgraph H_{π} ∈ Φ(G). It is not hard to see, via Theorem 3.1, that there are at most 4Δ|E| choices of π ∈ \binom{V}{2} such that at least one of the two vertices incident in K_{π} with a vertex of π has degree at least three in H_{π}, or such that K_{π} = H_{π}. Now suppose π is not such a pair and |π| = 2. Then we can assume π = {u, v},

K_{π} = (u, x, w, y) P_{π} = (u, x, w, v) Q_{π} = (u, y, w, v)

and K_{π} ≠ H = H_{π}, and d_{H}(x) = d_{H}(y) = 2. Since H is not a quadrilateral, K_{π} has the orientation u ← x → w ← y → u. If P_{π} is a forward path, then u → x → w or v → w → x, however, these orientations both conflict with the orientation of K_{π}. We conclude that neither P_{π} nor Q_{π} is a forward path. So there are less than 4Δ|E| pairs π ∈ Π^{∗∗}\(Π^{∗} ∪ Π). It follows that

∑_{π∈Π^{∗∗}} |π| ≤ ∑_{π∈Π^{∗∗}\(Π^{∗}∪Π)} |π| + ∑_{π∈Π^{∗}∪Π} |π| < 35Δ|E| + 8Δ|E| < 43Δ|E|.

This completes the proof.

Corollary 8.1 Let G = (V, E) be a hexagon-free graph of minimum degree δ and maximum degree Δ, where δ ≥ 2, and suppose G has no cut of size more than γ|E|. Then the number of pairs of vertices of G joined by exactly one path of length three is greater than

(1 − γ)^{2} \frac{(δ − 2)|E|^{2}}{n} − 43Δ|E|.

Proof. By Lemma 8.2, the number of directed paths of length two in any orientation of the edges of G is at least (1 − γ)^{2}|E|^{2}/n. In particular, the number of forward paths in any orientation of G is at least (1 − γ)^{2}(δ − 2)|E|^{2}/n, since there are at least δ − 2 ways of extending a given directed path of length two to a forward path. By Lemma 8.4, there is an orientation of G such that fewer than 43Δ|E| forward paths are the unique path of length three joining their endvertices. This completes the proof.

9 Proof of Theorem 1.1

Let G = (V, E) be an n-vertex graph with at least λn^{4/3} + cn edges and no hexagon, such that n is as small as possible. Let δ = ⌊\frac{4}{3}λn^{1/3}⌋ + c, and suppose G has maximum degree Δ. We may assume d_{G}(v) > δ − 1 for all v ∈ V, otherwise we remove a vertex of smallest degree to obtain a graph with at least λ(n − 1)^{4/3} + c(n − 1) edges, and this graph contains a hexagon, by the minimality of G. Consider a maximum cut H with parts of sizes m and n − m, where m = ⌊n/2⌋. By Theorem 1.2, if c > 32λ, then

|E(H)| ≤ 2^{1/3}(m(n − m))^{2/3} + 16n ≤ \frac{1}{2}n^{4/3} + 16n < \frac{1}{2λ}|E|.

Let Π_{i} be the set of pairs of vertices of G joined by exactly i paths of length three. Using the lower bound for |Π_{1}| given by Corollary 8.1, with γ = 1/2λ,

|Π_{1}| + 2|Π_{2}| < n^{2} − (1 − \frac{1}{2λ})^{2} \frac{(δ − 2)|E|^{2}}{n} + 43Δ|E|.

By inequality (1), G has at least \frac{4|E|^{3}}{n^{2}} − 3Δ|E| paths of length three. So, by Lemma 8.1,

\frac{4|E|^{3}}{n^{2}} − 3Δ|E| < ∑ |π| < |Π_{1}| + 2|Π_{2}| + 35Δ|E|

< n^{2} − (1 − \frac{1}{2λ})^{2} \frac{(δ − 2)|E|^{2}}{n} + 78Δ|E|

< n^{2} − (1 − \frac{1}{2λ})^{2} \frac{4|E|^{3}}{3n^{2}} + \frac{(c + 9)|E|^{2}}{3n} + 78Δ|E|.

By Corollary 3.1, Δ is within a constant factor of the average degree of G:

Δ ≤ (6/λ)^{2}n^{1/3}.

Using this inequality, we may rearrange the preceding inequality by replacing |E| by λn^{4/3}+ cn, multiplying by n^{2}, and moving all terms to the left hand side. A small calculation shows that after this rearrangement, the coefficient of n^{4} is \frac{1}{3}(16λ^{3} − 4λ^{2} + λ − 3). By definition of λ, this is zero. The rest of the inequality above becomes:

(c + 3λ^{2} + \frac{49}{3}λ^{2}c − \frac{2916}{λ} − 4λc) n^{\frac{11}{3}} + (\frac{c^{2}}{λ} + \frac{50}{3}λc^{2} + 6λc − \frac{2916c}{λ^{2}} − 4c^{2}) n^{\frac{10}{3}}
+ (\frac{17c^{3}}{3} − \frac{4c^{3}}{3λ} + \frac{c^{3}}{3λ^{2}} + 3c^{2}) n^{3} < 0.

The left hand side is positive if c is large enough, which is a contradiction. Therefore if c is large enough constant, then every n-vertex graph with at least λn^{4/3} + cn edges contains a hexagon. This proves Theorem 1.1.

10 Concluding Remarks

• Using Corollary 8.1, one can deduce the following statement:

if o(n^{2}) pairs of vertices in an n-vertex hexagon-free graph G are joined by exactly one path of length three, then G has a bipartite subgraph with |E(G)| − o(n^{4/3}) edges.

This is proved as follows. First we observe that the statement is trivial if |E(G)| = o(n^{4/3}), so we assume |E(G)| ≥ ϵn^{4/3} where ϵ > 0 is an absolute constant. As in the proof of Theorem 1.1, one proves that the minimum degree of G is at least c|E|/n and the maximum degree of G is at most d|E|/n where 0 < c < d are absolute constants (for example see the upper bound on Δ given in the proof of Theorem 1.1). If the maximum cut in G has size γ|E(G)| then Corollary 8.1 shows that at least

(1 − γ)^{2}cϵ^{3}n^{2} − O(dϵ^{2}n^{5/3})

pairs of vertices of G are joined by exactly one path of length three. On the other hand, the number of such pairs of vertices of G is o(n^{2}), by assumption. Therefore γ = 1 − o(1), and G has a maximum cut of size |E(G)| − o(n^{4/3}).

• The non-bipartite construction in Section 2 above gives a large family of hexagon-free graphs with roughly the same number of edges. Indeed, the base graph G is known to be pseudorandom (see Chung and Graham [5]), and it is known that in such graphs, the number of edges between disjoint sets A and B of vertices and the number of edges induced by A are roughly the same as in a random graph with the same density. Therefore we may choose any subset A of size K = ⌊(\sqrt{5} − 2)N⌋ and any orientation of the edges within A, and the construction will have about the same density. On the other hand, the distribution of the degrees of the new vertices in W depends explicitly on the orientation of A, so many of the graphs obtained are non-isomorphic.

• There is not much evidence to suggest whether

lim_{n→∞} ex(n, C_{6})/n^{4/3}

exists. If the limit does exist, then determining its value is an interesting problem. We are only able to show that the value is in the interval (0.5338, 0.6272). We believe that its value should be closer to 0.5338 than 0.6272, but do not have a conjecture as to the exact value, even under the assumption that our graphs are regular. For these reasons, we have not attempted to optimize the constants in the terms of lower order in all of our bounds.

• Another interesting question, which might shed light on the asymptotic behaviour of ex(n, C_{6}), is to determine whether or not there are infinitely many n such that

ex(n, n, C_{6}) ≥ cn^{4/3} − o(n^{4/3})

for some constant c > 1. One way of proving this would be to find infinitely many n/2 by n bipartite graphs of girth at least eight, and with at least \frac{1}{2}cn^{4/3} − o(n^{4/3}) edges; then the bipartite construction in Section 2 can be applied to give an n by n bipartite graph with cn^{4/3} − o(n^{4/3}) edges. Note that any bipartite graph of girth at least eight and with parts of sizes n/2 and n has at most 2^{−2/3}n^{4/3} + O(n) edges, by Theorem 1.2.

References

[1] Alon, N. Hoory, S. Linial, N. The Moore bound for irregular graphs. Graphs Combin. 18 (2002), no. 1, 53–57.

[2] Baker, R. C., Harman, G., Pintz, J. The difference between consecutive primes. II. Proc. London Math. Soc. 83 (2001), no. 3, 532-562.

[3] Blakley, G., Roy, P. A Hölder type inequality for symmetric matrices with nonnegative entries. Proc. Amer. Math. Soc. 16 (1965) 1244–1245.

[4] Brown, W.G. On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 (1966) 281-285.

[5] Chung, F., Graham, R., Sparse quasi-random graphs. Special issue: Paul Erdős and his mathematics. Combinatorica 22 (2002), no. 2, 217–244.

[6] de Caen, D., Székely, L.A. The maximum size of 4- and 6-cycle free bipartite graphs on m, n vertices. Sets, graphs and numbers (Budapest, 1991), 135-142, Colloq. Math. Soc. János Bolyai, 60, North-Holland, Amsterdam, 1992.

[7] Erdős, P. On the graph theorem of Turán. Matematikai Lapok 21 (1970) 249-251.

[8] Erdős, P., Gallai, T. On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar 10 (1959) 337–356.

[9] Erdős, P., Rényi, A., Sós, V.T. On a problem of graph theory. Studia Sci. Math. Hungar. 1 (1966) 215-235.

[10] Erdős, P., Simonovits, M. Compactness results in extremal graph theory. Combinatorica 2 (1982), no. 3, 275–288.

[11] Feit, W., Higman, G. The nonexistence of certain generalized polygons. J. Algebra 1 (1964) 114–131.

[12] Györi, E. C_{6}-free bipartite graphs and product representation of squares. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 371–375.

[13] Hoory, S. The size of bipartite graphs with a given girth. J. Combinatorial Theory (Ser B) 86 (2002) no. 2, 215-220.

[14] Kühn, D., Osthus, D. 4-Cycles in graphs with forbidden even cycles. To appear in Journal of Graph Theory.

[15] Lazebnik, F., Ustimenko, V. A., Woldar, A. J., Polarities and 2k-cycle-free graphs. Discrete Math. 197/198 (1999), 503–513.

[16] Peykre, L. P. An automorphism of the geometry of the group B_{2}(2^{n}) as a polynomial mapping. Ukrainian Math. J., v. 44, no. 11 (1992), 1530–1534 (in Russian).

[17] Sidorenko, A. F. Inequalities for functionals generated by bipartite graphs. (Russian) Diskret. Mat. 3 (1991), no. 3, 50–65; translation in Discrete Math. Appl. 2 (1992), no. 5, 489–504.

[18] Tits, J., Théorème de Bruhat et sous-groupes paraboliques. C. R. Acad. Sci. Paris 254 (1962), 2910–2912.