The University of New South Wales

School of Mathematics Department of Pure Mathematics

CYCLES OF EVEN LENGTH IN GRAPHS

by

Thomas Lam

Thesis Supervisor: Prof. T. Tao Co-supervisor: Prof. M. Cowling

A thesis submitted for consideration in the degree of Bachelor of Science with Honours in Pure Mathematics at the

University of New South Wales

June 2001

Acknowledgements

The foremost thanks go to Professor Tao who provided the problems for my study, inspired all my creative thought and gave me continual support and help throughout my thesis year.

Next I would like to thank Professor Cowling for supervising me in Professor Tao’s absence and coping with my very irregular requests.

I would like to thank my family for their patience during my thesis writeup and tolerating my peculiar work schedules.

Lastly, I would like to thank my friends for their curiosity in my thesis and their subsequent befuddled looks when I attempt to explain.

Contents

Introduction 3

1 Preliminary Discussion 5 1.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Adjacency matrices, rook moves and other definitions 8

2.1 Adjacency matrices . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.1 Adjacency matrices for bipartite graphs . . . . . . . . . 9 2.1.2 Cycles and paths within adjacency matrices . . . . . . 9

3 Graphs with cycles of particular length 11 3.1 Pancyclic graphs . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Woodall’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 Even cycles and bipartite graphs . . . . . . . . . . . . . . . . . 16

4 Graphs without cycles of even length 19 4.1 Introduction to problem . . . . . . . . . . . . . . . . . . . . . 19 4.2 Bondy and Simonovits’ proof . . . . . . . . . . . . . . . . . . 20 4.3 Recent progress on the upper bound . . . . . . . . . . . . . . 25 4.4 Lower Bound constructions . . . . . . . . . . . . . . . . . . . . 27

4.4.1 Projective planes and the C_{4} problem . . . . . . . . . . 28 4.4.2 Benson’s construction . . . . . . . . . . . . . . . . . . 32 4.4.3 Wenger’s construction . . . . . . . . . . . . . . . . . . 34

4.5 Minimal regular graphs . . . . . . . . . . . . . . . . . . . . . . 36 4.6 More recent lower bound constructions . . . . . . . . . . . . . 40 4.7 A number theoretic application . . . . . . . . . . . . . . . . . 41

5 Original results 43 5.1 A heuristic argument . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 A combinatorial lemma . . . . . . . . . . . . . . . . . . . . . . 45 5.2.1 Example: Matrices without rectangles . . . . . . . . . 46 5.2.2 Example: Matrices without hexagons . . . . . . . . . . 47

5.3 The inductive approach . . . . . . . . . . . . . . . . . . . . . . 48 5.4 The case 4n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.5 Non-bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . 56

5.5.1 Upper bound . . . . . . . . . . . . . . . . . . . . . . . 56 5.5.2 Lower bound . . . . . . . . . . . . . . . . . . . . . . . 62

5.6 Improving the hexagon case . . . . . . . . . . . . . . . . . . . 63 5.7 Conjectures and discussion . . . . . . . . . . . . . . . . . . . . 68

6 Non-self-crossing hexagons 72 6.1 Cauchy-Schwarz Inequality . . . . . . . . . . . . . . . . . . . . 74 6.2 Proof of Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

Introduction

This thesis concerns itself with problems in Extremal Graph Theory. Bollobás [6] describes extremal graph theory thus:

In extremal graph theory one is interested in the relations between the various graph invariants, such as order, size, connectivity, minimum degree, maximum degree, chromatic number and diameter, and also in the values of these invariants which ensure that the graph has certain properties.

Often one is interested in particular properties which guarantee another property for a graph. The graphs with extreme values of the former properties are of most interest and are known as extremal graphs. The most important example of an extremal problem is to determine the maximum number of edges in a graph of order n not containing a fixed graph G. In fact, most of the questions in which this thesis will be investigating will be similar to or be a generalisation of this kind of problem.

In Chapter 1, we will give the basic definitions concerning graphs that we will be using in the rest of the thesis. We will concentrate especially on definitions involving cycles and paths as those will be of particular interest to us later. In Chapter 2, we will introduce an alternative formulation of a graph as an adjacency matrix and also define the rook move which we will be using extensively in proofs and discussions throughout the later chapters. Chapter 3 focuses our attention on cycles within graphs. We ask how many edges ensure a graph of particular order contain cycles of many lengths or cycles of particular lengths. We prove Bondy’s theorem on pancyclic graphs. We state Woodall’s theorem which answers completely the question of when a graph contains all cycles of length 3 ≤ r ≤ l.

In Chapter 4, we move onto the question of cycles of even length in graphs. We give Bondy and Simonovits’ proof and generalisation of Erdős’ original conjecture, followed by some recent improvements to particular cases of the theorem. We then give Benson’s and Wenger’s constructions which provide the corresponding lower bound for the result in certain cases. We explain some connections between this area and the study of minimal regular graphs with particular girth. We finish the chapter with Erdős’ number theoretic problem which inspired his work on this problem and his original conjecture.

Chapter 5 is the central chapter of the thesis where we give an exposition of all the original work, some of which is to appear in [29] . Our aim is essentially to improve Bondy and Simonovits’ proof in a particular case as to show that Benson and Wenger’s constructions are optimal in some sense. We make much use of a Combinatorial Lemma of Katz and Tao and give examples first of its crude use on graphs without rectangles and hexagons. The results we prove begin with the bipartite graph case, which we extend in a later section to general graphs. We describe methods which appear to be superior in specific instances and apply them. The chapter concludes with a number of conjectures.

Chapter 6 tackles a slightly different question of matrices without nonself-crossing hexagons. Some ideas, such as the rook move, are remarkably similar to those in Chapter 5, but the combinatorial techniques used are vastly different. We follow Katz’s proof throughout this section with a few changes. Lastly, we describe an application of results of this type.

Chapter 1

Preliminary Discussion

1.1 Basic definitions

This section will introduce a number definitions involving graphs and the assumptions we will be making throughout the thesis.

Definition 1.1.1. A graph G is an ordered pair of disjoint sets (V, E) such that E is a subset of the set of unordered pairs of V.

Definition 1.1.2. The set V is the set of vertices and the set E is the set of edges. Given a graph G, these are denoted V (G) and E(G). The number of vertices is known as the order of G and is denoted v(G). The number of edges is the size of G and is denoted e(G). The notation G = G(n, m) denotes a graph with order n and size m. The notation G = G(V, E) denotes a graph with vertex set V and edge set E.

Definition 1.1.3. An edge e = (v, w) is said to join v and w. Two vertices are considered adjacent if an edge joins them.

Definition 1.1.4. The degree of a vertex v is the number of other vertices adjacent to it, denoted by d(v). Let δ(G) denote the minimum degree of any vertex in G.

Definition 1.1.5. H is a subgraph of G if E(H) ⊂ E(G) and V (H) ⊂ V (G). We write H ⊂ G.

Definition 1.1.6. Let G = (V, E) be a graph and suppose W ⊂ V. Then the subgraph spanned or induced by W is the graph with vertex set W and edge set E′ ⊂ E where E′ contains all the edges of E with vertices contained in W.

Definition 1.1.7. A directed graph is one where the edge set is composed of ordered pairs of vertices.

Definition 1.1.8. A multigraph is a graph in which we allow the edge set to be a multiset, that is, more than one edge may join two vertices. These edges are called multiedges.

Definition 1.1.9. A loop is an edge of the form (v, v) where v is in the vertex set of G.

Throughout this thesis, we will only be considering graphs which are not directed and which do not have loops or multiedges.

Definition 1.1.10. A graph G = (V, E) is bipartite if V is the disjoint union of non-empty vertex sets V_{1} and V_{2} such that every edge in E joins a vertex in V_{1} to one in V_{2}.

Definition 1.1.11. Two graphs G = (V, E) and H = (W, F) are isomorphic if there exists a bijection f : V → W such that for all v_{0}, v_{1} ∈ V, (v_{0}, v_{1}) ∈ E if and only if (f(v_{0}), f(v_{1})) ∈ F. We write simply G = H (or G ≅ H).

Definition 1.1.12. The complete graph of order n, K(n) has n vertices which are all adjacent to each other. The complete bipartite graph, denoted K(n, m), is the graph (V = V_{1}∪V_{2}, E) such that every vertex in V_{1} is adjacent to every vertex in V_{2} and |V_{1}| = n, |V_{2}| = m.

Definition 1.1.13. If G = (V, E) is a graph and U ⊂ V then G − U is the graph (V/U, E′) where E′ is obtained from E by removing any edge connected to any vertex in U.

1.2 Paths and cycles

Definition 1.2.1. A path is a sequence of vertices P of the form

(v_{0}, v_{1}, …, v_{l})

such that v_{i} is adjacent to v_{i+1} for every 0 ≤ i ≤ l − 1, and if v_{i} = v_{j} then i = j. The length of the path is the number l above. We say the path goes from v_{0} to v_{l}. A path of length l is denoted P_{l}.

Definition 1.2.2. A walk W in G is a sequence of vertices (v_{0}, v_{1}, …, v_{l}) such that v_{i} is adjacent to v_{i+1} for i ∈ [1, l − 1]. As with a path the walk has length l and goes from v_{0} to v_{l}.

Note that a path is just a walk with distinct vertices.

Definition 1.2.3. A cycle is a path with the difference that v_{0} = v_{l} and its length is the same as the corresponding path. The cycle of length l is denoted C_{l}. For simplicity, we will call a C_{3}, C_{4}, C_{5} and C_{6} a triangle, a rectangle (or quadrilateral), a pentagon and a hexagon respectively.

Definition 1.2.4. The distance between two vertices v and w is the length of the shortest path, if it exists, from v to w. If no such path exists, the distance is infinite. We denote the distance by d(v, w).

Definition 1.2.5. The diameter of G = (V, E) is the maximum distance between two vertices, max_{x,y∈V} {d(x, y)}.

Definition 1.2.6. A graph G = (V, E) is connected if for every two vertices v_{1} and v_{2} in V, there is a path P which goes from v_{1} to v_{2}. A maximal connected subgraph of G is called a component.

Definition 1.2.7. A graph without cycles is called a forest. A connected graph without cycles is called a tree.

Definition 1.2.8. The length of the shortest cycle in a graph G is called its girth. The length of the longest cycle in a graph G is called its circumference and is denoted by c(G).

Adjacency matrices, rook moves and other definitions

2.1 Adjacency matrices

It is possible to represent a graph with a matrix. Let G = (V, E) be a graph. Let v_{1}, v_{2}, …, v_{N} be the vertices in V. Then G can be represented by a N × N matrix M,

M_{ij} = \begin{cases}1 & if (v_{i}, v_{j}) ∈ E \\ 0 & otherwise. \end{cases}

Undirected graphs result in symmetric matrices. Graphs with multiedges can be represented by matrices with entries other than 1 or 0. Graphs without loops have vanishing diagonal entries.

One of the major uses of adjacency matrices is to calculate the number of paths between two vertices in a graph of a particular length. M_{ij} gives the number of paths from v_{i} to v_{j} which are of length 1. A short calculation will verify that (M^{2})_{ij} is the number of walks from v_{i} to v_{j} which are of length 2. Furthermore, (M^{n})_{ij} is the number of walks from v_{i} to v_{j} which are of length n. Thus adjacency matrices are a natural way to perform certain calculations in graphs, especially directed graphs, as those are taken into account automatically. This, however, is not the reason we will be using adjacency matrices.

2.1.1 Adjacency matrices for bipartite graphs

Let G be a bipartite graph with vertex sets V and W. Let the vertices in V and W be v_{1}, …, v_{K} and w_{1}, …, w_{L} respectively. Then a more concise matrix representation of G is the K × L matrix M with entries defined by:

M_{ij} = \begin{cases}1 & if (v_{i}, w_{j}) ∈ E \\ 0 & otherwise. \end{cases}

Unlike the previous type of adjacency matrices, this one has no redundancy– there is a one to one correspondence between bipartite graphs with parts of size K and L, and K × L matrices with entries in {0, 1}.

2.1.2 Cycles and paths within adjacency matrices

The latter type of adjacency matrix is the form we will be using to prove most of the original results in this thesis. It is worthwhile to look at what cycles and paths correspond to in the matrix formulation.

A cycle of length 2k in a bipartite graph G with corresponding matrix M is represented by a 2k sided ‘polygon’ in M such that:

1. The vertices of the polygon are entries with a 1 in M.

2. Two ‘adjacent’ vertices of the polygon belong to the same row or column of M. That is, the sides of the polygon are vertical or horizontal.

3. No three vertices belong to the same row or column.

Note that if the sides are drawn to connect the vertices of the polygon, the polygon is usually not convex, and usually self-crossing.

Walks correspond to particular kinds of rook moves in the matrix M. We will be using the following definition.

Definition 2.1.1. Suppose A is a matrix of 1s and 0s as above. A position in A are the coordinates (i, j) of a matrix entry A_{ij}. We write (i, j) ∈ A and say (i, j) contains a 1 or 0 depending on whether A_{ij} is 1 or 0. A rook move of length n is a vector of positions (x_{0}, x_{1}, …, x_{n}) such that x_{k} = (i_{k}, j_{k}) ∈ A satisfying the conditions:

1. Every position x_{i} contains a 1.

2. The positions x_{i} and x_{i+1} belong in either the same column or the same row, and this alternates, depending only on the parity of i. If x_{0} and x_{1} belong in the same column then the rook move is said to begin vertically, otherwise it begins horizontally.

We say that x_{n} can be reached from x_{0} by a rook move of length n. If x_{i} = x_{i+1} for some 0 ≤ i ≤ n − 1 then the rook move is called degenerate. Otherwise, it is called non-degenerate.

As it stands, a non-degenerate rook move corresponds to a walk, but not necessarily a path. The following is a rook move of length 4, (a_{0}, a_{1}, a_{2}, a_{3}, a_{4}):

a_{0}  a_{1} a_{2}  a_{3} a_{4}

Here is a degenerate rook move, also of length 4:

a_{0}  a_{1} = a_{2}  a_{3} a_{4}

There are a number of reasons why the matrix formulation of a graph is useful. One is when analysing a particular example for cycles, we have no problem with needing to draw edges over each other but we can still recognise cycles as easily in the matrix form. We also have shorthand words which can be used automatically: a row is simply a vertex in V while a column is a vertex in W. A non-zero position or simply an entry in the matrix corresponds to an edge.

Graphs with cycles of particular length

As mentioned in the introduction, a standard extremal graph theory problem is to find conditions which ensure that a graph G will always have or not have a particular graph H as a subgraph. We will be particularly interested in the case when the subgraph H is a cycle. The most common type of result we will hope to obtain is as follows:

If a graph G has n vertices and at least m = f(n) edges then it will contain a cycle of length l.

So basically, for each value of l we seek a function f(n). Of course, there are often many ways to rephrase the statement such as

If a graph G has n vertices and no cycles of length l then it contains less than m = f(n) edges.

We will be switching between these two different types of phrasings quite often.

Theorem 3.0.2. A tree of order n has n − 1 edges.

Proof. We shall prove this by induction. The result is clearly true for n = 1. Suppose we have proved the result for n = k. Let T be a tree of order k + 1.

Suppose every vertex in T has degree greater than or equal to 2. Take any vertex v_{0} and start constructing any path from v_{0} by picking an edge (v_{0}, v_{1}) at random and continuing from v_{1}. Since T has no cycles and each vertex is of degree greater than or equal to 2, we must always be able to continue this process. But this contradicts the assumption that T has finite order k + 1. Hence there is some vertex v which has degree less than 2.

The vertex v cannot have degree 0 since T is connected. Thus v has degree 1. Remove v (and the connecting edge) from G and apply the inductive hypothesis. This proves that the size of T is k and completes the induction.

Corollary 3.0.3. A forest of order n with c components has size n − c.

Proof. Just apply Theorem 3.0.2 to each component and the result follows immediately.

These results can also be phrased in the form: Every graph of order n with n or more edges must contain a cycle.

3.1 Pancyclic graphs

The previous section gives restrictions to the size of a graph which does not have any cycles. We now investigate graphs which have many cycles.

Definition 3.1.1. A graph G of order n is called pancyclic if it contains cycles of all lengths r, 3 ≤ r ≤ n.

Definition 3.1.2. A Hamiltonian-cycle in a graph of order n is a cycle of length n. A graph which contains a Hamiltonian-cycle is called Hamiltonian.

Theorem 3.1.3. Suppose G = G(n, m) is Hamiltonian and m ≥ n^{2}/4. Then either G is pancyclic or else G = K(n/2, n/2).

The following proof is taken from [5].

Proof. We will prove this by induction. If n ≤ 3 there is nothing to prove, so assume n > 3 and that the result is true for smaller values of n.

We now divide the proof into two cases.

Case 1: Suppose G contains a cycle C of length n − 1 and let the vertex not on C be v.

If the degree of v is greater than or equal to n/2 then clearly amongst the vertices adjacent to v we can always find two, x and y, which are distance r apart in C, for every r ∈ [1, (n − 1)/2] (this is a simple application of the pigeon hole principle). Now consider the cycles

(x, v, y, v_{1}, v_{2}, …, v_{r−1}, x)

of length r + 2 and the cycle using x, v, y but going the other way around C which has length n − r + 1. As r varies we cover all required cycle lengths and thus G is pancyclic.

If d(v) ≤ (n−1)/2 then we consider the graph G−{v} which has at least

\frac{n^{2}}{4} − \frac{n − 1}{2} > \frac{(n − 1)^{2}}{4}

edges and order n − 1. By the induction hypothesis this graph has all cycles of length 3 ≤ l ≤ n − 1. Thus G is pancyclic in this case as well.

Case 2: Suppose then that G has no cycle of length n − 1. Let the Hamiltonian cycle in G be (v_{0}, v_{1}, …, v_{n−1}, v_{0}) and for convenience we use the indices modulo n. Thus v_{i} is adjacent to v_{i+1} and v_{i−1} for all i.

We observe that

(v_{i}, v_{k}) and (v_{i+1}, v_{k+2}) cannot both be edges in G

for otherwise (v_{i}, v_{k}, v_{k−1}, …, v_{i+1}, v_{k+2}, v_{k+3}, …, v_{i}) would be a cycle of length n − 1 in G. For a fixed i, we consider all pairs (v_{i}, v_{j}) and (v_{i+1}, v_{j}). Clearly from our observation only half of these edges can be in G. Thus

d(v_{i}) + d(v_{i+1}) ≤ n.  (3.1)

Summing over i and dividing by the number of times each edge is counted we conclude that m ≤ n^{2}/4. In fact it is clear that for every i and k

exactly one of (v_{i}, v_{k}) and (v_{i+1}, v_{k+2}) is an edge in G  (3.2)

Hence we must have m = n^{2}/4 and n must be even with equality in (3.1). If the edges in G are exactly those (v_{i}, v_{j}) where i and j have different parity then we get the complete bipartite graph K(n/2, n/2).

Suppose otherwise and let s be the smallest even natural number for which G contains an edge of the form (v_{i+1}, v_{i+1+s}). From (3.2), we see that (v_{i}, v_{i−1+s}) is not an edge in G, so s ≥ 4 since (v_{i}, v_{i+1}) is in G. In turn this implies that (v_{i−1}, v_{i−3+s}) is an edge in G, but this contradicts the choice of s as the smallest even natural number with that property (here, s − 2 works).

The previous theorem required the graphs to contain a Hamiltonian cycle. Let us see what we can get without that requirement. First we require a theorem concerning the circumference of a graph which was first proven in [7] by Bondy but can also be found in Bollobás [5].

Theorem 3.1.4. Let C be a cycle of maximum length c in G = G(n, m) (length equal to circumference). Then there are at most

\frac{1}{2}c(n − c)

edges of G with at most one end vertex on C.

Proof. This proof requires a number of results concerning the circumference of a graph which is of less interest to us, and so will be omitted. See [7] or [5, p. 141].

Combining the last two theorems gives us this useful corollary: Corollary 3.1.5. If G = G(n, m) and m > n^{2}/4, then G contains a cycle of length r for every 3 ≤ r ≤ c(G). Proof. Let C be a cycle of length c(G). From Theorem 3.1.4 there are at most \frac{1}{2}c(n − c) edges of G with at most one end vertex on C. Removing these edges we obtain a graph H with order c more than

\frac{n^{2}}{4} − \frac{1}{2}c(n − c) ≥ \frac{c(2n − c)}{4} − \frac{1}{2}c(n − c) = \frac{c^{2}}{4}

edges. Applying Theorem 3.1.3 we see that H is pancyclic and contains all cycles of length 3 ≤ r ≤ c(G).

3.2 Woodall’s Theorem

More generally, one might hope to determine the function e(n, l) defined thus: any graph G(n, e(n, l)) contains a cycle of length r whenever 3 ≤ r ≤ l. This was completely solved by Woodall [48] (and some preexisting theorems).

In fact, Woodall calculated the function e(n, l, δ) which gave the minimum number of edges which ensures that any graph with n vertices and minimum degree δ to contain all the cycles of length r for 3 ≤ r ≤ l:

Theorem 3.2.1. Let \frac{1}{2} ≤ l ≤ n and s = n − l.

1. If n − l + 1 ≤ δ ≤ l/2, then e(n, l, δ) is the maximum of the following three values:

\binom{n − δ}{2} + \binom{δ + 1}{2}, \binom{l − δ}{2} + δ(δ + n − l), \binom{[l/2]}{2} + ⌊l/2⌋(n − ⌈l/2⌉),

where the last value is considered only if l is odd.

2. If δ ≤ n − l + 1 = s + 1, then

e(n, l, δ) = max \{\binom{l − 1}{2}, \binom{n − l}{2}\} .

Proof. Omitted. See Woodall [48] or Bollobás [5, pp. 153–155].

Erdős proved the following theorem in [14]:

Theorem 3.2.2. Let G(n, m) be a graph with n ≥ 3, and suppose that either δ = δ(G) ≥ n/2 or

m > max \{\binom{n − δ}{2} + δ^{2}, \binom{⌊(n + 2)/2⌋}{2} + ⌊(n − 1)/2⌋^{2}\} .

Then G is Hamiltonian.

Combining Theorems 3.1.3, 3.2.2 and 3.2.1, we can easily get:

Theorem 3.2.3.

e(n, l) = \begin{cases}⌊n^{2}/4⌋ & if l < (n + 3)/2 \\ \binom{l−1}{2} + \binom{n−l+2}{2} & if l ≥ (n + 3)/2. \end{cases}

3.3 Even cycles and bipartite graphs

So far we have not discriminated between cycles of even and odd length. However, the astute observer will notice that for a graph G(n, m), with m ≤ n^{2}/4, we can say nothing about the existence of cycles of odd length without additional constraints. The extremal graph K(n/2, n/2) has no cycles of odd length and has n^{2}/4 edges. When m ≥ n^{2}/4, Theorem 3.2.3 is nearly all that can be said about the presence of cycles.

On the other hand, there is quite a bit to be said about the existence of cycles of even length even when m << n^{2}/4, especially when n is large. In fact, Erdős conjectured in 1965 [15] the following theorem:

Theorem 3.3.1. For every k there is a constant c such that any graph of order n with at least cn^{1+1/k} edges has a cycle of length 2k.

For sufficiently large n, this and Corollary 3.1.5 imply the existence of not only cycles of even length but also cycles of odd length when m > n^{2}/4. Proving this and similar theorems will be the main purpose of the next chapter. This type of theorem will be loosely called an upper bound theorem– it tells us that the number of edges in a graph with particular properties is no more than a certain function. It tells us nothing about the existence of graphs with nearly that many edges, say cn^{1+1/k} − 1 edges. Theorems giving examples of such graphs will be called lower bound theorems or lower bound constructions.

We note that the bound in Theorem 3.3.1 is much less exact than the previous theorems. In fact, for small n, the bound cn^{1+1/k} could well be much greater than n^{2}/4. For sufficiently large n however, cn^{a} << n^{2}/4 for any a < 2. Thus we are most concerned about the asymptotic growth of our bounds. In all cases, we will first attempt to find the correct power a in the bound by proving upper bounds cn^{a} and lower bounds dn^{a} before optimising the constants c and d. If we can somehow make the constants c and d nearly equal, then we may attempt to prove a bound with a lower order term of the form cn^{a} + fn^{b} where b < a.

Before we move on, we will prove two simple lemmas which in a way justify the particular investigation of bipartite graphs:

Lemma 3.3.2. A graph G has no cycles of odd length if and only if it is bipartite.

Proof. Suppose a graph is bipartite with vertex parts V and W. Let v ∈ V be the first vertex in a path. It is easy to see that paths of odd length must end in W and paths of even length will end in V. To return to v we require at least that the path ends in V, so any cycle will be of even length.

Suppose on the other hand that G has no cycles of odd length. We need only prove that each component of G is bipartite as a graph is bipartite if and only if every component is bipartite. Begin by placing any vertex v in one part V. Then place all the vertices adjacent to v in W. Of the remaining vertices, place those adjacent to any in W in V and repeat. The resulting vertex sets V and W will contain no edges within themselves for otherwise G would have a cycle of odd length.

Lemma 3.3.3. A graph G = G(n, m) contains a bipartite subgraph having at least m/2 edges.

Proof. We will prove this by induction on the number of vertices. Suppose the result holds for all graphs with less than n vertices. Let G have n vertices,m edges and let v be any particular vertex. Then G − {v} has n − 1 vertices and m − d(v) edges.

By the inductive hypothesis, G − {v} has a bipartite subgraph with at least (1/2)(m − d(v)) edges. Let the two parts be A and B, then half of the vertices adjacent to v must be in A or B. Without loss of generality, let us assume A. Then form the bipartite graph with parts A and B ∪ {v}. This has at least

\frac{m − d(v)}{2} + \frac{d(v)}{2} = \frac{m}{2}

edges which completes our proof.

A more careful process proves that if a graph has no vertices of degree 0 then it contains a bipartite subgraph having at least ⌊\frac{m}{2} + \frac{n}{4}⌋ edges [16]. The complete graph K_{n} shows that this is an optimal result.

In fact, it is possible to pick the parts so that the bipartite subgraph that results has nearly the same number of vertices in each part (differing by at most 1). A probabilistic argument suffices: consider every possible bipartite subgraph of G induced by separating the vertices into two sets with nearly the same number of vertices. We note that any particular edge is present in at least as many of these possible subgraphs as not, so there must be one particular division of the vertices where the number of edges present is more than the number of edges which are not present.

Lemma 3.3.3 implies in particular that if we can prove an edge upper bound cn^{a} for bipartite graphs with particular properties then the upper bound 2cn^{a} is immediate for arbitrary graphs with the same properties (as long as these properties are always present in subgraphs).

Graphs without cycles of even length

4.1 Introduction to problem

The original work of this thesis is essentially associated with this question:

What is the maximum number of edges f(n) a graph with n vertices can have without containing particular cycles of even length?

The last part of the question is deliberately vague. For example, we can ask for graphs

1. without cycles of length 4, or

2. without cycles of length 4 or 6, or

3. without cycles of length 6 but possibly with cycles of length 4.

Indeed, we believe the answers for the last two sub-questions are asymptotically very similar but rather different to the the answer for the first question. For these questions, we are most concerned with the behaviour of f(n) for very large n. It is the asymptotic growth of f(n) which is of the most importance so we will occasionally use the o(n), Ω(n) and O(n) asymptotic notation.

Answering these questions require both finding an upper bound on the number of edges and using constructions to demonstrate lower bounds. The techniques used for the upper and lower bounds are usually very different as we shall see shortly.

4.2 Bondy and Simonovits’ proof

Bondy and Simonovtis [8] proved a generalisation of Erdös’ conjecture (Theorem 3.3.1) in 1974.

Before we begin the proof proper, we require a lemma concerning colouring of graphs. A colouring of a graph G assigns a colour to each vertex of G. A colouring is t-periodic if any 2 vertices v and w connected by a path of length t have the same colour assigned.

Apart from the following Lemma (Bollobás [5]) which simplifies both the colouring Lemma and the main Theorem, we essentially follow Bondy and Simonovits’ original method.

Lemma 4.2.1. Let

D_{d} = \{G(n, m) : n ≥ d and m ≥ dn − \binom{d + 1}{2} + 1\} .

If G ∈ D_{d} then G contains a subgraph H with δ(H) ≥ d + 1.

Proof. Note that if G = G(n, m) ∈ D_{d} then n > d for otherwise if n = d

m ≥ n^{2} − \binom{n + 1}{2} + 1
\binom{n}{2} ≥ n^{2} − \frac{1}{2}n(n + 1) + 1
\binom{n}{2} ≥ \binom{n}{2} + 1

which is impossible.

Now suppose G = G(n, m) ∈ D_{d} and δ(G) ≤ d. So there is a vertex v with d(v) ≤ d. Now n > d so G − {x} ∈ D_{d}. Repeating this, we must reach a subgraph H with δ(H) ≥ d + 1 or otherwise we would get a graph K of order d eventually.

Lemma 4.2.2 (Colouring Lemma). Let t be a positive integer, and let G = G(n, m) be a connected graph with

m ≥ 2tn.

Then the number of colours in any t-periodic colouring of G is at most two.

Proof. We first observe that if C is a cycle of length l in G and t_{C} is the smallest integer such that C is t_{C}-periodic then t_{C} divides l.

1. Let v and w be two vertices such that (v, w) is an edge. Suppose first there are two vertex disjoint paths from v to w both of length at least t. Such a subgraph will be called a θ - subgraph. We observe that this θ - subgraph contains 3 cycles C_{1},C_{2} and C_{3} of length say l_{1},l_{2} and l_{3} such that

l_{1} + l_{2} − l_{3} = 2.

Let t_{i} is the smallest integer such that C_{i} is t_{i}-periodic. Then it is easy to see that

t_{1} = t_{2} = t_{3}

since all the 3 cycles share adjacent vertices. But from before, t_{i}|l_{i} so this implies that t_{i} = t_{0} divides 2. Thus the θ-subgraph is coloured with at most 2 colours. However, since G is connected, any other vertex in G will be connected to some vertex in the θ-subgraph by a path of length kt and thus will also be the same colour. Hence the entire graph will be 1 or 2 - coloured.

2. Thus it suffices to prove the existence of a θ-subgraph. Now,

m ≥ 2tn ≥ (2t − 1)n − \binom{2t}{2} + 1.

So G ∈ D_{2t−1} and thus has a subgraph H with δ(H) ≥ 2t from Lemma 4.2.1.

Let a longest path in H be (v_{1}, v_{2}, …, v_{s}). Thus v_{1} is only adjacent to other vertices on this path say (v_{i_{1}}, v_{i_{2}}, … v_{i_{r}}) where i_{1} = 2, i_{1} < i_{2} … < i_{r} and r ≥ 2t. Then the paths (v_{1}, v_{2}, …, v_{i_{t}}) and (v_{1}, v_{i_{2t}}, v_{i_{2t}−1}, … v_{i_{t}}) are both of length at least t. Together with the edge (v_{1}, v_{i_{t}}) this forms a θsubgraph with distinguished vertices v_{1} and v_{i_{t}}.

Now suppose that not all vertices have degree at least 2t and we proceed by induction. When n ≤ 4t, the equation m ≥ 2tn cannot hold and when n = 4t + 1, G is complete and clearly contains the desired θ-subgraph. For the inductive step, suppose that all graphs H = H(n, m) satisfying m ≥ 2tn contain a θ-subgraph. Let G = G(n+1, m) have some vertex v with d(v) < 2t. Then the graph G − {x} has n vertices and it has more than

2tn − 2t = 2t(n − 1)

edges so by the inductive hypothesis it must contain a θ-subgraph and thus so must G. This completes the induction and the proof of the lemma.

We are now ready to prove our desired result.

Theorem 4.2.3. Let G = G(n, m) and suppose that

m > 100kn^{1+1/k}.

Then G contains a cycle of length 2l for all l, k ≤ l ≤ kn^{1/k}.

Proof. Let G = G(n, m) as usual and suppose m satisfies

m ≥ max {100ln, 10ln^{1+1/k}} = m_{0}

for some integer l. We need to show that G contains a cycle of length l.

From Lemma 3.3.3, G contains a bipartite subgraph G′ with at least m_{0}/2 edges. Let d = ⌊\frac{m_{0}}{2n} ⌋ then

dn − \binom{d + 1}{2} + 1 ≤ m

so G′ ∈ D_{d}. Thus by Lemma 4.2.1, G′ contains a subgraph K which has

δ(K) ≥ ⌊\frac{m_{0}}{2n} ⌋ + 1 ≥ max \{40ln, 5ln^{1+1/k}\} .

From now, let s = max {40ln, 5ln^{1+1/k}}.

Suppose now that K contains no cycle of length 2l. Let v be a particular vertex in K and set V_{i} = {w ∈ K : d(w, x) = i}. We will first show that for all i ∈ [1, l],

\frac{|V_{i}|}{|V_{i−1}|} ≥ \frac{s}{5l}.

We prove this by induction on i. When i = 1, |V_{0}| = 1 and v has degree at least s, so |V_{1}| ≥ s, so the inequality 4.2 is immediate. Suppose then that 4.2 is true for i − 1.

Define H be the subgraph of K induced by V_{i−1}∪V_{i} and let H_{1}, H_{2}, …, H_{r} be the connected components of H. Further define W_{j} as V (H_{j}) ∩ V_{i−1}, that is, the set of vertices in H_{j} which are on the (i − 1)^{th} level.

A path (v_{1}, v_{2}, …, v_{m}) in K is called monotonic if the distance between v and v_{i} is monotonic.

We now prove that

e(H_{k}) < 4lv(H_{k})

for every k. We may suppose that W_{k} has at least 2 vertices (otherwise removing H_{k} from consideration makes 4.2 easier to prove). Let us find the closest vertex w to v such that there are two monotonic paths P_{1} and P_{2} which join w to W_{k}, and such that P_{1} ∩P_{2} = w, and suppose w ∈ V_{a} (that is, we are finding the minimum a such that this works) . Such a vertex w clearly exists because there is definitely some vertex in V_{i−2} which is connected to at least two vertices in W_{k}.

Next we prove that every vertex x in W_{k} is joined to w by a monotonic path. It is definitely joined to v by a monotonic path P_{3} and this must intersect P_{1} or P_{2} (by minimality of a), say P_{1} at y. The path from w to y along P_{1} then from y to x along P_{3} is monotonic.

We now colour H_{k}. For any vertex x in W_{k}, we colour it red if there is a monotonic path from x to w which does not intersect P_{1}, otherwise, we colour it blue. We also colour the rest of H_{k} (on the V_{i} level) green completing the colouring.

Now let x_{1} and x_{2} be two vertices in W_{k} red and blue. Let T_{1} and T_{2} be monotonic paths joining x_{1} and x_{2} to w. And suppose T_{1} does not intersect P_{1} but T_{2} intersects P_{1} at z, picking z to be as close to x_{2} as possible. T_{2} cannot possibly intersect T_{1} between z and x_{2} for then the path xT_{2}zT_{1}w (meaning travel from x to z along T_{2} then from z to w along T_{1}) would contradict the fact that x_{2} is blue. The path xT_{2}zP_{2}w does not intersect T_{1} at all. Hence any two vertices of different colour in W_{k} are joined to w in vertex-disjoint paths.

We now prove that this colouring of H_{k} is t = 2(l − i + a + 1)-periodic. H_{k} is bipartite and t even so if the start vertex of a path of length t is green then so is the end vertex. We cannot have a path of length t which connects a blue and red vertex, for otherwise, that path together with the disjoint paths to w would form a cycle of length 2l. We have used 3 colours in this colouring since by the choice of w, we certainly use blue and red, and clearly there is some vertex coloured green. Thus we apply Lemma 4.2.2 to see that e(H_{k}) < 2tv(H_{k}) < 4lv(H_{k}). This is true for all k so summing over components we get

e(H) < 4lv(H).

Now let H′ be the subgraph of K induced by V_{i−2} ∪ V_{i−1} and by looking at the edges emanating from V_{i−1} we have the inequality

e(H) + e(H′) ≥ s |V_{i−1}| .

We also have

e(H′) < 4lv(H′).

Combining the last 3 equations gives

4l(|V_{i}| + |V_{i−1}|) + |V_{i−2}| ≥ s |V_{i−1}|
|V_{i}| > \frac{1}{4l}((s − 8l) |V_{i−1}| − 4l |V_{i−2}|)
|V_{i}| > \frac{1}{4l}(s − 8l − \frac{20l^{2}}{s}) |V_{i−1}| .

Finally, using s ≥ 50l,

\frac{|V_{i}|}{|V_{i−1}|} > \frac{1}{4l}(s − 9l) > \frac{1}{4l} × \frac{4s}{5} = \frac{s}{5l}

which proves the induction.

Hence using s/5l ≥ n^{1/l}

|V_{l}| = \frac{|V_{l}|}{|V_{l−1}|} × \frac{|V_{l−1}|}{|V_{l−2}|} … \frac{|V_{1}|}{|V_{0}|}

> (\frac{s}{5l})^{l}

≥ n.

This contradicts the fact that K had no more than n edges, being a subgraph of G.

Theorem 4.2.3 clearly implies Theorem 3.3.1.

4.3 Recent progress on the upper bound

Theorem 4.2.3 has not been significantly improved upon in its entire generality. The only improvements in the general case have been to the constant 100k in the Theorem. Bollobás [6], for example, provides a proof of the theorem with a constant of 90k, which is not a significant improvement (since neither constant appears to be near the actual universal constant).

On the other hand, bipartite graphs without C_{6}’s and bipartite graphs without either C_{6}’s or C_{4}’s have been heavily studied. In this section we will give a general description of the theorems for these problems.

For graphs with girth 8 and hence no C_{6}’s or C_{4}’s, de Caen, Székely [11] and Faudree, Simonovits [21] prove the following theorem.

Theorem 4.3.1. Let G(n + m, e) be a bipartite graph with vertex parts of sizes m and n have girth at least eight. Suppose that either every vertex has degree at least two, or m = O(n^{2}) and n = O(m^{2}). Then

e = O((mn)^{2/3}).

De Caen, Székely [12] further prove that e ≤ 2^{1/3}(mn)^{2/3} with a few extra assumptions. The incidence matrix of s^{2} points with 2s lines (s vertical and s horizontal) in a square pattern shows that Theorem 4.3.1 is sharp. In fact this question, for the region n ≈ m^{2} has drawn a lot of attention due to its relationship with a number-theoretic problem.

In [18], Erdős, Sárközy and Sós studied the following problem.

Problem 4.3.2. Let k and n be positive integers. Denote by F_{k}(n) the greatest positive integer t such that there is a subset A of {1, 2, …, n} of t elements such that there is no square representable as the product of k distinct elements of A. That is,

a_{1}a_{2} … a_{k} = x^{2}

has no solutions for distinct a_{i} ∈ A.

What is the asymptotic behaviour of F_{k}(n) as n → ∞, for fixed k?

It turns out that this problem, for even k, is related to the study of unbalanced bipartite graphs without C_{k}’s. The k = 2 case was easy to solve with existing results while the k > 6 could not be estimated well due to number theoretic reasons.

On the other hand, they had difficulty with the associated graph theoretic problem in the k = 6 case. Let s(m, n) denote the smallest positive integer s such that if a bipartite graph G with vertex parts of sizes m and n has at least s edges then G must contain a cycle of length 6, where n ≥ m. (Note: quadrilaterals do not come into this problem.)

They conjectured that

Conjecture 4.3.3.

s(m, n) < 2n + c(mn)^{2/3}

for m^{2} ≤ n.

And proving the conjecture would be sufficient to solve the number theoretic problem.

This led to Sárközy [39] proving

s(m, n) < c(n + (mn)^{2/3})

in 1995.

Subsequently, Győri proves in [24] that

s(m, n) < 2n + m^{2}/2,

which is better than the other bounds in the region n ≈ m^{2} and also settles the above conjecture.

Another very heavily studied problem is the computation of the function f_{4}(n), the maximum number of edges in a graph with n vertices and no quadrilaterals. In fact f_{4}(n) has been explicitly calculated for small values of n. Clapham, Flockart and Sheehan [13] determined all the extremal graphs for n ≤ 21. This was further extended to n ≤ 31 by Yuansheng and Rowlinson [49].

On the other hand, for large n, Brown [10] and P. Erdős, A. Rényi, V.T. Sós [20] prove that

Theorem 4.3.4. Asymptotically,

lim_{n→∞} \frac{f_{4}(n)}{n^{3/2}} = \frac{1}{2}.

This result will be a consequence of bounds and constructions we will be proving later.

In fact, Füredi [22] proves that

Theorem 4.3.5. Let f_{4}(n) be defined as before and let q be an even integer. Then

f(q^{2} + q + 1) ≤ \frac{1}{2}q(q + 1)^{2}.

We will now look at this exact problem from the lower bound (constructive) perspective.

4.4 Lower Bound constructions

Theorem 4.2.3 proves an upper bound for the number of edges a graph can have before it must have certain cycles. But it says nothing about the existence of graphs with no such cycles and a high number of edges.

We will first consider graphs which have no cycles of length 2l but have order n and size O(n^{1+1/l}) – in these cases the lower bound given by the constructions and the upper bound of Theorem 4.2.3 agree asymptotically (if we do not worry about constants). Unfortunately, this situation has only been resolved for a small number of values for l.

4.4.1 Projective planes and the C_{4} problem

We first look for graphs which have nearly n^{3/2} edges which do not contain any cycles of length 4.

Theorem 4.4.1. For any n, there exists graphs G(n, m) which contain no quadrilaterals and have m ≥ O(n^{3/2}).

Proof. We offer two different constructions:

Construction 1: Since there is always a prime between n and 2n (Bertrand’s Conjecture), it suffices to demonstrate a graph with 2p^{2} vertices and p^{3} edges.

Let G = (A ∪ B, E) where

A = {(a, b) : 0 ≤ a < p, 0 ≤ b < p}

and

B = {(c, d)′ : 0 ≤ c < p, 0 ≤ d < p} .

Thus |A| = |B| = p^{2}. We define E thus: (a, b) and (c, d)′ are connected if and only if

d ≡ b + ac mod p.

Then suppose G contained a quadrilateral (a, b), (c, d)′, (a′, b′), (c′, d′)′. The 4 edges imply that

d ≡ b + ac  mod p
d ≡ b′ + a′c  mod p
d′ ≡ b + ac′  mod p
d′ ≡ b′ + a′c′  mod p

Cancelling d and d′,

b + ac ≡ b′ + a′c
b + ac′ ≡ b′ + a′c′,

giving both,

c ≡ \frac{b − b′}{a′ − a}
c′ ≡ \frac{b − b′}{a′ − a}

which is impossible unless the quadrilateral is degenerate. Thus this construction contains no C_{4}’s. Since for every triplet a, b, c exactly one value for d works, this graph contains p^{3} edges.

This construction was first given by Euler, and it is also a model for the Heisenberg group. In the context of matrices without particular minors, a similar construction was given in [28] by Kővári, Sós and Turán. This construction is also very similar to Wenger’s more generalised constructions in [47].

Here is the construction for p = 3 (expressed as an adjacency matrix with bullets as 1s).

(2, 2)  •  •  • (2, 1)  •  •  • (2, 0) •  •  • (1, 2)  •  •  • (1, 1)  •  •  • (1, 0) •  •  • (0, 2)  •  •  • (0, 1)  •  •  • (0, 0) •  •  • (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) (2, 1) (2, 2)

Construction 2: A better construction, in the sense that it has the correct properties but contains more edges is given via projective planes.

Take the projective plane P G(2, p) (p prime) and construct a bipartite graph G = (Q ∪ L, E) thus:

• Q is the set of points in the projective plane and L is the set of lines.

• An edge (q, l) : q ∈ Q, l ∈ L is in E if and only if q is incident with l.

The fact that there are no quadrilaterals is obvious: no two lines and two points can all touch each other. It is well known that each point lies on p + 1 lines and each line p + 1 points. Each vertex has degree p + 1 and there are 2(p^{2} + p + 1) vertices all together.

This and similar constructions has been given in many places including Brown [10]. Singleton proves more generally that there is a one to one correspondence between graphs of this type (every vertex same degree, girth 6) and finite projective plane geometries.

Here is the adjacency matrix derived from the finite projective plane with 7 points and 7 lines:

(\begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \end{matrix})

We can see that this is ‘better’ than the last construction in the sense that we have the same number – 3 – entries per row and column, in a smaller matrix and thus less empty space. This translates to a graph with ‘more’ edges in some sense.

One might ask whether we can fit more edges into the graph if we did without the condition that the graph was bipartite. The answer is yes and the construction which achieves this was provided by Erdős, Rényi, and Sós [20] to prove Theorem 4.3.4.

Consider the projective plane construction above. We make the following definition.

Definition 4.4.2. Let π be a bijection from the points to the lines of the projective plane. We call π a polarity if a is a point and b is a line incident with a then π(b) lies on π(a).

Define a new graph G with vertex set just the points of the projective plane. And let an edge join a and b if and only if a ≠ b and b lies on π(a). It is easily verified that G contains no cycles of length 4.

The graph G above has p^{2} +p+1 vertices and just less than half the edges of the bipartite construction. The reason is that we lose the edges where π(a) is incident on a because those result in loops within G. A theorem of Baer [2] says that the minimum number of times this happens is exactly p + 1.

In fact such polarities do exist and there are instances when we lose exactly p + 1 edges. One example is given by ‘dualing’. Let us consider our projective plane in homogeneous coordinates. Each point is identified with an equivalence class of vectors (a_{1}, a_{2}, a_{3}) ∈ F_{p}^{3}. The lines are identified with an identical set of vectors [a_{1}, a_{2}, a_{3}] ∈ F_{p}^{3}. We define π by

π((a_{1}, a_{2}, a_{3})) = [a_{1}, a_{2}, a_{3}].

It is easy to see that π is indeed a polarity. Furthermore, the points a incident on π(a) are exactly those which lie on

x^{2} + y^{2} + z^{2} = 0.

There are p + 1 points on this conic, so a short calculation shows that using this π, w obtain a graph G with p^{2} +p+1 vertices and \frac{1}{2}q(q +1)^{2} edges. This (in part) proves Theorem 4.3.4. Here we have taken the previous adjacency matrix and rearranged the rows so that it is now symmetric. If we removed the diagonal elements, we have the normal adjacency matrix of some graph.

(\begin{matrix}0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{matrix})

Such graphs have been further studied by Füredi [22, 23]. In fact he proves the following theorem in [23].

Theorem 4.4.3. If a graph has p^{2} + p + 1 vertices (p > 13), e edges and no 4-cycles, then e ≤ \frac{1}{2}p(p + 1)^{2}. Equality holds for graphs obtained from finite projective planes with polarities.

For the next few sections, we turn to graphs with many edges but no cycles of longer length, in particular without cycles of length 6 or cycles of length 10.

4.4.2 Benson’s construction

Benson’s [3] constructions rely on projective plane geometries and are higher dimensional generalisations of the construction given above.

Theorem 4.4.4. Let Q be the non-degenerate quadric surface

x_{0}^{2} + x_{1}x_{−1} + x_{2}x_{−2} = 0  (4.1)

in projective 4-space P (4, q) = (x_{−2}, x_{−1}, x_{0}, x_{1}, x_{2}) with the standard equivalence relation. Define G to be the graph whose vertices are the points and lines of Q_{4} and let two vertices be adjacent if they are an incident pointline pair. Then G has degree q + 1, girth 8, 2(1 + q + q^{2} + q^{3}) vertices and (q + 1)(1 + q + q^{2} + q^{3}) edges.

Proof. First we prove that there are no triangles in Q.

Because of the symmetry of the projective geometry, it suffices to show that some particular line is not involved in triangles within Q. Let us pick the line L = (a, b, 0, 0, 0) (that is, all points of that form) . It is easy to see that indeed all the points on this line lie in Q.

Thus all we need to show is that if y = (y_{−2}, y_{−1}, y_{0}, y_{1}, y_{2}) does not lie on L then at most one line in Q intersects both y and L. Let M be a line through y. Lines in Q through y lie on the tangent hyperplane of Q at y. So any point x on M satisfies:

2y_{0}x_{0} + y_{1}x_{−1} + y_{−1}x_{1} + y_{2}x_{−2} + y_{−2}x_{−2} = 0.

(Just take the grad of 4.1 at y and dot it with x). If x also lies on L then it is of the form (a, b, 0, 0, 0) and we obtain

by_{1} + ay_{2} = 0.

And so up to equivalence classes of points in P (4, q) there is only one solution unless y_{1} = y_{2} = 0 which implies that y lies on L. Hence there are no triangles in Q.

This in turn means that there are no cycles of length 6 in G. As it is bipartite and derived from a projective geometry it necessarily contains no cycles of smaller length as well. Hence G has girth at least 8. Q is a nondegenerate surface in P (4, q) and so has the same number of points as any typical 3-space, which is 1 + q + q^{2} + q^{3}. In fact, Q also has 1 + q + q^{2} + q^{3} lines and every vertex in G has degree q + 1.

Benson also constructs a graph with n vertices and O(n^{6/5}) edges which has girth 12.

Theorem 4.4.5. Let Q be the quadric surface in P (6, q) (defined as in the previous theorem) given by

x_{0}^{2} + x_{1}x_{−1} + x_{2}x_{−2} + x_{3}x_{−3} = 0.

For each point in Q distinguish the lines in Q incident with x and points y satisfying

x_{0}y_{i} − x_{i}y_{0} − x_{−j}y_{−k} − x_{−k}y_{−j} = 0

where (i, j, k) is a cyclic even permutation of (1, 2, 3) or (−1, −2, −3). Define G to be the graph whose vertices are the points of Q and the above distinguished lines. Then G is a regular graph with degree q + 1, girth 12, 2(q + 1)(1 + q^{2} + q^{4}) vertices and (q + 1)(1 + q + q^{2} + q^{3} + q^{4} + q^{5}) edges.

The proof is rather technical but uses the same techniques as in the proof of Theorem 4.4.4. The key feature is that we have examples of graphs with no C_{6}’s and O(n^{4/3}) edges, no C_{10}’s and O(n^{6/5}) edges. In fact, these constructions have (n/2)^{4/3} + O(n) and (n/2)^{6/5} + O(n) edges respectively. This is because when we have n/2 = 1+q+q^{2}+q^{3}, applying Taylor’s theorem we get

(n/2)^{4/3} ≈ q^{4} + \frac{4}{3} \frac{1 + q + q^{2}}{q} = q^{4} + o(n).

But

(q + 1)(1 + q + q^{2} + q^{3}) = q^{4} + 2q^{3} + O(n^{2/3}).

Thus

(q + 1)(1 + q + q^{2} + q^{3}) = (n/2)^{4/3} + O(q^{3}) = (n/2)^{4/3} + O(n).

4.4.3 Wenger’s construction

Wenger’s [47] constructions are of the same order as Benson’s but they do not use projective plane geometry. On the other hand, they have slightly less number of edges, exactly (n/2)^{4/3} and (n/2)^{6/5}, though like Benson’s constructions, Wenger’s also only work when a particular parameter is a prime.

Wenger defines his graphs thus (very similar to the first construction in Theorem 4.4.1):

Definition 4.4.6. For each k and p we define H_{k}(p). The vertex set of H_{k}(p) is the union of two sets V_{1}(H_{k}(p)) and V_{2}(H_{k}(p)) with p^{k} vertices each. Each of the vertices a ∈ V_{1} is given a label (a_{0}, a_{1}, …, a_{k−1}), 0 ≤ a_{i} ≤ p − 1. Similarly each of the vertices b ∈ V_{2} has a unique label (b_{0}, b_{1}, …, b_{k−1}), 0 ≤ a_{i} ≤ p − 1. Th edge set of H_{k}(p) is

{(a, b) : a ∈ V_{1}, b ∈ V_{2}, b_{j} ≡ a_{j} + a_{j+1} × b_{k−1} (mod p) for j = 0, …, k − 2} .

For every a ∈ V_{1}, the value of b_{k−1} uniquely determines some b which is adjacent to a. Since there are p possible values of b_{k−1}, each vertex has degree p. So the total number of vertices is 2p^{k} and the total number of edges is p^{k}.

If we look closely, H_{k}(p) is really a refinement of H_{k−1}(p). A vertex in H_{k−1}(p) splits up into p vertices in H_{k}(p). Thus if we can prove that H_{k−1}(p) has a certain girth, then H_{k}(p) has at least that girth.

Wenger’s proof requires one rather technical Lemma and one rather trivial Lemma:

Lemma 4.4.7. If b, b′ ∈ V_{2}(H_{k}(p)) are both adjacent to a ∈ V_{1}(H_{k}(p)), then b_{k−1} ≠ b′_{k−1}.

Proof. The observations above essentially imply this.

Lemma 4.4.8. Let p be a prime. If H_{k}(p) contains a cycle

C = (v_{0}, w_{0}, v_{1}, … v_{k−1}, w_{k−1})

of length 2k then for every w_{i} ∈ C there exists a w_{i′} ∈ C different to w_{i} such that (w_{i})_{k−1} = (w_{i′})_{k−1}.

The proof of this Lemma involves writing out the equations from the adjacency, then summing them in a way to get a system of linear equations whose coefficients are a Vandermonde matrix and then deducing certain things about the coefficients.

Theorem 4.4.9. Let p be a prime. H_{2}(p) does not contain a C_{4}, H_{3}(p) does not contain a C_{6}, and H_{5}(p) does not contain a C_{10}.

Proof. Suppose H_{2}(p) contains a C_{4}, (v_{0}, w_{0}, v_{1}, w_{1}). Then by Lemma 4.4.8, (v_{0})_{1} = (v_{1})_{1}. So they are both adjacent to w_{0} which is impossible by Lemma 4.4.7.

Suppose H_{3}(p) contained a C_{6}, (v_{0}, w_{0}, v_{1}, w_{1}, v_{2}, w_{2}). By Lemma 4.4.8, either (v_{0})_{2} = (v_{1})_{2} or (v_{0})_{2} = (v_{2})_{2}. However, v_{0} and v_{1} are adjacent to w_{0} while v_{0} and v_{2} are adjacent to w_{2}, so by Lemma 4.4.7 this is impossible.

Suppose H_{5}(p) contained a C_{10}, (v_{0}, w_{0}, v_{1}, w_{1}, v_{2}, w_{2}, v_{3}, w_{3}, v_{4}, w_{4}). By Lemma 4.4.8, 3 of the v_{i} will be such that there 4th components are equal. Two of those must be adjacent to the same vertex and this is impossible by Lemma 4.4.7 as before.

The two approaches are quite different but they both give constructions which have the ‘right’ order of edges–the same order as the upper bound Theorem 4.2.3. It seems remarkable that neither method grants the missing construction of a graph with no C_{8}’s and O(n^{5/4}) edges. One would expect that ingenuously selected quadric surfaces in P (5, q) might yield such an example (or more generally quadric surfaces in P (l, q) yielding graphs with girth 2l). And then the reason why H_{4}(p) cannot be proven to have girth 10 seems a coincidence with the way the two Lemma’s functioned.

However, the next section casts some light in this direction.

4.5 Minimal regular graphs

Definition 4.5.1. Let n(d, g) be the smallest integer n such that there exists a graph G with n vertices such that G has girth g and every vertex has degree at least d.

It is intuitive that as d and g increase so does n(d, g). In fact, it is not completely obvious that n(d, g) is defined for all values of d and g, especially large values.

On the other hand, a very good lower bound for n(d, g) can be proved quite easily. The following theorem is due to Tutte [44]:

Theorem 4.5.2.

n(d, g) ≥ \begin{cases}1 + d\frac{(d−1)^{(g−1)/2}−1}{d−2} & if g is odd \\ \frac{(d−1)^{g/2}−1}{d−2} & if g is even \end{cases}

Proof. Suppose first that g = 2k + 1 is odd and let v be some vertex in G(n, m) which has girth g and each vertex degree at least d. The vertices within distance k of v form a tree, for otherwise we would have a cycle of length 2k or less. Thus for l ∈ [0, k − 1] there are at least d(d − 1)^{l} vertices at distance l + 1 from v. Hence,

n ≥ 1 + d ∑_{0}^{k−1} (d − 1)^{l},

which is exactly the bound in 4.5.2.

Suppose g = 2k is even. Then we consider two vertices v and w and the tree spanned by vertices within a distance of k − 1 from either of the two vertices. A similar bound follows, agreeing with the statement of the theorem.

It is clear from the proof that indeed this lower bound can only be achieved by graphs with girth g and every vertex of degree d. Graphs which do achieve this lower bound will be called minimal regular graphs with degree d and girth g. Alternatively, such a graph is also known as a Moore graph of degree d and girth g or when g = 2k + 1 is odd, as a Moore graph of degree d and diameter k.

In fact, the projective plane constructions given in the previous section are all minimal regular graphs. Those constructions give the best lower bounds for our problem (graphs without cycles of even length) and it is not too hard to see that minimal regular graphs in general act as good lower bound constructions for our problem: fixing g and letting d vary we get a collection of graphs with n = n′(d) vertices and m = O(dn′(d)) edges. Clearly, if n′(d) is small and grows slowly in terms of d, then so does m grow slowly as n increases. This collection of graphs serves as lower bound constructions for the problem of graphs without cycles of length g − 1 or g − 2 according to g odd or even.

Further, the results from the next section will strongly suggest that extremal graphs for the even cycles problem has every vertex of nearly the same degree and a structure quite similar to that in the proof of Theorem 4.5.2.

Thus it is natural to look at upper bounds for n(d, g) to obtain lower bounds for the maximum number of edges in graphs without particular cycles. Unfortunately, the known upper bound for n(d, g) is quite poor except for small values of d and g. It is very far from the lower bound in Theorem 4.5.2 which is suspected to be much closer to the true answer.

The following theorem was proven by Sauer in [40] (similar results were discovered by Walther [45, 46] and Erdös and Sachs [19]):

Theorem 4.5.3.

n(d, g) ≥ \begin{cases}2\frac{(d−1)^{(g−1)}−1}{d−2} & if g is odd \\ 4\frac{(d−1)^{g−2}−1}{d−2} & if g is even \end{cases}

The proof is rather technical and will be omitted. It is not very useful for our purposes because using this upper bound, we do not get a very good lower bound for our problem. In fact, let g = 2k + 2 be even (as we shall see it does not really matter asymptotically) then n(d, g) = O(d^{2k−1}), giving graphs with m = O(d^{2k}). This gives:

Corollary 4.5.4. There exists a graph G(n, m) with m = O(n^{2k/2k−1}) edges and no cycles of length 2k or less.

On the other hand, our upper bound for graphs G(n, m) without cycles of length 2k is (Theorem 4.2.3)

m ≤ O(n^{1+1/k}).

Whether we looked at minimal regular graphs with girth 2k or 2k − 1 above does not matter because of the following Lemma (a similar idea will be used in the next chapter).

Lemma 4.5.5. If g is odd then

n(d, g + 1) ≤ 2n(d, g).

Proof. Let G = G(n(d, g), m) be a graph with every vertex of degree at least d and girth at least g. Let G′ be another copy of G separate to G. Define a bipartite graph H which has vertex parts V (G) and V (G′). An edge (a, b) : a ∈ V (G), b ∈ V (G′) is in E(H) if and only if (a, b) is an edge in G (and thus also an edge in G′). Thus (b, a) will also be a (different) edge in H. It is trivial to see that the degree of H is at least d and girth at least g and that H has 2n(d, g) vertices. Further, H is bipartite so it will not have a cycle of length g and thus has girth at least g + 1.

As we saw, however, for certain small values of g, we do indeed get minimal regular graphs associated with projective planes. In fact, Singleton [42] proved that there is a one to one correspondence correspondence between certain minimal regular graphs and particular projective geometries:

Theorem 4.5.6. • To each finite plane projective geometry with d ≥ 3 points on a line there corresponds a minimal regular graph with degree d and diameter 6.

• To each minimal regular graph with degree d ≥ 3 and girth 6 there corresponds a finite, plane projective geometry with d points on a line.

• To each projective geometry G of rank 4 over a finite commutative field and with d ≥ 3 points on a line there corresponds a minimal regular graph with girth 8.

• To each minimal regular graph with degree d ≥ 3 and girth 8, there corresponds a finite projective geometry of rank 4 over a commutative field.

Unfortunately for us, Singleton also proved the following theorem about the non-existence of certain minimal regular graphs:

Theorem 4.5.7. For d > 2, there do not exist minimal regular graphs of degree d and girth 2k for k other than 2, 3, 4 and 6.

The proof is quite technical and looks at complicated polynomials of adjacency matrices. The idea is similar to this. Let A be the adjacency matrix of a minimal regular graph and for concreteness let it have girth 5. By the proof of Theorem 4.5.2, there is exactly one path of length less than or equal to 2 between any two distinct vertices.

However, the entries of A^{2} gives us the number of paths of length 2 between two vertices, and the entries of A gives us those of length 1. Thus, apart from the diagonal, A^{2} + A is filled with 1’s. In fact,

A^{2} + A − (d − 1)I = J,

where d is the degree, I the identity and J the n by n matrix with all entries equal to 1. We can now analyse this situation as if it was just a matrix equation and in particular look at the eigenvalues of this matrix. For example, see Brown [10] where he proves n(d, 5) ≠ d^{2} + 2, or Singleton’s rather long proof of Theorem 4.5.7 in [42].

Thus Theorem 4.5.7 quite strongly suggests that we will be unable to find more lower bound constructions for our problem from projective planes, and if we did, they would not be as ‘optimal’ as Benson’s constructions. Perhaps more lower bound constructions could be found using Wenger’s method. It is very curious that Wenger’s method fails and succeeds for the same cases that Benson’s does, even though they seem inherently so different.

4.6 More recent lower bound constructions

More recently, progress has been made which improves upon the trivial Corollary 4.5.4. So far there has been no success in obtaining constructions for cases other than the C_{4}, C_{6} and C_{10} cases, which asymptotically agree with the upper bound in Theorem 4.2.3.

The best current bounds are by F. Lazebnik, V.A. Ustimenko and A.J. Woldar [32, 33] in 1995. They find bipartite, q-regular graphs with order n ≤ 2q^{k−t+1}, where k is an odd integer and t = ⌊\frac{k+2}{4}⌋. They then prove that these graphs have girth g ≥ k + 5 (and thus no cycles of length k + 3 or less), and Ω(n^{1+ \frac{1}{k−t+1}} ) edges.

For example, for k = 5, g = 10 and their constructions will have around O(n^{1+ \frac{1}{5}} ) edges and no cycles of length 8. This compares with O(n^{1+ \frac{1}{7}} ) from Corollary 4.5.4 and the upper bound value of O(n^{1+ \frac{1}{4}} ).

Other weaker bounds were established by Margulis [37] whose constructions were Cayley graphs of SL_{2}(ℤ_{p}). Imrich [25] and Biggs, Hoare, [4] provided constructions of families of cubic and sextet graphs. These bounds were again improved by constructions known as Ramanujan graphs, established by Margulis [37] and Lubotzky, Phillips, Sarnak [36, 38].

4.7 A number theoretic application

Before moving onto a number of original results, we will demonstrate a simple application of these results to number theory. We have already briefly described the application of results of graphs without C_{6}’s to product representation of squares. Here, we give a much simpler application, and indeed the one studied by Erdős which first led to his conjecturing of Theorem 3.3.1.

In [17], Erdős investigated two problems, one of which was:

Problem 4.7.1. Assume that n_{1} < … < n_{k} are positive integers such that n_{i}n_{j} ≠ n_{h}n_{l} unless i = h and j = l or j = h and i = l. What is the maximum number B(n) of such integers in [1, n]?

To see how graph theory can help in tackling this problem, we first define D to be the set of integers in [1, n^{2/3}] and P the set of primes in (n^{2/3}, n] and set B = D ∪ P.

Lemma 4.7.2. Every integer a ∈ [1, n] can be written as

a = bd

where b ∈ B and d ∈ D.

Proof. If a ∈ D, the result is trivial. Now suppose a ∈ (n^{2/3}, n]. It is not possible for a to have two prime divisors (or a repeated prime divisor) both in P for otherwise a > n^{4/3} > n.

Thus either a = pc for a prime p ∈ P or a is not divisible by any prime in P. For the first case, it is clear that c ∈ D and we are done. For the second case, we repeatedly divide a by divisor d_{i} less than or equal to a^{1/2} ≤ n^{1/2} to obtain a sequence a_{i}. If at some point ∏_{1}^{n} d_{i} ≥ n^{1/3} then a_{n} ∈ D. If ∏_{1}^{n} d_{i} < n^{1/3} then ∏_{1}^{n+1} d_{i} < n^{2/3}. These observations imply that at some stage we can express a = (∏_{1}^{n} d_{i})a_{n} where a_{n} ∈ D and ∏_{1}^{n} d_{i} ∈ D.

Now let A be a set satisfying the conditions of Problem 4.7.1. We present each a ∈ A by a_{i} = b_{j}(i)d_{j}(i). Now form a bipartite graph G(B∪D, E) where the vertex b_{i} is joined to d_{j} if and only if a = b_{i}d_{j} ∈ A.

This graph G turns out to have no cycles of length 4. For otherwise, we would get (b_{1}, d_{1}, b_{2}, d_{2}) such that a_{1} = b_{1}d_{1}, a_{2} = b_{2}d_{1}, a_{3} = b_{2}d_{2} and a_{4} = b_{1}d_{2} were all in A. And then a_{1}a_{3} = a_{2}a_{4}, contradicting our assumption.

Using the (weak) result that a bipartite graph with parts of sizes k and k without C_{4}’s had

m ≤ 3k^{3/2}

edges, Erdős then proceeded to prove that

π(n) + \frac{cn^{3/4}}{(logn)^{3/2}} ≤ B(n) ≤ π(n) + O(n^{3/4}).

Here π(x) denotes the number of primes in [2, x]. This says that asymptotically, the biggest subset A we can pick is around the same size as just picking all the primes.

This example is probably the first application of extremal graph theory to number theory. Interestingly, it was not until a few years after Erdős’ paper (when Turán [43] wrote his paper on forbidden complete subgraphs in 1941), that the study of cycles in graphs and extremal graph theory in general took off.

Original results

Throughout this chapter, we will be using an adjacency matrix formulation of bipartite graphs. We will consider a matrix A with N columns and M rows. The matrix entries of A are either 1 or 0 and for brevity we will refer to an entry with a 1 simply as an entry. The number of entries in A will be called X.

5.1 A heuristic argument

Let A be a N × M matrix which contains no rectangles. Consider a ‘typical’ entry x in A. There are X other entries so on average we would expect the row containing x to have X/M. The number of rook moves of length 2 starting at x horizontally we would expect to be around

\frac{X}{N} × \frac{X}{M}

as each column in A has on average X/N entries. However two different rook moves of length 2 starting at x horizontally cannot possibly end on the same row for otherwise we would have a rectangle. Thus we get

\frac{X}{N} × \frac{X}{M} < M.

[figure: x; •; X/Mchoices; •; X/Nchoices]

Two distinct rook moves (x, a, b), (x, c, d) ending in the same column results in a rectangle (a, b, c, d):

\xymatrix{x \ar[rr] \ar[r] & c \ar[d] & a \ar[d] \\  & d & b}

Repeating for an arbitrary vertex w ∈ W we get

X < min \{M\sqrt{N}, N\sqrt{M}\} .

Applying Lemma 3.3.3, this suggests that m < cn^{3/2} for some constant c and for any graph G = G(n, m) without quadrilaterals. The same argument suggests the corresponding results for graphs lacking longer even cycles. For hexagons we get

(\frac{X}{N} )^{3} < N,

where N is approximately n/2. This gives m < cn^{4/3}.

At present this heuristic argument is not completely convincing and hardly rigorous but still quite suggestive. However, this type of idea will be the basis of the original results of this thesis and is made rigorous by a combinatorial lemma of Katz and Tao from [27].

5.2 A combinatorial lemma

Lemma 5.2.1. Let X and A_{1}, …, A_{n} be finite sets for some n ≥ 0, and for each 1 ≤ i ≤ n let f_{i} : X → A_{i} be a function. Then:

# \{(x_{0}, …, x_{n}) ∈ X^{n+1} : f_{i}(x_{i−1}) = f_{i}(x_{i}), 1 ≤ i ≤ n\} ≥ \frac{(#X)^{n+1}}{∏_{i=1}^{n} #A_{i}} .

Proof. We shall prove the Lemma by induction on n. The result is clearly true for n = 0. Suppose that n ≥ 1 and that the result is true for n − 1.

Define an element a ∈ A_{n} to be popular if

# \{x ∈ X : f_{n}(x) = a\} ≥ \frac{#X}{2XA_{n}} ,

and define X′ to be those elements x ∈ X such that f_{n}(x) is popular. Since each unpopular element of A_{n} contributes at most #X/(2#A_{n}) elements to X, we see that

#(X/X′) ≤ \frac{1}{2}#X,

so

#X′ ≥ \frac{1}{2}#X.

By applying the inductive hypothesis to X′ we have

# {(x_{0}, …, x_{n−1}) ∈ (X′)^{n} : f_{i}(x_{i−1}) = f_{i}(x_{i}) for all 1 ≤ i ≤ n} ≥

\frac{(#X′)^{n}}{∏_{i=1}^{n−1} #A_{i}} .

Since f_{n}(x_{n−1}) is popular, we thus have

# {(x_{0}, …, x_{n−1}, x_{n}) ∈ (X′)^{n} × X : f_{i}(x_{i−1}) = f_{i}(x_{i})∀i : 1 ≤ i ≤ n}

≥ \frac{#X^{′n}}{∏_{i=1}^{n−1} #A_{i}} \frac{#X}{2#A_{n}} .

From 5.2 we thus have

LHS of 5.2.1 ≥ 2^{−n} \frac{(#X)^{n+1}}{∏_{i=1}^{n} #A_{i}} .

To eliminate the factor of 2^{−n}, we let M be a large integer and apply 5.2 with X,A_{i} replaced by X^{M},A_{i}^{M} and f_{i} replaced with the function f_{i}^{M} : X^{M} → A_{i}^{M} defined by

f_{i}^{M}(x^{1}, …, x^{M}) = (f_{i}(x^{1}), …, f_{i}(x^{M})),

to obtain

( LHS of 5.2.1)^{M} ≤ 2^{−n}(\frac{(#X)^{n+1}}{∏_{i=1}^{n} #A_{i}} )^{M}.

The claim then follows by letting M → ∞.

To apply Lemma 5.2.1 to our problem, we let X be the set of entries which have a 1 (abusing notation), and let A_{i} be the set of rows for i odd and the set of columns when i is even. For x ∈ X, we set f_{i}(x) to be the row that x is in when i is odd and the column that x is in when i is even.

Thus Lemma 5.2.1 counts the number of vectors (x_{0}, x_{1}, …, x_{n}) where x_{0} and x_{1} belong to the same row, x_{1} and x_{2} to the same column and so on. These are exactly the number of rook moves of length n starting horizontally. Thus for n = 2k,

# \{such rook moves\} ≥ \frac{X^{n+1}}{N^{k}M^{k}} ,

and n = 2k + 1,

# \{such rook moves\} ≥ \frac{X^{n+1}}{N^{k}M^{k+1}} .

5.2.1 Example: Matrices without rectangles

To simplify things for our example, we assume our matrix A is square, N ×N. Let n = 1 and we see that the number of rook moves of length 1 beginning horizontally is at least X^{2}/N. However, no two proper rook moves of that form can start and end on the same columns, for then we would have a rectangle. Thus we can nearly say that:

\frac{X^{2}}{N} ≤ N^{2}.

Unfortunately, we have not taken into account the degenerate rook moves of the form (x_{0}, x_{0}). Two rook moves of this form can start and end on the same columns without any problems (we get a degenerate rectangle which does not count). To complete the calculation, we need only remove these rook moves from consideration. Clearly the set of such degenerate rook moves are just single entries in A and has size exactly X:

\frac{X^{2}}{N} − X ≤ N^{2}.

This is not too hard to solve:

X ≤ \frac{N + \sqrt{N^{2} + 4N^{3}}}{2} ,

giving:

X ≤ N^{3/2} + O(N).

5.2.2 Example: Matrices without hexagons

Let us repeat the calculations for a matrix without either rectangles or hexagons. We are now interested in rook moves of length 2, which say start horizontally. Then we can say that no two non-degenerate rook moves of length 2, (a, b, c) and (a′, b′, c′), can possibly start on the same column and end on the same row, for otherwise the two rook moves will either be identical or will form a hexagon or rectangle:

[figure: a; b; c; a′; b′; c′]

The degenerate rook moves are of the form (a, a, b), (a, b, b) or (a, a, a) where in the first case a and b belong to the same column and in the second case they belong in the same row, and a ≠ b . These are just rook moves of length 1 beginning vertically and horizontally respectively, and there are certainly no more than N^{2} of each type using just the no rectangle condition. A bit of careful analysis will show that in fact we do not have to remove the degenerate rook moves of the form (a, a, a) from our counting.

\frac{X^{3}}{N^{2}} − 2N^{2} ≤ N^{2}
X^{3} ≤ 3N^{4}
X ≤ 3^{1/3}N^{4/3}.

Even with a crude application of Lemma 3.3.3 we see that for a graph G = G(n, m) with no rectangles or hexagons,

m ≤ 2 × 3^{1/3} (\frac{n}{2})^{4/3} = (\frac{3}{2})^{1/3}n^{4/3}.

This is already much better than Bondy and Simonovits’ constant in Theorem 4.2.3, albeit quite a bit less general. However, the projective plane constructions of Benson seem just right and they could well be very close to an extremal graph in this example. In that case, those constructions suggest a bound of:

X ≤ N^{4/3} + O(N),

for bipartite graphs G with vertex parts both of size N. This is the type of result we will be aiming for in the next few sections.

5.3 The inductive approach

The reason for the constant of 3^{1/3} in the above example is because of the poor estimation of the degenerate rook moves. We only used the fact that there were no rectangles and no doubt overestimated the number of degenerate rook moves.

Having arrived at the final result of X ≤ 3^{1/3}N^{4/3} we could heuristically argue that in the extremal case each row and column should have approximately the same number of entries, around 3^{1/3}N^{1/3} 1’s. This gives around O(N^{2/3}) pairs of entries in each column, or O(N^{5/3}) rook moves of length 1:

X^{3} ≤ N^{4} + CN^{11/3}
X ≤ N^{4/3} + \frac{C}{3} \frac{N^{11/3}}{N^{4×2/3}}
X ≤ N^{4/3} + \frac{C}{3} N,

where we have used the first two terms of the Taylor series expansion of f(x) = x^{1/3} for the middle inequality (the correction term makes the right hand side smaller, so we can legitimately ignore it).

The only problem, of course, is finding out how to argue that every row and column has an ‘average’ number of entries. Our method involves first using an induction approach to give us an easy lower bound on the number of entries, and then a trickier argument to give us an upper bound on the number of entries. Our first theorem will be:

Theorem 5.3.1. Let A be a matrix with dimensions M × N whose entries are either 1’s or 0’s. If A does not contain any cycles of length 2l for any l ≤ 2k + 1 then the number of entries with a 1 in A is no more than

(NM)^{\frac{k+1}{2k+1}} + C_{k}(N + M),

for some constant C_{k} depending only on k.

We will prove the theorem by induction in N and M where N is the number of columns and M the number of rows. The result is clearly true when either N or M is 1 with C_{k} = 1. Suppose then that there is some D ≥ 1 such that X(n, m) ≤ (nm)^{\frac{k+1}{2k+1}} + D(n + m) is true ∀(n, m) : n < N, m ≤ M or n ≤ N, m < M. Let A be an N × M matrix of 1s and 0s such that the number of entries with a 1 is X > (NM)^{\frac{k+1}{2k+1}} + D(N + M).

Recall that an entry is a position in A containing a 1. Throughout the proof, C will represent any positive constant which only depends on k but not N or M.

We begin by proving 3 lemmas:

Lemma 5.3.2. No row contains less than CN^{\frac{k+1}{2k+1}} M^{\frac{−k}{2k+1}} + 1 entries. No column contains less than CM^{\frac{k+1}{2k+1}} N^{\frac{−k}{2k+1}} + 1 entries.

Proof. Pick a row R with r entries. Then removing this row and applying the inductive hypothesis to the resulting matrix gives:

X − r ≤ (N(M − 1))^{\frac{k+1}{2k+1}} + D(N + M − 1)
(NM)^{\frac{k+1}{2k+1}} + D(N + M) − r < (N(M − 1))^{\frac{k+1}{2k+1}} + D(N + M − 1).

Expanding the right hand side using the Taylor series f(x) = x^{\frac{k+1}{2k+1}} we get the weaker inequality:

−r < −\frac{k + 1}{2k + 1}N^{\frac{k+1}{2k+1}} M^{\frac{−k}{2k+1}} − D

from which our first desired result immediately follows as D ≥ 1. The proof for columns is identical.

Lemma 5.3.3. No row contains more than CN^{\frac{k+1}{2k+1}} M^{\frac{−k}{2k+1}} entries. No column contains more than CM^{\frac{k+1}{2k+1}} N^{\frac{−k}{2k+1}} entries.

Proof. Pick a row R with say r entries. We want to count the number of destination entries which can be reached from any entry of R by nondegenerate rook moves of length 2k.

Pick any entry x_{0} of R. The number of entries that can be reached from x_{0} by a non-degenerate rook move of length 1, starting vertically, is at least CM^{\frac{k+1}{2k+1}} N^{\frac{−k}{2k+1}} , using Lemma 5.3.2. Repeating this, we see that the number of non-degenerate rook moves of length 2l starting at x_{0} is at least

(C^{2}M^{\frac{k+1}{2k+1}} N^{\frac{−k}{2k+1}} N^{\frac{k+1}{2k+1}} M^{\frac{−k}{2k+1}} )^{l} = CM^{\frac{l}{2k+1}} N^{\frac{l}{2k+1}}

Now set l = k and note that all these non-degenerate rook moves must end on a different column (and in particular, end on different entries). For if we have two rook moves x_{0}, x_{1}, … x_{2k} and x_{0}, y_{1}, … y_{2k} such that x_{2k} and y_{2}k are entries of the same column, then

x_{1}, … x_{2k}, y_{2k}, y_{2k−1}, …, y_{1}, x_{1}

will contain a cycle of even length ≤ 4k (x_{1} and y_{1} are both on the same column as x_{0} so are on the same column as each other).

Now consider the set of all such non-degenerate rook moves as x_{0} varies over all the entries of R. Again we claim that no two such rook moves say x_{0}, x_{1}, … x_{2k} and y_{0}, y_{1}, … y_{2k} where x_{0} ≠ y_{0} end on the same column. For otherwise,

x_{0}, x_{1}, … x_{2k}, y_{2k}, y_{2k−1}, …, y_{1}, y_{0}, x_{0}

will contain a cycle of length ≤ 2(2k + 1).

Thus we get the inequality:

r × CM^{\frac{k}{2k+1}} N^{\frac{k}{2k+1}} < N

Or:

r < CN^{\frac{k+1}{2k+1}} M^{\frac{−k}{2k+1}} .

Similarly, no column contains more than CM^{\frac{k+1}{2k+1}} N^{\frac{−k}{2k+1}} entries.

Lemma 5.3.4. The number of degenerate rook moves of length 2k is no more than C(N + M)(NM)^{\frac{k}{2k+1}} .

Proof. A degenerate rook move (x_{0}, x_{1}, …, x_{2k}) must have some i such that x_{i} = x_{i+1}. Let the row with the maximum number of entries have C_{r} entries, and correspondingly C_{c} for the columns. Fixing i, the maximum number of such rook moves is no more than XC_{r}^{k−1}C_{c}^{k} when i is even or XC_{r}^{k}C_{c}^{k−1} when i is odd. Since X ≤ NC_{c} and X ≤ MC_{r}, we get these are less than N(C_{c}C_{r})^{k} and M(C_{c}C_{r})^{k}. Using Lemma 5.3.3 to give C_{r} ≤ CN^{\frac{k+1}{2k+1}} M^{\frac{−k}{2k+1}} and C_{c} ≤ CM^{\frac{k+1}{2k+1}} N^{\frac{−k}{2k+1}} and summing over 0 ≤ i ≤ 2k (this summation just contributes to the constant as it doesn’t depend on N or M) , we see that the number of degenerate rook moves is no more than :

C(N + M)(NM)^{\frac{k}{2k+1}} .

Proof. Combining Lemma 5.2.1 and Lemma 5.3.4 we now have:

\frac{X^{2k+1}}{N^{k}M^{k}} − C(N + M)(NM)^{\frac{k}{2k+1}} ≤ NM

or

X^{2k+1} ≤ (NM)^{k+1} + C(N + M)(NM)^{\frac{k(2k+2)}{2k+1}} .

Using the first two terms of the Taylor series for f(x) = x^{\frac{1}{2k+1}} this implies that:

X ≤ (NM)^{\frac{k+1}{2k+1}} + \frac{C}{2k + 1}(N + M)(NM)^{\frac{k(2k+2)}{2k+1}} (NM)^{\frac{−(k+1)2k}{2k+1}}  (5.1)

Thus:

X ≤ (NM)^{\frac{k+1}{2k+1}} + \frac{C}{2k + 1}(N + M).

Since C does not depend on N or M nor on the size of D in the inductive hypothesis, we have proved that X ≤ (NM)^{\frac{k+1}{2k+1}} + max \frac{C}{2k+1}, D(N + M). Thus, by the principle of mathematical induction, for each k there is a constant D_{k} such that

X ≤ (NM)^{\frac{k+1}{2k+1}} + D_{k}(N + M).

This proves Theorem 5.3.1.

Theorem 5.3.1 is best possible in the following way: by the constructions of Benson and Wenger, the order of the leading term ((NM)^{\frac{k+1}{2k+1}} ) and the constant preceding it is best possible. For the lower order term, Benson’s projective plane constructions show that indeed such a term must be present in general, and our term is of the correct order. Our result improves upon that of de Caen, Székely [11] and Faudree, Simonovits [21] who showed a bound of C(NM)^{2/3} for some constant C.

5.4 The case 4n

The result of Theorem 5.3.1 is symmetric in N and M as we would expect. Unfortunately, as we saw in the C_{4} case for matrices without rectangles, we actually get two different bounds each of which is assymetric in N and M, depending on whether we look at rook moves beginning horizontally or vertically. This makes the C_{4n} case quite a bit more complicated.

In fact, we are unable to prove a form of the result as strong as Theorem 5.3.1, though for the case N = M the result is as strong as we could hope for. The calculations are nearly identical to those of the previous section, with a few modifications.

Theorem 5.4.1. Let A be a matrix with dimensions M ×N whose entries are either 1’s or 0’s. If A does not contain any cycles of length 2l where l ≤ 2k then the number of entries with a 1 in A is no more than the maximum of

N^{\frac{1}{2}} M^{\frac{k+1}{2k}} + C_{k}(N + M),

and

M^{\frac{1}{2}} N^{\frac{k+1}{2k}} + C_{k}(N + M),

for some constant C_{k} depending only on k.

We will prove the bound by induction.

We will prove the theorem by induction in N and M where N is the number of columns and M the number of rows. The result is clearly true when either N or M is 1 with C_{k} = 1.

Suppose then that there is some constant for which our theorem is true for all n < N, m < M.

Suppose N > M. Let A be an N × M matrix of 1s and 0s such that the number of entries with a 1 is X > M^{\frac{1}{2}} N^{\frac{k+1}{2k}} + D(N + M) (this bound is greater than the other one in the region N > M).

Throughout the proof, C will represent any positive constant which only depends on k but not N or M.

Our first step is the following lemma:

Lemma 5.4.2. No row contains less than CN^{\frac{k+1}{2k}} M^{\frac{−1}{2}} +1 entries. No column contains less than CM^{\frac{1}{2}} N^{\frac{1−k}{2k}} + 1 entries.

Proof. Pick a row R with r entries. Then removing this row and applying the inductive hypothesis to the resulting matrix gives:

X − r ≤ N^{\frac{k+1}{2k}} (M − 1)^{\frac{1}{2}} + D(N + M − 1)
M^{\frac{1}{2}} N^{\frac{k+1}{2k}} + D(N + M) − r < N^{\frac{k+1}{2k}} (M − 1)^{\frac{1}{2}} + D(N + M − 1).

expanding the right hand side using the Taylor series f(x) = x^{\frac{1}{2}} we get the weaker inequality:

−r < −CN^{\frac{k+1}{2k}} M^{\frac{−1}{2}} − D

from which our first desired result immediately follows as D ≥ 1. The proof for columns is essentially the same.

Lemma 5.4.3. No row or column contains more than CN^{\frac{1−k}{2k}} M^{\frac{1}{2}} entries.

Proof. Pick a row R with say r entries. We want to count the number of destination entries which can be reached from any entry of R by nondegenerate rook moves of length 2k − 1, starting vertically.

Pick any entry of R, x_{0}. The number of entries that can be reached from x_{0} by a non-degenerate rook move of length 1, starting vertically, is at least CM^{\frac{1}{2}} N^{\frac{1−k}{2k}}, using Lemma 5.4.2. Repeating this, we see that the number of non-degenerate rook moves of length 2k − 1 starting at x_{0} is at least

(CN^{\frac{k+1}{2k}} M^{\frac{−1}{2}} )^{k−1}(CM^{\frac{1}{2}} N^{\frac{1−k}{2k}})^{k} = CM^{\frac{1}{2}} N^{\frac{k−1}{2k}}

Now note that all these non-degenerate rook moves must end on a different row (and in particular, end on different entries). For if we have two rook moves x_{0}, x_{1}, … x_{2k−1} and x_{0}, y_{1}, … y_{2k−1} such that x_{2k−1} and y_{2}k − 1 are entries of the same column, then

x_{1}, … x_{2k−1}, y_{2k−1}, y_{2k−2}, …, y_{1}, x_{1}

will contain a cycle of even length ≤ 4k − 2 (x_{1} and y_{1} are both on the same column as x_{0} so are on the same column as each other).

Now consider the set of all such non-degenerate rook moves as x_{0} varies over all the entries of R. Again we claim that no two such rook moves say x_{0}, x_{1}, … x_{2k−1} and y_{0}, y_{1}, … y_{2k−1} where x_{0} ≠ y_{0} end on the same column. For otherwise,

x_{0}, x_{1}, … x_{2k−1}, y_{2k−1}, y_{2k−2}, …, y_{1}, y_{0}, x_{0}

will contain a cycle of length ≤ 4k.

Thus we get the inequality:

r × CM^{\frac{1}{2}} N^{\frac{k−1}{2k}} < M

Or:

r < CN^{\frac{1−k}{2k}} M^{\frac{1}{2}} .

Similarly, we get the same bound for columns.

Lemma 5.4.4. The number of degenerate rook moves of length 2k−1 starting horizontally is no more than C(N^{\frac{1−k}{2k}} M^{\frac{1}{2}} )^{2k−1}.

Proof. A degenerate rook move (x_{0}, x_{1}, …, x_{2k−1}) must have some i such that x_{i} = x_{i+1}. Let the row with the maximum number of entries have C_{r} entries, and correspondingly C_{c} for the columns. Fixing i, the maximum number of such rook moves is no more than XC_{r}^{k−1}C_{c}^{k−1} when i is even or XC_{r}^{k}C_{c}^{k−2} when i is odd. We now use Lemma 5.4.3 to give C_{r} ≤ CN^{\frac{1−k}{2k}} M^{\frac{1}{2}} and C_{c} ≤ CN^{\frac{1−k}{2k}} M^{\frac{1}{2}} and we note that X ≤ NC_{c} and X ≤ MC_{r}. Summing over 0 ≤ i ≤ 2k − 1 (this summation just contributes to the constant as it doesn’t depend on N or M) , we see that the number of degenerate rook moves is no more than N or M multiplied by :

C(N^{\frac{1−k}{2k}} M^{\frac{1}{2}} )^{2k−1}.

Proof. Combining Lemma 5.2.1 and Lemma 5.4.4 we now have:

\frac{X^{2k}}{M^{k}N^{k−1}} − CN(N^{\frac{1−k}{2k}} M^{\frac{1}{2}} )^{2k−1} ≤ N^{2},

or

X^{2k} ≤ N^{k+1}M^{k} + CN^{k}M^{k}(N^{\frac{1−k}{2k}} M^{\frac{1}{2}} )^{2k−1}.

Using the first two terms of the Taylor series for f(x) = x^{\frac{1}{2k}} this implies that:

X ≤ M^{\frac{1}{2}} N^{\frac{k+1}{2k}} + CM^{k}N^{1−k}.

Thus, for the region N > M,

X ≤ M^{\frac{1}{2}} N^{\frac{k+1}{2k}} + C(N + M).

So we have proven the inductive step for this region. Similarly, we can prove the inductive step for the region M > N (we will be proving the other bound in this region). When M = N, we will require one bound to give the minimum per column and the other bound to give the minimum per row, but the procedure is identical. Since C does not depend on N or M we have proven the inductive step.

Thus, by the principle of mathematical induction, for each k there is a constant D_{k} such that X is less than or equal to the maximum of

M^{\frac{1}{2}} N^{\frac{k+1}{2k}} + D_{k}(N + M),

and

N^{\frac{1}{2}} M^{\frac{k+1}{2k}} + D_{k}(N + M).

This proves Theorem 5.4.1.

5.5 Non-bipartite graphs

5.5.1 Upper bound

Applying Lemma 3.3.3 immediately gives us a reasonable bound for all graphs, not just bipartite graphs of at most

2 (\frac{N}{2} )^{\frac{k+1}{2k+1}} + O(N)

edges in graphs without even cycles of length less than C_{4k+2}. However, it is possible to modify the arguments above to obtain a bound which we believe is nearly optimal for graphs in general.

Theorem 5.5.1. Let G = G(n, m) be a graph without any cycles of even length less than or equal to C_{4k+2}. Then there exists a constant C so that

m ≤ \frac{1}{2}n^{\frac{2k+2}{2k+1}} + Cn.

for all n.

The proof of this theorem uses the same idea as Lemma 4.5.5 to produce a a bipartite graph of twice the order, to which we apply the same methods as in Theorem 5.3.1.

Let our graph G have N vertices, then we can form an N × N matrix A such that entry (i, j) contains a 1 if vertex i is connected to vertex j in G, and a 0 otherwise.

Then we hope to be able to apply our theorems for bipartite graphs to this matrix, except now, each row is identified with some column in a particular way. The problem of course is that the graph G may contain cycles of odd length and thus the matrix A can contain particular kinds of cycles of even length. For example, if (a, b, c) is a triangle in G, then ((a, b′), (c, b′), (c, a′), (b, a′), (b, c′), (a, c′)) is a hexagon in A. These types of hexagons and similar cycles only happen rarely though, because each row is identified with only one column, which is the source of these cycles – essentially a cycle of odd length transversed twice becoming a proper cycle of even length in the bipartite graph. Indeed, if we added the condition that G also does not contain certain shorter odd cycles, then proving Theorem 5.5.1 is quite trivial.

Firstly, we begin with the same inductive hypothesis as in Theorem 5.3.1 except that now each row may be identified with at most one column in a one-to-one fashion, and cycles of even length in the matrix are allowable if they do not translate to a cycle of even length in the corresponding graph which we can draw using the matrix. We further assume that the constant for the linear term is at least 4k + 1 in the inductive hypothesis.

We will follow the same steps as in the proof of Theorem 5.3.1 with a few modifications.

Lemma 5.5.2. No row contains less than CN^{\frac{k+1}{2k+1}} M^{− \frac{k}{2k+1}} + 4k + 1 entries. No column contains less than CM^{\frac{k+1}{2k+1}} N^{− \frac{k}{2k+1}} + 4k + 1 entries.

Proof. The proof is identical to that of Lemma 5.3.2.

We now introduce an additional lemma concerning graphs without cycles of even length in general.

Definition 5.5.3. A θ-subgraph is a cycle C and a path P joining two vertices x and y in C such that P ∩ C = {a, b}.

Lemma 5.5.4. Let G be a graph without cycles of even length. Then G cannot contain a θ-subgraph {C, P }. Furthermore, if there exists two points {c, d} on C such that the three paths from c to d (two along cycle and 1 via P) all have length less than l, then we need only require G to have no cycles of even length shorter than or equal to 2l.

Proof. There are 3 vertex disjoint paths from a to b and 2 of them must be of the same parity. Travelling along one and back along the other results in a cycle of even length.

For the second part, we note that any of the cycles above is no longer than the sum of the lengths of some two of the paths from c to d.

Lemma 5.5.5. Let G be a graph without cycles of even length less than or equal to 2l. Let a and b be two vertices in G and let S be a set of paths from a to b which all have length less than or equal to some integer l. Then |S| < C for some constant C which depends only on l.

Proof. Let G′ be the graph induced by the paths in S. We show that G′ is composed of a number of cycles and a number of paths in a linear fashion. To prove this, we successively add a path from S to G′ and suppose that at some point the structure of G′ contains a θ-subgraph. Then since the θ-subgraph is composed of parts which are all subpaths of paths of length less than or equal to l, it will satisfy the conditions of Lemma 5.5.4 and is forbidden.

However, there are only a constant number of paths from each such arrangement of cycles and paths – depending on only choosing which branch of the cycle at each step. Since the total length of the paths is bounded by l, the total number of cycles and choices is again bounded by some function of l.

Figure 5.1: Multiple paths from a to b with no even cycles.

a  b

Lemma 5.5.6. No row contains more than CN^{\frac{k+1}{2k+1}} M^{− \frac{k}{2k+1}} entries. No column contains more than CM^{\frac{k+1}{2k+1}} N^{− \frac{k}{2k+1}} entries.

Proof. The proof here is nearly identical to that of Lemma 5.3.3. We will pick a row and count non-degenerate rook moves of length 2k starting from some entry in this row. The major difference is that now we do not allow these rook moves to revisit any row or column which is the same or identified with a previously visited row or column. Since we are looking at rook moves of length 2k < 4k + 1, we can be ensured of at least CN^{\frac{k+1}{2k+1}} M^{− \frac{k}{2k+1}} choices for each step of the rook move, as before. (This is the reason for needing the higher lower bound in Lemma 5.3.2.) Thus we get the same number of such non-degenerate, non-self-revisiting rook moves as before.

Furthermore, it is no longer true that no two such rook moves starting on same row cannot end on same column, for if we consider this situation in the graph, we can have two paths of length 2k + 1 between two vertices – this can be possible if they intersect and the resultant cycles are all odd in length.

However, by Lemma 5.5.5 only a constant number of such paths can exist (any even cycles generated will have length less than or equal to 4k + 2 so we can apply the Lemma). Thus we are ensured that only a constant number of non-degenerate, non-self-revisiting rook moves can end on the same column, giving us the same result as before (Lemma 5.3.3) with the exception of a constant.

Lemma 5.5.7. The number of degenerate rook moves of length 2k is no more than C(N + M)(NM)^{\frac{k}{2k+1}} .

Proof. The proof of this is identical to that of Lemma 5.3.4.

Proof. As before, we count all the rook moves of length 2k starting horizontally. We then subtract all the degenerate rook moves of length 2k. However, we may still have two rook moves which begin on the same column and end on the same row if this corresponds to some combination of odd cycles in the graph G.

Consider the graph G induced by the one-to-one correspondence between some of the rows and some of the columns. Let us call a degenerate cycle of length 4k + 2 any walk (x_{0}, x_{1}, …, x_{4k+1}, x_{0}) such that it is not a normal cycle of length 4k + 2.

Let us count the number of such degenerate cycles beginning at x_{0}. Since the walk begins and ends at x_{0} it must contain some proper cycle which involves x_{0} or otherwise, it is the case that x_{1} = x_{4k+1}. We can repeat this argument recursively to see that a degenerate cycle must be a nested sequence of cycles which touch and walks which are travelled along twice. Since the length of the walk is bounded by 4k + 2 there is only a finite and constant number of ways these walks can be nested (e.g. path of length 2 from x_{0} followed by a cycle of length 5, which has two cycles of length 3 and 7 at its 2nd and 3rd vertices, etc.).

How many proper cycles of length r odd are there from a vertex x_{0} (and any other vertex)? We note that two proper cycles of length r cannot share too many edges for otherwise we would immediately get a cycle of even length less than or equal to 4k + 2. The longest r we are interested in is 4k − 1 and if we have too many such proper cycles sharing the first 2k − 2 edges (say from x_{0} to y) we will get many paths from y to x_{0} each of length 2k + 1. By Lemma 5.5.5 we can only have a constant number of such paths. Thus the number of proper cycles of length 4k − 1 beginning at x_{0} is bounded by a constant times the number of paths of length 2k − 2 beginning at x_{0}. For other values of r < 4k − 1, the number of proper cycles beginning at x_{0} of length r is bounded by a constant times the number of paths of length (r − 1)/2. So, for example, the number of triangles is bounded by a constant times the number of adjacent vertices (in the case of triangles, this constant is 1).

So to count the number of degenerate cycles of a particular type, we use the same method as with the degenerate rook moves. We have the maximum degree of each vertex, and according to whether it is the number of cycles or walks which we want to count next, we can obtain a bound. The whole degenerate cycle is of length 4k+2 so it is composed of walk segments of total length w and cycles of total length c such that 2w +c = 4k +2. But since the number of cycles of length c′ is bounded by walks of length < c′/2, the total such degenerate cycles is bounded by the number of walks of length 2k + 1, with equality if and only if no cycles are present. However if no proper cycles are present in a degenerate cycle, then it is just a walk transversed twice. This corresponds to two identical rook moves and so can be ignored. All the other cases are bounded by a huge constant times the number of paths of length 2k which is the less than the number of rook moves of length 2k − 1, which itself is the same order as the number of degenerate rook moves of length 2k.

Thus from the total number of rook moves of length 2k we subtract those which are involved in degenerate cycles and those which are degenerate rook moves. As before in the proof of Theorem 5.3.1 we obtain the result

X ≤ (NM)^{\frac{k+1}{2k+1}} + C(N + M).

where X is the number of entries in A, and C is a constant which does not depend on N or M (but much larger than in Theorem 5.3.1). This in turn gives

m ≤ \frac{1}{2}n^{\frac{2k+2}{2k+1}} + Cn

for graphs G = G(n, m) with no cycles of even length less than or equal to 4k + 2.

Similarly, we can obtain the result for general graphs with no cycles of even length less than or equal to 4n.

Theorem 5.5.8. Let G = G(n, m) be a graph. If G does not contain any cycles of length 2l where l ≤ 2k then m is less than

\frac{1}{2}n^{\frac{2k+1}{2k}} + Cn,

for some constant C depending only on k.

5.5.2 Lower bound

Can the above construction be reversed? That is, given a bipartite graph H without certain cycles, can we produce a non-bipartite graph G also without those cycles such that if we applied the above construction to G, we would obtain H (or something similar)?

We are particularly interested in whether we can do this for the existing lower bound constructions for the bipartite problem to produce lower bound constructions for the non-bipartite problem. The lower bounds for the bipartite problem agree with the upper bound in that asymptotically, they give the same order of edges, and the constant in front of the highest order term is identical. We would like to do the same for the non-bipartite case.

Thus we want to produce families of graphs G with n vertices and around

m ≈ \frac{1}{2}n^{\frac{l+1}{l}}

edges and no even cycles of length less than or equal 2l.

In fact, suppose we are given a matrix representing a bipartite graph with ‘many’ edges. If we can rearrange the rows so that the matrix becomes (nearly) symmetric, then we can produce a non-bipartite graph with ‘many’ edges, simply by treating the symmetric matrix as the normal adjacency matrix of a graph (after removing a small number of 1s on the diagonal). This is exactly the reverse of the process described in the previous section.

For the C_{4} case, we have already shown that this is possible using polarities (see Theorem 4.3.4). Unfortunately, we have been unable to do so for cycles of longer length. We shall return to this question in the last section of this chapter.

5.6 Improving the hexagon case

A slightly different analysis allows us to reduce the constant for the (N +M) term in the no C_{6}, C_{4} case to the optimal value of 1.

This constant is optimal because by picking M = 1 and N very large and placing 1’s in every position, any smaller constant C < 1 in the bound (NM)^{2/3} + C(N + M) will fail.

Furthermore, for a bipartite graph with C_{6}’s but possibly containing C_{4}’s we prove the bound

X < 2^{1/3}(NM)^{2/3} + C(N + M),

and show that the constant 2^{1/3} is exact by a construction.

Unfortunately, we have been unable to use these methods for any other situations.

Theorem 5.6.1. When k = 1, D_{1} = 1 suffices in Theorem 5.3.1.

Proof. We begin as before, supposing that the result X(n, m) ≤ (nm)^{\frac{2}{3}} + n + m is true ∀(n, m) : n < N and m ≤ M or n ≤ N and m < M. Let A be an N × M matrix of 1s and 0s such that the number of entries with a 1 is X > (NM)^{\frac{2}{3}} + N + M.

Lemma 5.3.2 gives us an easier way to count the number of non-degenerate rook moves which start horizontally. For k = 1, no row contains less than \frac{2}{3}N^{\frac{2}{3}} M^{− \frac{1}{3}} +1 1s and no column has less than \frac{2}{3}M^{\frac{2}{3}} N^{− \frac{1}{3}} +1 1s. All rook moves of length 2 are of the form (x_{0}, x_{1}, x_{2}). Fixing x_{1} we see that the proportion of non-degenerate rook moves to total rook moves is at least:

\frac{\frac{2}{3}N^{\frac{2}{3}} M^{− \frac{1}{3}}}{\frac{2}{3}N^{\frac{2}{3}} M^{− \frac{1}{3}} + 1} × \frac{\frac{2}{3}M^{\frac{2}{3}} N^{− \frac{1}{3}}}{\frac{2}{3}M^{\frac{2}{3}} N^{− \frac{1}{3}} + 1}

This ratio holds for all x_{1} so is true for all rook moves as a whole. So applying the same logic as before we obtain:

\frac{X^{3}}{NM} × \frac{\frac{2}{3}N^{\frac{2}{3}} M^{− \frac{1}{3}}}{\frac{2}{3}N^{\frac{2}{3}} M^{− \frac{1}{3}} + 1} × \frac{\frac{2}{3}M^{\frac{2}{3}} N^{− \frac{1}{3}}}{\frac{2}{3}M^{\frac{2}{3}} N^{− \frac{1}{3}} + 1} ≤ NM.

Rearranging, we get:

X^{3} ≤ (NM)^{2}(1 + \frac{3}{2}N^{− \frac{2}{3}} M^{\frac{1}{3}} )(1 + \frac{3}{2}M^{− \frac{2}{3}} N^{\frac{1}{3}} ).

Now we use the Taylor series for f(x) = x^{\frac{1}{3}} . The third term of the Taylor series is negative, so we can preserve our inequality by using only the first two:

X ≤ (NM)^{\frac{2}{3}} (1 + \frac{1}{2}(N^{− \frac{2}{3}} M^{\frac{1}{3}} + M^{− \frac{2}{3}} N^{\frac{1}{3}} ) + \frac{3}{4}N^{− \frac{1}{3}} M^{− \frac{1}{3}} ).

multiplying out, we get:

X ≤ (NM)^{\frac{2}{3}} + \frac{1}{2}(N + M) + \frac{3}{4}N^{\frac{1}{3}} M^{\frac{1}{3}} .

This is as good as our desired bound of (NM)^{\frac{2}{3}} + (N + M) when:

\frac{3}{2}N^{\frac{1}{3}} M^{\frac{1}{3}} ≤ (N + M).

Let us suppose that M = aN. Substituting this, we get:

\frac{3}{2} ≤ N^{\frac{1}{3}} (a^{\frac{2}{3}} + a^{− \frac{1}{3}} ).

The number a is positive and real and an easy calculation shows that a^{\frac{2}{3}} + a^{− \frac{1}{3}} > 1.889. So we have proved our bound when N > 0.5 which is always the case. This is a contradiction to the fact that X > (NM)^{\frac{2}{3}} + (N + M) and thus no such matrix A exists.

Hence by the inductive hypothesis, Theorem 5.6.1 is true for all N and M.

The next theorem shows that we can remove the no C_{4} condition and do nearly as well.

Theorem 5.6.2. Let A be a matrix with dimensions M × N whose entries are either 1’s or 0’s. If A does not contain any cycles of length 6 then it contains no more than

2^{1/3}(NM)^{\frac{2}{3}} + C(N + M)

for some constant C which does not depend on N or M.

As before, we can obtain a lower bound for the number of entries in each row and column by simply applying the inductive hypothesis. Each row and column contains at least DN^{\frac{2}{3}} M^{− \frac{1}{3}} + C 1’s, for some constant D and the constant C in the theorem.

We will also need the following lemma.

Lemma 5.6.3. Let A be a matrix with no C_{6}’s as above. If two rectangles share an entry, then they must share at least an edge.

Proof. Suppose (x_{1}, a, b, c) and (x_{1}, d, e, f) are (clockwise) rectangles with entries 1, but a, b, c, d, e, f are distinct. Then (a, d, e, f, c, b) is a C_{6}. Thus 2 rectangles involving x_{1} must share an edge.

Now, let us count the number of rook moves of length 2 in A. Firstly, we call a rook move bad if there is another rook move which starts on the same row and ends on the same column such that a (non-degenerate) quadrilateral results. We say two rook moves conflict if they start on the same row and end on the same column so that we obtain a quadrilateral (as opposed to a hexagon).

We call an entry x in A bad if there is a rectangle which involves x. It is clear that an entry x is bad if and only if there is some bad rook move (x_{0}, x_{1}, x_{2}) such that x = x_{1}. From Lemma 5.6.3, it is clear that in fact all rectangles involving a bad entry x share an edge (x, x′). The entry x′ is unique unless there is only one rectangle in A involving x, in which case let us pick x′ so that x and x′ share the same row. In either case, all bad entries are paired up and we call x′ the partner of x.

Finally, we prove the following theorem.

Theorem 5.6.4. Let A be a matrix without hexagons, but possibly with rectangles. Let S denote the set of all rook moves of length 2 (possibly degenerate). Then there is a subset of S′ so that no two non-degenerate rook moves in S′ conflict and

|S′| ≥ \frac{1}{2} |S| .

Proof. For each entry x, let us consider all the rook moves of the form (a, x, b) or (c, x′, d). Let us suppose first that x and its partner x′ are on the same row.

First consider rook moves of the form (a, x, b), where b ≠ x′ and b ≠ x. Since all rectangles involving x also involve x′, the only rook move it conflicts with is (a′, x′, b) (if it exists), where a and a′ are on the same row. We call this rook move the partner of (a, x, b). Clearly, (a, x, b) is also the partner of (a′, x′, b) and the partner is unique.

If a rook move (a, x, b) has no partner, we place it in S′. If it does have a partner, we place one of the partner pair into S′. Thus of rook moves of the type (a, x, b) and (c, x′, d) (where b ≠ x, b ≠ x′, d ≠ x and d ≠ x′) we have placed at least half into S′.

For the remaining rook moves, they are of the form (a, x, x), (a, x, x′), (b, x′, x) and (b, x′, x′). Clearly if (a, x, x) is a rook move then so is (a, x, x′). Let us place (a, x, x) into S′ and do the same for (b, x′, x′). Again we have placed at least half of the rook moves into S′. It is also clear that these rook moves are degenerate.

We now repeat for x such that x and its partner x′ share the same row. The argument is the same here.

Finally, if x is not bad, we place every rook move (a, x, b) into S. It is clear from the construction that no two non-degenerate rook moves in S′ conflict and that we have placed at least half of the rook moves of length 2 into S′.

Let the total number of rook moves of length 2 be R.

As before, we note that if the minimum per column is M_{c} and the minimum per row is M_{r} then at most

R (1 − (1 − \frac{1}{M_{c}} ) (1 − \frac{1}{M_{r}} ))

are degenerate. So the number of rook moves in S′ which are not degenerate is at least

\frac{R}{2} − R (1 − (1 − \frac{1}{M_{c}} ) (1 − \frac{1}{M_{r}} )) .

It is easy to ensure that M_{c} and M_{r} are at least 4 so finally we can use R ≥ X^{3}/(NM) and get

\frac{X^{3}}{NM} ((1 − \frac{1}{M_{c}} ) (1 − \frac{1}{M_{r}} ) − \frac{1}{2}) ≤ NM
X^{3} ≤ 2N^{2}M^{2} (\frac{1}{2 (1 − \frac{1}{M_{c}} ) (1 − \frac{1}{M_{r}} ) − 1})
X^{3} ≤ 2(NM)^{2} (\frac{M_{c}}{M_{c} − 3}) (\frac{M_{r}}{M_{r} − 3}) .

(In the last inequality, we use the fact that 1−2/M_{c}−2/M_{r}+2/(M_{c}M_{r}) > (1 − 3/M_{c})(1 − 3/M_{r}), when M_{c} and M_{r} are not too small.)

We can now repeat the calculation as for Theorem 5.6.1 except we will get different constants. In any case we obtain a bound of

X < 2^{1/3}(NM)^{\frac{2}{3}} + C(N + M)

for some constant C.

The constant 2^{1/3} is sharp. To prove this, let us consider the following construction.

Construction 5.6.5. Let A be a N by M matrix with no cycles of length 4, 6 … 2l. Construct a matrix B with dimensions (l − 1)N by M simply by inserting an extra l − 2 identical copies of each column.

Then B contains no cycles of length 2l.

Proof. The proof is not hard. Let us call all the copies in B of a particular column in A a component. We can map each entry in B to a unique entry in A by mapping any entry in a component to the corresponding entry in the particular column of A. Let us do so for a cycle of length 2l in B.

It is clear that this gives us ‘degenerate’ cycle of length 2l in A. Since A has no cycles of shorter length, this ‘degenerate’ cycle does not contain any shorter subcycles and this can only happen if all the entries of it lie in a single column of A if the original cycle in B was not degenerate. That means the original cycle belonged within some component of B. However, a component of B is just a (l − 1) by M matrix which cannot contain any cycles of length 2l.

We have already given N by N matrices with N^{4/3} entries and no cycles of length 4 or 6 (for arbitrarily large N). Applying Construction 5.6.5 we see that we can get a 2N by N matrix with 2N^{4/3} entries and no cycles of length 6. This shows the constant 2^{1/3} in the theorem is sharp.

5.7 Conjectures and discussion

Let us first summarize our results. For the upper bound problem of bipartite and general graphs without even cycles of lengths less than 2k, our results give the first reasonable (as in possibly sharp) constants for the highest order term, for k ≥ 4. Furthermore, for the bipartite C_{6} and C_{10} cases, our constant is indeed sharp and improves upon existing results. In fact, we have done even better and found the correct lower order term (correct for the important square case which relates to general non-bipartite graphs). For the C_{4} case both our bipartite and non-bipartite results agree with the best in the literature (which in fact is the true answer), and this suggests that many of our other results may also be best possible. Some of these results will be appearing in [29].

Our result for bipartite graphs without C_{6}’s only is exceptional in that it does not fit with the results above. However, it is still the strongest result of its kind near the region M = N. We have further shown that the constant of the highest order term is sharp. The construction is slightly unsatisfactory as it is a 2M × M example, when the square case is of the most interest.

In the final part of this chapter, we shall discuss a number of results we believe to be true but have been unable to prove. Some results we have been able to prove in very specific cases but not in full generality.

We begin by conjecturing a stronger version of Theorem 5.4.1, which agrees for the case N = M.

Conjecture 5.7.1. Let A be a matrix with dimensions M ×N whose entries are either 1’s or 0’s. If A does not contain any cycles of length 2l where l ≤ 2k then the number of entries with a 1 in A is no more than the minimum of

N^{\frac{1}{2}} M^{\frac{k+1}{2k}} + C_{k}(N + M),

and

M^{\frac{1}{2}} N^{\frac{k+1}{2k}} + C_{k}(N + M),

for some constant C_{k} depending only on k.

The only difference here is that we believe the correct bound should be the minimum of the two formulae, rather than the maximum. There is quite a bit of evidence to suggest it. Firstly, this conjecture is true for the case k = 1. The number of 1’s in a matrix A with rectangles is bounded by both NM^{1/2} + O(M) and MN^{1/2} + O(N). The second reason is that for small N and large M or for small M and large N, one bound is ridiculously larger than the other, and the smaller bound appears to be closer to the truth.

The results concerning the exact constants for the O(N + M) term for the C_{6} case suggest similar constants in general. In fact, we can conjecture Conjecture 5.7.2. The constants in Theorem 5.4.1 and Theorem 5.3.1 can be 1.

This seems likely because if we look at the lower bounds given by Benson’s projective plane constructions, we have bipartite graphs with approximately

N^{4/3} + \frac{2}{3}N

edges. Thus for the case when N = M, even a constant of C = 1 in Theorem 5.3.1 is not optimal. The same is true for the other of Benson’s constructions, the C(N + M) term has constant much less than 1. We might expect that this would be true in general, in which case the constant in the lower order term would be determined by the behaviour when N >> M or M >> N. In those cases a constant of C = 1 seems likely.

On the side of the lower bounds, we believe that the higher order term of our theorems are exact.

Conjecture 5.7.3. There exist bipartite graphs with vertex parts of sizes N and N, for arbitrarily large N, which do not contain any cycles of length 4, 6, … 2l and nearly

CN^{(l+1)/l}

edges for some constant C.

So far such graphs have only been found for l = 2, 3 and 5. The constructions given in Section 4.6 describe the unresolved situation for other values of l.

The situation for extremal non-bipartite graphs is even more tenuous. The constant in front of the highest order term has only been settled for the case l = 2. In that case we have already described graphs with \frac{1}{2}n^{3/2} edges and n vertices. Our upper bound shows that in general no constant greater than c = \frac{1}{2} can work for families of graphs with cn^{(l+1)/l} edges, n vertices and no even cycles of length less than or equal to 2l.

In a subtle twist, Lazebnik, Ustimenko and Woldar [31] show that extremal non-bipartite graphs without cycles of length 2l will indeed contain cycles of shorter length. That is, the shorter cycles make a significant difference in non-bipartite graphs, a question which is not resolved for the square bipartite graphs.

For the cases l = 3, 5, Lazebnik, Ustimenko and Woldar [31] show that we can have non-bipartite graphs with

((l − 1)l^{−(l+1)/l} + o(1))n^{(l+1)/l}

edges, n vertices and no cycles of length 2l. The constant is reasonably close to the upper bound constant of 1/2 for graphs with no cycles of length less than or equal to 2l. Furthermore, for the hexagon case, the above constant agrees with the one we would obtain if we treated Construction 5.6.5 as a non-bipartite graph.

Non-self-crossing hexagons

There are some similar and related problems which are more natural in the matrix formulation than in the graph formulation. We shall consider the following problem.

Problem 6.0.4. Let I be a N × N matrix of 1’s and 0’s. How many 1’s can I have if it possesses neither a rectangle nor a non self-crossing hexagon?

We would expect that I could possess more 1’s than matrices without general hexagons and rectangles but less 1’s than a matrix which was restricted only by rectangles. But asymptotically, are non self-crossing hexagons such an obstacle? Do we have many less 1’s than matrices with only rectangles?

We have to be careful with our intuition though. As we saw in Section 5.6 matrices without hexagons or rectangles can have nearly as many 1’s as matrices without only hexagons. The former case is strictly more restrictive, but asymptotically the additional condition only effects the constant, not the power of the highest order term.

In fact Katz [26] proved that non self-crossing hexagons do indeed make a significant difference. Let us first make the following definitions:

Definition 6.0.5. A N ×N matrix I_{ij} of 1’s and 0’s is said to have property A if it does not contain a rectangle of 1’s.

Definition 6.0.6. A matrix I_{ij} is said to satisfy property A+ if it satisfies property A and if there do not exist i_{1} < i_{2} < i_{3} and j_{1} < j_{2} < j_{3} so that the

Figure 6.1: Non-self-crossing hexagon

•  • • • • •

Figure 6.2: Self-crossing hexagon

•  • • • • •

3 × 3 matrix

J_{αβ} = I_{i_{α}i_{β}}

contains six 1’s and so that J_{22} = 1.

The latter condition is equivalent to not containing any non self crossing hexagons.

Definition 6.0.7. A matrix I is a (C, ϵ) example of property A if it satisfies property A and

∑_{i} ∑_{j} I_{ij} ≥ CN^{\frac{3}{2} −ϵ}.

That is, it contains at least CN^{\frac{3}{2} −ϵ} 1’s.

Katz [26] proved the following theorem:

Theorem 6.0.8. There exist universal constants C, ϵ > 0 so that if I is a matrix satisfying property A+ then

∑_{i} ∑_{j} I_{ij} ≤ CN^{\frac{3}{2} −ϵ}.

Here, we will follow the same approach as Katz, except that we will actually find a value of ϵ which works.

The strategy is as follows. We will begin with a matrix I which is a (C, ϵ) example for property A+ and then by removing a small number of 1’s we can show that it has additional properties: indeed that the new matrix will be a (C′, ϵ′) example of these additional properties, where C′ and ϵ′ depend only on C and ϵ but not on N.

Some of these additional properties are similar to the ones we used in the previous chapter, for example, we want to ensure no column or row has too many 1’s. However, we will be requiring other properties that give the 1’s in the matrix more structure before we can prove that it contains a non-self-crossing hexagon.

6.1 Cauchy-Schwarz Inequality

We will be using the Cauchy-Schwarz Inequality many times in a particular form, so we begin by illustrating its use on our standard example of matrices without rectangles.

Let I be a N × N matrix of 1’s and 0’s satisfying property A. If we let

a_{i} = ∑_{j} I_{ij},

be the number of 1’s in each row then counting pairs of rows we easily obtain:

∑_{i} \binom{a_{i}}{2} ≤ \binom{N}{2}.

We can perform an exact analysis at this point, but for our purposes we estimate \binom{a_{i}}{2} by a_{i}^{2},

∑_{i} a_{i}^{2} ≤ CN^{2},  (6.1)

for some constant C.

We apply the Cauchy-Schwarz Inequality in the following form:

Theorem 6.1.1 (Cauchy-Schwarz). Let a_{i} and b_{i} be non-negative real numbers for 1 ≤ i ≤ n. Then

( ∑_{i}(a_{i}^{2}))( ∑_{i}(b_{i}^{2})) ≥ ( ∑_{i}(a_{i}b_{i}))^{2}.

In particular, setting b_{i} = 1 for all i, we obtain

( ∑_{i}(a_{i}^{2}))(1 + 1 + … + 1) ≥ ( ∑_{i}(a_{i}))^{2}.

Substituting this into 6.1,

∑_{i} a_{i} ≤ CN^{3/2}
∑_{i,j} I_{ij} ≤ CN^{3/2}.

This result we have proved already many times. For the remaining sections, when the Cauchy-Schwarz Inequality is applied we will not perform the calculations explicitly, as we have done above, but simply state the result.

6.2 Proof of Theorem

Throughout this proof, we will be careful with the powers of N, usually involving ϵ, but be less than careful with constants. In fact, we will always assume N is at least a certain size and that some constant will work for those N for each step of the process.

Definition 6.2.1. A matrix I satisfies property B if, for every i, one has

∑_{j} I_{ij} ≤ CN^{\frac{1}{2} +ϵ},

and for every j, one has

∑_{i} I_{ij} ≤ CN^{\frac{1}{2} +ϵ}.

In such a case, I will be called a (C, ϵ) example of B.

Lemma 6.2.2. Given I a (C, ϵ) example for property A, and ϵ sufficiently small, there exist C′,C′′ depending only on (C, ϵ) and J a subset of I such that J is a (C′, 2ϵ) example of property B and a (C′′, ϵ) example of property A.

Proof. Let us count the number of rows I_{i}, where

∑_{j} I_{ij} ≥ C′N^{\frac{1}{2} +ϵ′}.

We call this set of i’s E and using property A we know that there are no more than M = \frac{2}{C′} N^{1−ϵ′} i’s in E. Let us now count the number of 1’s in all these rows.

∑_{i∈E} ∑_{j=1}^{N} I_{ij} ≤ M^{\frac{1}{2}} (∑_{i∈E}(∑_{j=1}^{N} I_{ij})^{2})^{\frac{1}{2}}  (Cauchy-Schwarz)

≤ M^{\frac{1}{2}} (∑_{i∈E} ∑_{j_{1}=1}^{N} ∑_{j_{2}=1}^{N} I_{ij_{1}}I_{ij_{2}})^{\frac{1}{2}}

≤ M^{\frac{1}{2}} (N^{2} + NM)^{\frac{1}{2}}  (Property A)

≤ 2NM^{\frac{1}{2}} = \frac{4}{C′} N^{\frac{3}{2} − \frac{ϵ′}{2}} .

Thus for N sufficiently large, this set of 1’s will be small compared to the existing set of 1’s when ϵ′ > 2ϵ. By picking an appropriate (large) constant C′ and removing the rows in E, we can ensure the result of the Lemma for ϵ′ = 2ϵ. We then repeat for columns and the Lemma is proved.

Our next step is to introduce the NK-cells which provides a very strong restriction on where the 1’s can be located. At this point let us assume that N is a perfect fourth power, for otherwise we can add O(N^{3/4}) empty rows and columns which will only affect the C in a (C, ϵ) example but not the ϵ.

Definition 6.2.3. Let C_{1}, …, C\sqrt{N} be sets of integers defined thus:

C_{j} = \{k : (j − 1)\sqrt{N} < k ≤ j\sqrt{N}\} .

These are our NK-cells. A matrix I has property C if for every i and l,

∑_{j∈C_{l}} I_{ij} ≤ 1,

and for every j and l,

∑_{i∈C_{l}} I_{ij} ≤ 1.

Furthermore, we say that (a row) i talks to a cell C_{l}, if

∑_{j∈C_{l}} I_{ij} > 0.

For such a case, we write i ∗ l. Similarly, we define a column j talking to a cell C_{l}.

Lemma 6.2.4. Given a matrix I of 1’s and 0’s which is a (C, ϵ) example of Property A and a (C′, 2ϵ) example of Property B, we can find J which is a subset of I, a (C′′, 17ϵ) example of Property A which also satisfies Property C.

Proof. Let us first remove all those i’s which talk to no more than R = N^{\frac{1}{2} −ϵ′} many cells. We call this set of i’s E, and proceed to count the number of 1’s in these cells.

∑_{i∈E} ∑_{j} I_{ij}

= ∑_{i∈E} ∑_{l:i^{∗}l} ∑_{j∈C_{l}} I_{ij}

≤ (N × R)^{\frac{1}{2}} (∑_{i∈E} ∑_{l:i^{∗}l}(∑_{j∈C_{l}} I_{ij})^{2})^{\frac{1}{2}}

≤ N^{\frac{3}{4} − \frac{ϵ′}{2}} (∑_{l=1}^{\sqrt{N}} ∑_{j_{1}∈C_{l}} ∑_{j_{2}∈C_{l}} ∑_{i∈E} I_{ij_{1}}I_{ij_{2}})^{\frac{1}{2}}

≤ N^{\frac{3}{4} − \frac{ϵ′}{2}} (N^{\frac{3}{2}} + ∑_{i∈E} ∑_{j} I_{ij})^{\frac{1}{2}}

≤ 3N^{\frac{3}{2} − \frac{ϵ′}{2}} .

We have used the Cauchy-Schwarz inequality in the first inequality and counted j_{1} = j_{2} and j_{1} ≠ j_{2} separately to obtain the second last inequality.

When ϵ′ ≥ 2ϵ this is small compared to the existing number of 1’s and can be removed. What remains is still C′′N^{\frac{3}{2} −ϵ} 1’s and since there are at most CN^{\frac{1}{2} +2ϵ} 1’s in each row by property B, we have at least C′′′N^{1−3ϵ} non empty rows. We proceed to remove all but one of the 1’s in each cell of each of these remaining rows which leaves us with at least DN^{\frac{3}{2} −5ϵ} 1’s.

Now we have to repeat for the columns, which leaves us with D′N^{\frac{3}{2} −17ϵ} 1’s for some constant D′.

Now we will begin using an extra notation. Given I a matrix of 1’s and 0’s, I_{ij} denotes the value at entry (i, j). We will further say that (i, j) ∈ I.

We will say two positions (i, j) and (i′, j′) are connected by a rook move if they are connected by a non-degenerate rook move of length 1 as per our previous definition. In fact it is clear that we can define a unique rook distance between any two positions in I (possibly ∞).

Definition 6.2.5. A matrix of 1’s and 0’s I is said to satisfy Property D if there exists a position (i_{0}, j_{0}) ∈ I so that the rook distance from any (i, j) ∈ I to the distinguished point (i_{0}, j_{0}) is less than or equal to 3.

Lemma 6.2.6. Let I be a matrix which is a (C, ϵ) example of Property A which satisfies Property C. Then there exists a subset J of I which is a (C′, 7ϵ) example of Property A which satisfies Property D.

Proof. For now, we will omit the constants in our estimations, but will compensate for that by allowing our final constant to change.

Denote by G_{1} the set of i’s for which there exist at least N^{\frac{1}{2} −ϵ_{1}} many j’s for which (i, j) ∈ I. We want to ensure that there are at least N^{1−ϵ_{1}} many such i’s. By Property C, no row has more than N^{\frac{1}{2}} 1’s, so we can ensure this is the case if

N^{\frac{1}{2}} × N^{1−ϵ_{1}} + (N − N^{1−ϵ_{1}}) × N^{\frac{1}{2} −ϵ_{1}} ≤ CN^{\frac{3}{2} −ϵ}
2N^{\frac{3}{2} −ϵ_{1}} − N^{\frac{3}{2} −2ϵ_{1}} ≤ CN^{\frac{3}{2} −ϵ}.

Apart from a possible problem with the constant, ϵ_{1} = ϵ works.

Call the G_{1} the good rows. Similarly let G_{2}, the good columns, be the set of j such that there are at least N^{1−2ϵ} values of i ∈ G_{1} such that (i, j) ∈ I.

An identical argument to above proves that that there are at least N^{\frac{1}{2} −2ϵ} such j (just consider the matrix with 1’s off the good rows removed). Finally, we can find some i_{0} such that (i_{0}, j) ∈ I for N^{\frac{1}{2} −4ϵ} many j ∈ G_{2}.

Using Property A, we see that all the good rows that can be reached from (i_{0}, j) (distance 2) can be reached in only one way. This shows that the subset of 1’s which are within a rook distance of 3 from (i_{0}, j) is at least CN^{\frac{1}{2} −7ϵ} 1’s. Thus there is a subset which satisfies Property D and is a (C, 7ϵ) example of Property A (assuming N is sufficiently large).

So far we have not used Property A+, that there are no non self-crossing hexagons. This will be used in the final Lemma where we utilise all the existing properties to show that for Property A+ forces ϵ to be at least a certain value.

Lemma 6.2.7. Let I be a (C, ϵ) example for Property A which also satisfies Property C and Property D. If C is sufficiently large and ϵ < \frac{1}{52} then I cannot satisfy Property A+.

Proof. Let (i_{0}, j_{0}) be the position from which all positions have rook distance at most 3. Without affecting the value of ϵ but only that of C, we can assume that for all (i, j) ∈ I, i > i_{0} and j > j_{min} for some j_{min}.

We call the set of j such that (i_{0}, j) ∈ I the range, R.

Now pick some j ∉ R. For each NK-cell C_{l} there is at most one i such that (i, j) ∈ I. We call the set of l’s such that such an i exist the domain of j, D_{j}. For any l ∈ D_{j} there is exactly one j′ ∈ R so that (i, j′) ∈ I for some i ∈ C_{l} by Property D.

Next define a function

f_{j} : D_{j} → R,

by

f_{j}(l) = j′.

Assume now that I contains no non self-crossing hexagons (Property A+). By a drawing a diagram, we see that the functions f_{j} satisfy the following

conditions:

1. f_{j} is monotone increasing. This follows from the fact that I contains

no non-self-crossing hexagons:

[figure: j_{min}; f_{j}(l_{1}); f_{j}(l_{2}); f_{j}(l_{3}); j; i_{0}; •; •; •; •; •; •; •; •; •; •]

2. For any j_{1} ≠ j_{2}, both not in R, there cannot be l_{1} ≠ l_{2} both in D_{j_{1}} and D_{j_{2}} such that

f_{j_{1}}(l_{1}) = f_{j_{2}}(l_{1})(= a)
f_{j_{1}}(l_{2}) = f_{j_{2}}(l_{2})(= b).

Suppose i^{∗} ∈ l_{1} such that (i^{∗}, j_{1}) ∈ I and thus (i^{∗}, a) ∈ I. If i^{∗} ∈ l_{1} is such that (i′, j_{2}) ∈ I then (i′, a) ∈ I and so we have (i^{∗}, a) and (i′, a) both in I and i^{∗}, i′ ∈ C_{l}. This is forbidden by NK-cellyness unless i^{∗} = i′ = i_{1}. Repeating the argument we get

(i_{1}, j_{1}), (i_{1}, j_{2}), (i_{2}, j_{1}), (i_{2}, j_{2}) ∈ I.

This is forbidden by Property A. We call this property the disjointness condition.

We now order the elements j ∈ R from smallest to largest as j^{1}, …, j^{M} with M ≤ \sqrt{N}. And define p(j^{k}) = k. Similarly we order l ∈ D_{j} as l_{j,1}, …, l_{j,M_{j}}.

We now consider the following expression:

T = ∑_{j∉R} ∑_{k=2}^{M_{j}}(p(f_{j}(l_{j,k})) − p(f_{j}(l_{j,k−1}))).

This sum we call the ‘total variation’. Since each f_{j} is monotone increasing, so is p ∘ f. Thus for each j, the inner sum has value

p(f_{j}(l_{j,M^{k}})) − p(f_{j}(l_{j,1})) ≤ \sqrt{N} − 1 ≤ \sqrt{N}.

We then have to sum over all j ∉ R which is certainly less than N different j’s.

Thus we obtain

T ≤ N^{\frac{3}{2}} .

We shall now compute T in a different way.

Define S_{1}, …, S_{N^{\frac{1}{4}}} as the NK-cells in the set \{1, …, N^{\frac{1}{2}} \}. Thus we have S_{1} = \{1, 2, 3, …, N^{\frac{1}{4}} \} for example. We want to find ϵ′ so that there are at least N^{\frac{1}{4} −ϵ′} values of k so that there are at least N^{1−ϵ′} values of j for which there are at least N^{\frac{1}{4}} − ϵ′ many values of l ∈ S_{k} for which l ∈ D_{j}.

The total number of l and j such that l ∈ D_{j} is at least C′N^{\frac{3}{2} −ϵ}. Call such pairs of l and j inclusions. Let there be K values of k such that there are at least N^{1−ϵ′} values of j for which there are at least N^{\frac{1}{4}} −ϵ′ many values of l ∈ S_{k} for which l ∈ D_{j}. Then for these other values of k there are at most

N^{1−ϵ′} × N^{\frac{1}{4}} + (N − N1 − ϵ′) × N^{\frac{1}{4} −ϵ′} ≤ 2N^{\frac{5}{4} −ϵ′}

inclusions. Thus the total number of inclusions is at most

(N^{\frac{1}{4}} − K) × CN^{\frac{5}{4} −ϵ′} + K × N^{\frac{5}{4}} ≤ KN^{\frac{5}{4}} + 2N^{\frac{5}{4} −ϵ′}.

Set ϵ′ = ϵ. For sufficiently large C′, we see that K ≥ N^{\frac{1}{4} −ϵ}.

For any such value of k, we can find two elements l_{1} and l_{2} both in S_{k} such that there are N^{1−3ϵ} values of j for which l_{1}, l_{2} ∈ D_{j}. To prove this note that for each there are N^{1−ϵ} values of j which have at least N^{\frac{1}{2} −2ϵ} pairs of l, l′ ∈ S_{k} in D_{j}. But there are only N^{\frac{1}{2}} many pairs l, l′ ∈ S_{k} so we can find one particular pair which has at least N^{1−3ϵ} values of j for which the pair is in D_{j}.

Limit our attention to the one particular member of that pair, l_{1} for the moment and assume l_{2} > l_{1}. There are only at most N^{\frac{1}{2}} values of j for which f_{j}(l_{1}) = i for any particular i by NK-cellyness. Thus there are at least N^{\frac{1}{2} −3ϵ} collections of j’s each of which with at least N^{\frac{1}{2} −3ϵ} elements, which we call J_{1}, …, J_{K} such that for any 2 j_{1}, j_{2} ∈ J_{n}, f_{j_{1}}(l_{1}) = f_{j_{2}}(l_{2}).

Then within each T_{n}, by disjointness, f_{j_{2}}(l_{1}) ≠ f_{j_{2}}(l_{2}). Now consider

∑_{j∈T_{n}}(p(f_{j}(l_{2})) − p(f_{j}(l_{1}))).

The value in the bracket is a positive integer which is different for each j. The smallest possible value is thus 1 + 2 + … + |T_{n}|. Hence we obtain

∑_{j∈T_{n}}(p(f_{j}(l_{2})) − p(f_{j}(l_{1}))) ≥ \frac{1}{2}N^{1−9ϵ}.

Summing over n, we obtain

∑_{n=1}^{K} ∑_{j∈T_{n}}(p(f_{j}(l_{2})) − p(f_{j}(l_{1}))) ≥ \frac{1}{2}N^{\frac{3}{2} −12ϵ}.

Since this happens in N^{\frac{1}{4} −ϵ} cells S_{k} we find that the following bound on the total variation:

T ≥ CN^{\frac{7}{4} −13ϵ}.

When

ϵ < \frac{1}{52}

we obtain a contradiction.

Lemmas 6.2.2, 6.2.4, 6.2.6, 6.2.7 clearly imply Theorem 6.0.8. In fact, if we follow the ϵ through the 4 Lemmas, we see that we have shown

Theorem 6.2.8. There exists a constant C such that whenever a matrix I of 1’s and 0’s contains more than

CN^{\frac{3}{2} − \frac{1}{6188}}

1’s then it must contain either a rectangle or a non-self-crossing hexagon.

6.3 Applications

The question of graphs without non-self-crossing hexagons can only be phrased in graph theory if the vertex sets are given orderings, and as such it is not the most natural question to ask in a graph theory context.

However, this question is possibly more natural in a very different context. Let f(x, y) be a twice differential function

f : R^{2} → R

and suppose that

\frac{∂}{∂x} \frac{∂}{∂y} f(x, y) ≥ λ,

for some positive real λ > 0. Let S = {(x, y) : f(x, y) = 0} be the zero set of f. Then it is a simple application of the fundamental theorem of calculus to see that S cannot contain the vertices of a rectangle with sides parallel to the coordinate axes. In fact, S cannot possibly contain any non self-crossing polygons with sides parallel to the coordinate axes.

Thus if we are interested in the zeroes of f on a set of lattice points, we can give a bound on the number of zeroes using Theorem 6.0.8. Of course a harder question to ask is

How many 1’s can a N × N matrix I of 1’s and 0’s have without containing any non-self-crossing polygon?

This problem seems rather hard to approach. From the results in Theorems 5.3.1 and 5.4.1 we might expect that as we forbid more polygons, we would significantly reduce the number of 1’s allowed. However, the difficulty of tackling the non-self-crossing hexagons suggests that any such result, if true, would be very hard to prove. The difficulty here is similar to the difficulty in removing the shorter cycle restrictions for example in Theorem 5.6.2. If we perform any counting argument too generally, then most of the time we mix allowable cycles with not allowable cycles which are hard to separate. The only way for this to work seems to be by providing a strong structure to the matrices and graphs we investigate.

Bibliography

[1] R. Artzy, Self-dual configurations and their Levi graphs, Proc. Amer. Math. Soc. 7 (1956), 299-303.

[2] R. Baer, Polarities in finite projective planes, Bull. Amer. Math. Soc. 52 (1946), 77-93.

[3] C. Benson, Minimal Regular Graphs of Girths Eight and Twelve, Canad. J. Math, 26, (1966), 1091-1094.

[4] N.L. Biggs and M.J. Hoare, The sextet construction for cubic graphs, Combinatorica 3 (1983), 153-165.

[5] B. Bollobás, Graph theory, Springer-Verlag New York Inc., 1979.

[6] B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978.

[7] J. A. Bondy, Large cycles in graphs, Discrete Math., 1 (1971), 121-132.

[8] J.A. Bondy, M. Simonovits, Cycles of even lengths in graphs, J. Combin. Theory Ser. B, 16, (1974) 97-105.

[9] S. Brandt, Cycles and paths in triangle-free graphs, in The Mathematics of Paul Erdős, Vol. II (eds. R.L. Graham and J. Nešetřil), Algorithms and Combinatorics, 14, Springer Verlag, Berlin, 1997, 32-42.

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

[11] 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, Colloq. Math. Soc. János Bolyai 60, Budapest, 1991, 135-142.

[12] 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, (1997), 268-278.

[13] C.R.J. Clapham, A. Flockart, and J. Sheehan, Graphs without fourcycles J. Graph Theory 13 (1989), 29-47.

[14] P. Erdős, Remarks on a paper of Pósa, Publ. Math. Inst. Hungar. Acad. Sci, 7 (1964), 29-36.

[15] P. Erdős, Extremal problems in graph theory, ‘Theory of Graphs and Its Applications’ (M.Fiedler, Ed.), Academic Press, New York, 1965.

[16] P. Erdős, On some extremal problems in graph theory, Israel J. Math. 3 (1965), 113-116.

[17] P. Erdős, On sequences of integers no one of which divides the product of two others and on some related problems, Izv. Nauk Mat. i Mech. Tomsk 2 (1938), 74-82.

[18] P. Erdős, A. Sárközy and V.T.Sós, On product representations of powers I, European J. Combin. 16 (1995), 567-588.

[19] P. Erdős, H. Sachs, Reguläre Graphen gegebener Taillenweite und minimaler Knotenzahl, Wiss. Z. Univ. Halle Martin-Luther Univ. Halle-Wittenberg Math.-Natur. Reihe 12 (1963) 251-257.

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

[21] R.J. Faudree and M. Simonovits, On a class of degenerate extremal graph problems, Combinatorica 3 (1983), 83-93.

[22] Z. Füredi, Graphs without quadrilaterals, J. Combin. Theory Ser. B, 34 (1983), 187-190.

[23] Z. Füredi, On the Number of Edges of Quadrilateral-Free Graphs, J. Combin. Theory Ser. B, 684 (1996), 1-6.

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

[25] W. Imrich, explicit construction of graphs without small cycles, Combinatorica 2 (1984), 53-59.

[26] N.H. Katz, ‘The discrete hexagon lemma’, in unpublished manuscript.

[27] N.H. Katz, T. Tao, Bounds on arithmetic progressions and applications to the Kakeya conjecture, Math. Res. Letters 6 (1999), 625-630.

[28] T. Kővári, V.T. Sos and P. Turan, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954) 50-57.

[29] T. Lam, Graphs without cycles of even length, Bull. Austral. Math. Soc., 63 (2001), 435-440, to appear.

[30] F. Lazebnik and V.A. Ustimenko, New examples of graphs without small cycles and of large size, European J. Combin. 14 (1993), 445-460.

[31] F. Lazebnik, V.A. Ustimenko and A.J. Woldar, Properties of certain families of 2k-cycle free graphs, J. Combin. Theory Ser. B. 60 (1994), 293-298.

[32] F. Lazebnik, V.A. Ustimenko and A.J. Woldar, New constructions of bipartite graphs on m, n vertices with many edges and without small cycles, J. Combin. Theory Ser. B. 61 (1994), 111-117.

[33] F. Lazebnik, V.A. Ustimenko and A.J. Woldar, A new series of dense graphs of high girth, Bull. Amer. Math. Soc. 32 (1995), 73-79.

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

[35] J.Q. Longyear, Regular d-valent graphs of girth 6 and 2(d^{2} − d + 1) vertices, J. Combinatorial Theory 9 (1970) 420-422.

[36] A.Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261-277.

[37] G.A. Margulis, Explicit construction of graphs without short cycles and low density codes, Combinatorica 2 (1982), 71-78.

[38] P. Sarnak, Some applications of modular forms, Cambridge Tracts in Math., Vol. 99, Cambridge Univ. Press. Cambridge, 1990.

[39] G.N. Sáközy, Cycles in bipartite graphs and an application in number theory, J. Graph Theory 19 (1993), 323-331.

[40] N. Sauer, Extremaleigenschaften reguläre Graphen gegebener Taillenweite, I and II, Sitzungsberichte Österrich. Akad. Wiss. Math. Natur. Kl., S-B II,176 (1967) 9-25, ibid 176 (1967) 27-43.

[41] M. Simonovits, Paul Erdős’ influence on extremal graph theory, in The Mathematics of Paul Erdős, Vol. II (eds. R.L. Graham and J. Nešetřil), Algorithms and Combinatorics, 14, Springer Verlag, Berlin, 1997, 148-192.

[42] R. Singleton, On Minimal Graphs of Maximum Even Girth, J. Combinatorial Theory. 1 (1966), 215-235.

[43] P. Turán , On an extremal problem in graph theory, Mathematical Lapok, 48 (1941), 426-452.

[44] W.T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947), 459-474.

[45] H. Walther, Eigenschaften von regulären Graphen gegebener Taillenweite und minimaler Knotenzahl, Wiss Z. Ilmenau, 11 (1965) 167-168.

[46] H. Walther, Über regulären Graphen gegebener Taillenweite und minimaler Knotenzahl, Wiss Z. Techn. Hochsch. Ilmenau, 11 (1965) 93-96.

[47] R. Wenger, Extremal Graphs with no C^{4}’s, C^{6}’s, or C^{10}’s, Journal of Combinatorial Theory, Series B, 52, (1991), 113-116.

[48] D. R. Woodall, Thrackles and deadlock, in ‘Combinatorial Mathematics and its Applications’ (Welsh, D.J.A., ed.), Academic Press, London and New York (1971), 335-347.

[49] Y. Yuansheng, P. Rowlinson, On extremal graphs wthiout four-cycles, Utilitas Math. 41 1992, 204-220.