The size of bipartite graphs with girth eight

Stefan Neuwirth

Abstract

Reiman’s inequality for the size of bipartite graphs of girth six is generalised to girth eight. It is optimal in as far as it admits the algebraic structure of generalised quadrangles as case of equality. This enables us to obtain the optimal estimate e ∼ v^{4/3} for balanced bipartite graphs. We also get an optimal estimate for very unbalanced graphs.

1 Introduction

De Caen and Székely recently proposed a new bound for the size of a bipartite graph of girth eight, that is a bipartite graph without cycle of length four and six. We adapt their method to obtain the following cubic inequality.

Theorem 1.1. Let G be a bipartite graph on v + w vertices.

(i) If G contains no cycle of length 4 and 6, then its size e satisfies

e^{3} − (v + w)e^{2} + 2vwe − v^{2}w^{2} ⩽ 0.

(ii) If v ⩾ ⌊w^{2}/4⌋, then furthermore e ⩽ v + ⌊w^{2}/4⌋.

Part (i) is the right generalisation of Reiman’s inequality for bipartite graphs of girth 6 (see Prop. 3.1) to girth 8. It is optimal in the sense that it is an equality for all known extremal graphs constructed via finite fields. Part (ii) describes the case of very unbalanced bipartite graphs and is optimal: there is a graph, constructed by hand, for which it is an equality.

Let us give a brief description of this article. Section 2 describes a way to translate uncoloured graphs into bipartite graphs and its converse. This permits to get two propositions on very unbalanced graphs.

Section 3 summarises facts about bipartite graphs of girth six that should be folklore and well known although I did not see them printed.

Section 4 is the core of the paper. We adapt an inequality of Atkinson et al. to get an optimal lower bound on the number of paths of length 3 in a bipartite graph (Cor. 4.6). This enables us to bypass the final step in the proof of [5, Th. 1] and to get our theorem.

2 Uncoloured graphs and bipartite graphs

Expanding a graph to a bipartite graph

We propose the following construction of a bipartite graph out of an uncoloured graph. Let G′ be an uncoloured graph with set of vertices V. Then the bipartite graph G is defined as follows:

• the first class of vertices of G is V;

• the second class W of vertices of G is the set of edges of G′;

• the set of edges of G is { {x, y} : y is an edge of G′ with endpoint x }.

Thus every vertex of W has degree 2 and the size of G is twice the size of G′.

Contracting a bipartite graph to an uncoloured graph

Let us describe an inverse construction. Let G be a bipartite graph with colour classes V and W. Let G′ be the following graph:

• its set of vertices is V;

• its set of edges is { {x, z} ⊆ V : ∃y {x, y} and {z, y} are edges of G }.

The size of G′ is at most half the size of G. If G contains no cycle of length 4, then, given {x, z}, there is at most one y such that {x, y} and {z, y} are edges of G, so that the size of G′ is exactly

∑_{y∈W} \binom{d(y)}{2} ⩽ \binom{#V}{2} .  (1)

(We recognise here [3, Inequality (2), p. 310] for s = t = 2.) Thus each vertex y ∈ W of degree at least 2 contributes at least 1 to sum (1). This yields Proposition 2.1. Let G be a bipartite graph on v + w vertices that contains no cycle of length 4.

(i) If w > \binom{v}{2}, then there are at least w − \binom{v}{2} vertices in W of degree 0 or 1. (ii) If its minimal degree is at least 2, then w ⩽ \binom{v}{2} and v ⩽ \binom{w}{2}.

If G contains no cycle of length 4 nor 6, then G′ contains no triangle and its size is at most ⌊v^{2}/4⌋. This argument proves Proposition 2.2. Let G be a bipartite graph on v + w vertices that contains no cycle of length 4 or 6.

(i) If w > ⌊v^{2}/4⌋, then there are at least ⌈w − v^{2}/4⌉ vertices in W with degree 0 or 1. (ii) If its minimal degree is at least 2, then w ⩽ ⌊v^{2}/4⌋ and v ⩽ ⌊w^{2}/4⌋.

3 Bipartite graphs of girth six

The following estimate is well known as Reiman’s inequality, but its cases of equality were not written down explicitly. Reading the proof of [3, Th. VI.2.6], one gets with [2, Def. I.3.1] Proposition 3.1. Let v ⩽ w. A graph of girth at least 6 on v + w vertices with e edges satisfies

O(v, w, e) = e^{2} − we − vw(v − 1) ⩽ 0

e ⩽ \sqrt{vw(v − 1) + w^{2}/4} + w/2.

We have equality if and only if it is the incidence graph of a Steiner system S(2, k; v) on v points with block degree k given by wk(k − 1) = v(v − 1).

Note that by symmetry, we also get O(w, v, e) ⩽ 0, but this is superfluous by Lemma 3.2. Let v ⩽ w. Let e be the positive root of X^{2} − vX − vw(w − 1). Then O(v, w, e) ⩾ 0. Proof. As (vw)^{2} − vvw − vw(w − 1) = vw(vw − v − w + 1) ⩾ 0, we have e ⩽ vw. Therefore

e^{2} − we − vw(v − 1) = e^{2} − ve − vw(w − 1) + (v − w)e + vw(w − v)
= (vw − e)(w − v) ⩾ 0 .

Remark 3.3. The case of equality in Prop. 3.1 may be described further as follows. By [2, Cor. I.2.11], every vertex in V has same degree r and every vertex in W has same degree k with

k − 1 | v − 1 and k(k − 1) | v(v − 1),  (2)

so that v = 1 + r(k − 1) and k | r(r − 1). For given k, this set of conditions is in fact sufficient for the existence of an extremal graph for large r: this is Wilson’s Theorem [2, Th. XI.3.8]. For example, we have the following complete sets of parameters (v, w, r, k):

(1 + r(k − 1), r(1 + r(k − 1))/k, r, k) for 1 ⩽ k ⩽ 5 and k | r(r − 1).

The first set of parameters satisfying (2) for which an extremal graph does not exist is (36, 42, 7, 6). Consult [2, Table A1.1] for all known block designs with r ⩽ 17. [2, Table A5.1] provides the following sets of parameters (v, w, r, k) for block designs: given any prime power q and natural number n, given t ⩽ s,

( q^{n}, q^{n−1} \frac{q^{n} − 1}{q − 1} , \frac{q^{n} − 1}{q − 1} , q) , ( \frac{q^{n+1} − 1}{q − 1} , \frac{q^{n+1} − 1}{q^{2} − 1} \frac{q^{n} − 1}{q − 1} , \frac{q^{n} − 1}{q − 1} , q + 1) ,

(q^{3} + 1, q^{2}(q^{2} − q + 1), q^{2}, q + 1) , (2^{t+s} − 2^{s} + 2^{t}, (2^{s} + 1)(2^{s} − 2^{s−t} + 1), 2^{s} + 1, 2^{t}) .

The following proposition provides a simpler but coarser bound.

Proposition 3.4. Let G be a bipartite graph on vertex classes V and W with #V = v and #W = w without cycles of length 4. Its size satisfies

e ⩽ \{ \begin{matrix}\sqrt{2vw(v − 1)} & if w ⩽ v(v − 1)/2 \\ v(v − 1)/2 + w & otherwise. \end{matrix}

We have optimality in the second alternative for the bipartite expansion of a complete graph on V as described in Section 2, on which we add w − v(v − 1)/2 new edges by connecting any vertex of V to w − v(v − 1)/2 new vertices in colour class W.

Proof. By Proposition 2.1, if w > v(v − 1)/2, then w − v(v − 1)/2 vertices in W have degree 0 or 1. If we remove them, we remove at most w − v(v − 1)/2 edges and the remaining graph has at most v(v − 1) edges because O(v, v(v − 1)/2, v(v − 1)) = 0. The first alternative follows from

O(v, w, \sqrt{2vw(v − 1)}) = w\sqrt{v(v − 1)}(\sqrt{v(v − 1)} − \sqrt{2w}).

4 Bipartite graphs of girth eight

Statement of the theorem

Consult [8, Def. 1.3,1] for the definition of generalised polygons.

Theorem 4.1. Let G be a bipartite graph on vertex classes V and W with #V = v and #W = w. If G contains no cycle of length 4 or 6, then its size e satisfies

P (v, w, e) = e^{3} − (v + w)e^{2} + 2vwe − v^{2}w^{2} ⩽ 0.  (3)

We have equality exactly in two cases:

(i) if G is the complete bipartite graph and v = 1 or w = 1;

(ii) if G is the incidence graph of a generalised quadrangle.

Remark 4.2. Let us first note that this polynomial has exactly one positive root in e for positive v, w. It suffices to this purpose to show that its discriminant is negative. This is −v^{2}w^{2}D with

D = 27p^{2} + 4s^{3} − 36sp − 4s^{2} + 32p, s = v + w, p = vw.

Let us study this quantity for s ⩾ 2, p ⩾ s − 1. We have

\frac{dD}{dp} = 54p − 36s + 32 ⩾ 54p − 36(p + 1) + 32 = 18p − 4 > 0,

so that its minimum satisfies p = s − 1, which implies D = (4s − 5)(s − 1)^{2} ⩾ 3. Therefore Inequality (3) is equivalent to an inequality of form e ⩽ e(v, w).

Remark 4.3. The case of equality in Th. 4.1 implies the following: every vertex in V has same degree s + 1 and every vertex in W has same degree t + 1. By [8, Cor. 1.5.5, Th. 1.7.1], s + t | st(1 + st) and

v = (t + 1)(1 + st) , w = (s + 1)(1 + st) , e = (s + 1)(t + 1)(1 + st).

Let us suppose, by symmetry, that s ⩽ t. If s = 0, we get case (i). If s = 1, we obtain exactly the examples of extremal graphs produced by de Caen and Székely: W consists of t + 1 horizontal lines and as much vertical lines and V is the set of (t + 1)^{2} intersection points and G is the point-line incidence graph of this grid (this is also the bipartite expansion of a complete bipartite graph on (t + 1) + (t + 1) vertices.) Otherwise s, t ⩾ 2 and G is in fact the incidence graph of a generalised quadrangle, so that by [8, Th. 1.7.2], t ⩽ s^{2}. Let q be a prime power. Then there are generalised quadrangles with set of parameters (s, t) any of (q, q), (q, q^{2}), (q^{2}, q^{3}), (q − 1, q + 1); all known ones fit in this list. In particular, by [8, Th. 1.7.9], if t ⩾ s = 2, then t = 2 or t = 4 and in each case there is exactly one extremal graph. By [8, Sec. 1.7.11], if t ⩾ s = 3, then there is a (unique) extremal graph exactly if t = 3, 5, 9. There is a unique extremal graph with s = t = 4. It is open whether there exists a generalised quadrangle with s = 4 and t ∈ {11, 12}.

A generalisation of an inequality of Atkinson et al.

We first need an optimal lower bound on the number of paths of length 3. Let us prove the following inequality.

Theorem 4.4. Let (a_{ij} )_{1⩽i⩽v,1⩽j⩽w} be a matrix of nonnegative coefficients and ρ, γ ⩾ 0. Let

a_{i⋆} = ∑_{j=1}^{w} a_{ij} , a_{⋆j} = ∑_{i=1}^{v} a_{ij} , e = ∑_{i=1}^{n} ∑_{j=1}^{v} a_{ij} .  (4)

If a_{i⋆} ⩾ 2ρ and a_{⋆j} ⩾ 2γ, then

ϕ = ∑_{i=1}^{v} ∑_{j=1}^{w} a_{ij} (a_{i⋆} − ρ)(a_{⋆j} − γ) ⩾ e(e/v − ρ)(e/w − γ),  (5)

equality holding exactly if a_{i⋆} and a_{⋆j} are constant.

This refines the inequality in [1], which states

ψ = ∑_{i=1}^{v} ∑_{j=1}^{w} a_{ij} a_{i⋆}a_{⋆j} ⩾ e^{3}/vw  (6)

as, by the Arithmetic-Quadratic Mean Inequality,

ϕ − ψ = −γ ∑_{i=1}^{v} a_{i⋆}^{2} − ρ ∑_{j=1}^{w} a_{⋆j}^{2} + ργe ⩽ e(−γe/v − ρe/w + ργ)  (7)

Remark 4.5. If v = w and a is diagonal, Inequality (6) is the Arithmetic-Cubic Mean Inequality and Inequality (5) becomes

\frac{1}{v} ∑_{i=1}^{v} a_{ii} (a_{ii} − ρ)(a_{ii} − γ) ⩾ \frac{e}{v} \frac{e − vρ}{v} \frac{e − vγ}{v} ,

which is true by Chebyshev’s Inequality [7, Th. 43] if a_{ii} ⩾ ρ and a_{ii} ⩾ γ. For our “non commutative Chebyshev Inequality”, the conditions a_{i⋆} ⩾ 2ρ and a_{⋆j} ⩾ 2γ cannot be weakened to a_{i⋆} ⩾ ρ and a_{⋆j} ⩾ γ, as we have the following counterexamples:

( \begin{matrix}2 & 5 \\ 4 & 0 \end{matrix}) , ( \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix}) .

Proof. If (5) is an equality, then so are (7) and (6) and our case of equality follows from the identical case of equality in [1], whose proof we now imitate. We shall suppose that a_{i⋆} > 2ρ or a_{⋆j} > 2γ, so that the whole inequality follows by continuity. Fix e and suppose that under this condition the a_{ij} are chosen so to minimise ϕ. We may suppose that the rows and the columns have been permuted such that the sequences (a_{i⋆}) and (a_{⋆j} ) are nondecreasing:

a_{1⋆} ⩽ … ⩽ a_{v⋆}, a_{⋆1} ⩽ … ⩽ a_{⋆w} .  (8)

If one of these sequences is constant, the inequality follows by the Arithmetic-Quadratic inequality (and the case of equality is easy). Let us suppose that this is not so.

One can suppose that a_{1w} and a_{v1} are positive. Let us show the argument for a_{1w}. If a_{1w} = 0, there are k, l such that a_{1k}, a_{lw} > 0. Make a perturbation by adding α to a_{1w} and to a_{lk} and subtracting α to a_{1k} and to a_{lw}. The row and column sums a_{i⋆} and a_{⋆j} are unaltered and ϕ increases of

Δϕ = α((a_{1⋆} − ρ)(a_{⋆w} − γ) + (a_{l⋆} − ρ)(a_{⋆k} − γ)
− (a_{1⋆} − ρ)(a_{⋆k} − γ) − (a_{l⋆} − ρ)(a_{⋆m} − γ))
= α(a_{1⋆}a_{⋆w} + a_{l⋆}a_{⋆k} − a_{1⋆}a_{⋆k} − a_{l⋆}a_{⋆w})
= α(a_{1⋆} − a_{l⋆})(a_{⋆w} − a_{⋆k}),

so that ϕ does not increase.

Now make the following perturbation: add 2α to a_{11} and subtract α to a_{1w} and to a_{v1}. Let us compute the differential of ϕ: as

\frac{dϕ}{da_{rc}} = (a_{r⋆} − ρ)(a_{⋆c} − γ) + ∑_{i=1}^{v} a_{ic}(a_{i⋆} − ρ) + ∑_{j=1}^{w} a_{rj} (a_{⋆j} − γ),

dϕ = dα( 2\frac{dϕ}{da_{11}} − \frac{dϕ}{da_{1w}} − \frac{dϕ}{da_{v1}} )
= dα( (a_{1⋆} − ρ)(a_{⋆1} − a_{⋆w}) + (a_{1⋆} − a_{v⋆})(a_{⋆1} − γ) + ∑_{i=1}^{v} a_{i1}(a_{i⋆} − ρ)

+ ∑_{j=1}^{w} a_{1j} (a_{⋆j} − γ) − ∑_{i=1}^{v} a_{iw} (a_{i⋆} − ρ) − ∑_{j=1}^{w} a_{vj} (a_{⋆j} − γ))

For positive dα, we have by (8)

dϕ ⩽ dα((a_{1⋆} − ρ)(a_{⋆1} − a_{⋆w}) + (a_{1⋆} − a_{v⋆})(a_{⋆1} − γ) + a_{⋆1}(a_{v⋆} − ρ)
+ a_{1⋆}(a_{⋆w} − γ) − a_{⋆w} (a_{1⋆} − ρ) − a_{v⋆}(a_{⋆1} − γ))
= dα((a_{1⋆} − 2ρ)(a_{⋆1} − a_{⋆w}) + (a_{⋆1} − 2γ)(a_{1⋆} − a_{v⋆}))
< 0 ,

which contradicts the minimum hypothesis.

Corollary 4.6. Let G be a bipartite graph on v + w vertices and of minimal degree 2. Then the number of paths of length 3 in G is at least e(e/v − 1)(e/w − 1). This bound is achieved exactly if the graph is regular for each of its two colours.

Proof. A path of length 3 is a sequence of 4 vertices (x, y, z, t) with no repetition such that

{x, y}, {y, z}, {z, t} ∈ G.

Given two adjacent vertices y and z, the number of paths (x, y, z, t) makes (d(y) − 1)(d(z) − 1), where d denotes the degree of a vertex. Therefore the number of all paths of length 3 is

∑_{{y,z}∈G} (d(y) − 1)(d(z) − 1).

Let (a_{ij} )_{1⩽i⩽v,1⩽j⩽w} be the reduced incidence matrix of G: a_{ij} = 1 if the ith vertex of the first class is adjacent to the jth vertex of the second class; otherwise a_{ij} = 0. Then this sum is

∑_{i=1}^{v} ∑_{j=1}^{w} a_{ij} (a_{i⋆} − 1)(a_{⋆j} − 1),  (9)

so that it suffices to take ρ = γ = 1 in Th. 4.4.

Proof of Theorem 4.1

The case of equality follows from [8, Lemma 1.4.1] because its axiom (i) is exactly what makes Bound (10) an equality.

I now follow the proof of [5, Th. 1]. If G contains no cycle of length 4, there is no path of length 3 between two adjacent vertices; if G contain no cycle of length 6, there is at most one path of length 3 between non-adjacent vertices of different colour. Therefore the sum (9) is bounded by

vw − e with e = ∑_{i=1}^{n} ∑_{j=1}^{v} a_{ij} .  (10)

By Corollary 4.6, if all the vertices of G have degree at least two, one has

vw − e ⩾ e^{3}/vw − (1/v + 1/w)e^{2} + e

and therefore (3). In order to get rid of this degree condition, we have to do an induction on the sum s = v + w of the number of columns and the number of rows of the incidence matrix. If v = 1, then P (v, w, e) = (e − w)(e^{2} − e + w), so that the inequality states e ⩽ w, which is trivial; symmetrically for w = 1. Suppose the result is true for all v × w incidence matrices with v + w = s. Consider now a v × w incidence matrix with v + w = s + 1 and v, w ⩾ 2. If each vertex has degree at least two, the result is true; otherwise there is a column or a row containing only zeroes or exactly one “1”. Apply the induction hypothesis on the matrix without this row or column: we get P (v − 1, w, e − 1) ⩽ 0 or P (v, w − 1, e − 1) ⩽ 0 and we may apply the following growth lemma to conclude.

Lemma 4.7. Let v, w ⩾ 1. If P (v, w, e) ⩽ 0, then P (v + 1, w, e + 1) ⩽ 0.

Proof. In fact, one has

P (v + 1, w, e + 1) − P (v, w, e) = 2e^{2} + (1 − 2v)e + (w − w^{2})(2v + 1) − v,

which is negative as long as

0 ⩽ e ⩽ e_{0} =(2v − 1 + \sqrt{(2v + 1) (2v + 8w^{2} − 8w + 1)} )/4 = (2v − 1 + Δ)/4.

Let us use that P (v, w, e) has a unique root in e and compute P (v, w, e_{0}). This makes

(4vw^{2} + 2w^{2} + 1)Δ/16 + (−16vw^{3} − 8v^{2}w^{2} − 8w^{3} + 8vw^{2} + 2w^{2} − 2v + 4w − 1)/16.

Then either the second term in this sum is positive and P (v, w, e_{0}) is positive, or the conjugate expression of this sum is positive, and the product of the sum with this conjugate expression is

(w − 1)^{2}w^{2}(8v^{3}w^{2} + 4v^{2}w^{2} − 2vw^{2} + 2v^{2} − w^{2} − 4vw + 2v − 2w)/8,

which is positive if v, w ⩾ 1.

Further remarks

Remark 4.8. Theorem 4.1 does not always give the right order of magnitude for the maximal size of a graph of girth 8: as

P (v, w, (vw)^{2/3} ) = 2(vw)^{5/3} − (vw)^{4/3} (v + w)) ⩽ 2(vw)^{5/3} − 2(vw)^{4/3+1/2} ⩽ 0,

we expect to find maximal graphs of size (vw)^{2/3} : De Caen and Székely [5, Th. 4] find a counterexample to this expectation if v “lies in an interval just slightly below” w^{2}. They conjecture [4] that this is the case as soon as v ≫ w^{5/4} and v ≪ w^{2}.

In the case of v = w, let us give the following approximation for the real root of the polynomial. For

e = v^{4/3} + \frac{2}{3}v − \frac{2}{9}v^{2/3} − \frac{20}{81}v^{1/3} ,

P (v, v, e) = \frac{40}{243}v^{7/3} + \frac{376}{2187}v^{2} − \frac{80}{2187}v^{5/3} − \frac{800}{19683}v^{4/3} − \frac{8000}{531441}v ⩾ \frac{129808}{531441},

P (v, v, e − 16/81) = −\frac{8}{531441}(v^{1/3} − 1)(39366v^{7/3} + 28431v^{2} + 8262v^{5/3}
− 8748v^{4/3} − 11880v − 6560v^{2/3} − 2432v^{1/3} − 512)
⩽ 0.

In particular,

Corollary 4.9. Let G be a bipartite graph of size e with v vertices in each vertex class. If the girth of G is at least 8, then

e < v^{4/3} + \frac{2}{3}v − \frac{2}{9}v^{2/3} − \frac{20}{81}v^{1/3} .

Let us now show that we generalise the following estimations for the size of bipartite graphs of girth 8 in [5, Th. 1]:

(i) if the minimal degree of G is at least 2, then e ⩽ 2^{1/3} (vw)^{2/3} ;

(ii) if v ≼ w^{2} or w ≼ v^{2}, then e ≼ (vw)^{2/3} .

In fact,

P (v, w, 2^{1/3} (vw)^{2/3} ) = (vw)^{4/3} (w^{2/3} − 2^{2/3} v^{1/3} )(v^{2/3} − 2^{2/3} w^{1/3} ),

which is nonnegative exactly if v ⩽ w^{2}/4 and w ⩽ v^{2}/4 or if (v, w) is among {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}, and this is the case by Prop. 2.2 if the minimal degree is at least 2.

Furthermore, by Prop. 2.2, if w > ⌊v^{2}/4⌋, then ⌈w − v^{2}/4⌉ vertices in W have degree 0 or 1. If we remove them, we remove at most ⌈w − v^{2}/4⌉ edges and the remaining graph has at most ⌊v^{2}/2⌋ edges because P (v, ⌊v^{2}/4⌋, ⌊v^{2}/2⌋ + 1) > 0. This yields

Proposition 4.10. Let G be a bipartite graph on vertex classes V and W with #V = v and #W = w without cycles of length 4 and 6. Its size satisfies

e ⩽ \{ \begin{matrix}2^{1/3} (vw)^{2/3} & if max(v, w) ⩽ ⌊min(v, w)^{2}/4⌋ \\ ⌊min(v, w)^{2}/4⌋ + max(v, w) & otherwise. \end{matrix}

We have optimality in the second alternative: make a bipartition V = V_{1} ∪ V_{2} with V_{1} = ⌈v/2⌉ and V_{2} = ⌊v/2⌋, let G′ be the complete bipartite graph on the colour classes V_{1} and V_{2}, which has ⌊v^{2}/4⌋ edges. Now consider the bipartite expansion of G′, add ⌈w − v^{2}/4⌉ new vertices to colour class W, and connect each of them to some vertex of V.

Note that this estimate yields another proof of [6, Th. 1] by means of [6, Th. 3].

Remark 4.11. Our inequality condenses the following facts about the behaviour of e for fixed w and large v. If w ⩽ 3, then extremal graphs of girth 8 do not contain any cycle at all, so that their size is e = v + w − 1; if v ⩾ w = 4 and if v = w = 5, then extremal graphs of girth 8 contain exactly one cycle, so that their size is e = v + w; if v > w = 5, then extremal graphs of girth 8 contain exactly one “θ-graph”, so that their size is e = v + w + 1.

Bibliography

[1] F. V. Atkinson, G. A. Watterson, and P. A. P. Moran. A matrix inequality. Quart. J. Math. Oxford Ser. (2), 11:137–140, 1960. (pp. 4 and 5).

[2] T. Beth, D. Jungnickel, and H. Lenz. Design theory. Cambridge University Press, seconde edition, 1999. (pp. 2 and 3).

[3] Béla Bollobás. Extremal graph theory. Academic Press, 1978. (p. 2).

[4] D. de Caen and L. A. Székely. The maximum size of 4- and 6-cycle free bipartite graphs on m, n vertices. In Sets, graphs and numbers (Budapest, 1991), pages 135–142. North-Holland, 1992. (p. 7).

[5] D. de Caen and L. A. Székely. On dense bipartite graphs of girth eight and upper bounds for certain configurations in planar point-line systems. J. Combin. Theory Ser. A, 77(2):268–278, 1997. (pp. 1, 6, and 7).

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

[7] G. H. Hardy, J. E. Littlewood, and G. Pólya. Inequalities. Cambridge Univ. Press, seconde edition, 1952. (p. 5).

[8] H. van Maldeghem. Generalized polygons. Birkhäuser Verlag, 1998. (pp. 3, 4, and 6).