Preprint in the style of Combinatorics, Probability and Computing \begin{matrix}c \\ ◯ \end{matrix} 1998 Cambridge University Press

A Note on Bipartite Graphs without 2k-Cycles.

ASSAF NAOR JACQUES VERSTRAËTE

Microsoft Research  Faculty of Mathematics
One Microsoft Way  University of Waterloo
Redmond, WA 98052-6399  200 University Avenue West
United States  Waterloo, Canada N2L 3G1

The question of the maximum number ex(m, n, C_{2k}) of edges in an m by n bipartite graph without a cycle of length 2k is addressed in this note. For each k ≥ 2, it is shown that

ex(m, n, C_{2k}) ≤ \{ \begin{matrix}(2k − 3) [(mn)^{\frac{k+1}{2k}} + m + n] & if k is odd. \\ (2k − 3) [m^{\frac{k+2}{2k}} n^{\frac{1}{2}} + m + n] & if k is even. \end{matrix}

1. Introduction

In this note, we study the maximum number of edges in an m by n bipartite graph containing no 2k-cycles. This problem was studied in the papers by Erdős, Sós and Sárközy [3] and by Győri [4], in the context of a number theoretic problem. It is also related to the size of subsets of points in projective planes, such as arcs and caps. A connection to a geometric problem involving points and lines in Euclidean space is described in de Caen and Székely [1].

Throughout the material to follow, γ(m, n, g, k) denotes the maximum number of edges in an m by n bipartite graph of girth at least 2g containing no 2k-cycle. In particular, we write γ(m, n, 2, k) = ex(m, n, C_{2k}), which is the maximum number of edges in a 2kcycle-free m by n bipartite graph. For d, g ≥ 2, let c(d, g) be the largest integer such that every bipartite graph of average degree at least 2d and girth at least 2g contains a cycle of length at least c(d, g) with at least one chord. Our main result is as follows:

Theorem 1. Let k, g ≥ 2 be integers. Then, for any d such that c(d, g) ≥ 2(k − g + 1),

γ(m, n, g, k) ≤ \{ \begin{matrix}2d[(mn)^{\frac{k+1}{2k}} + m + n] & if k is odd. \\ 2d[m^{\frac{k+2}{2k}} n^{\frac{1}{2}} + m + n] & if k is even. \end{matrix}

Theorem 1 depends explicity on the parameter c(d, g). Let us make a few remarks about c(d, g). First, a straightforward argument shows that c(d, g) ≥ 2d(g − 1) + 1. Stronger results were obtained by Erdős, Faudree, Rousseau, and Schelp [2]. We deduce from their paper that c(d, g) ≥ d^{g/4}. In particular, by using these two bounds on c(d, g) in Theorem 1, we respectively obtain the following two corollaries:

Corollary 2.

ex(m, n, C_{2k}) ≤ \{ \begin{matrix}(2k − 3)[(mn)^{\frac{k+1}{2k}} + m + n] & if k is odd. \\ (2k − 3)[m^{\frac{k+2}{2k}} n^{\frac{1}{2}} + m + n] & if k is even. \end{matrix}

Corollary 3. For any number δ > 0, there exists a constant c(δ) such that

γ(m, n, δ log k, k) ≤ \{ \begin{matrix}c(δ)[(mn)^{\frac{k+1}{2k}} + m + n] & if k is odd. \\ c(δ)[m^{\frac{k+2}{2k}} n^{\frac{1}{2}} + m + n] & if k is even. \end{matrix}

Using the requirement on c(d, g) from Theorem 1 and the inequality c(d, g) ≥ d^{g/4}, a short computation shows that we may certainly take c(δ) = 4^{4/δ} in Corollary 3. Recent results of Hoory [5] and of Lam [7] show that γ(m, n, k, k) satisfies the bounds given in Corollary 3, with c(δ) = 1. In the case k ∈ {2, 3, 5}, the existence of rank two geometries known as generalized polygons (see [6] for constructions) show that the constant c(δ) = 1 is best possible when m = n. The strength in Corollary 3 is that it shows that excluding cycles of length O(log k) has, to within an absolute constant factor, the same effect on the upper bounds as excluding all cycles of length at most 2k. On the other hand, our next result gives an indication that γ(m, n, k, k) and γ(m, n, 2, k) may differ substantially:

Theorem 4. For all integers m, n and k ≥ 3,

γ((k − 1)m, n, k, k) ≥ (k − 1) · γ(m, n, 2, k).

If we make the assumption that for each even positive integer k, γ(m, n, 2, k) is asymptotically c_{1}(mn)^{1/2+1/(2k)} + c_{2}(m + n) as m, n → ∞, for some constants c_{1}, c_{2}, then Theorem 4 gives

lim inf_{m,n→∞} \frac{γ(m, n, k, k)}{γ(m, n, 2, k)} ≥ \sqrt{k − 1}.

Similar observations may be made for odd values of k, namely

lim inf_{m,n→∞} \frac{γ(m, n, k, k)}{γ(m, n, 2, k)} ≥ (k − 1)^{1/2−1/(2k)}.

One can deduce from these observations and the constructions of generalized quadrangles and hexagons that

lim inf_{n→∞} \frac{γ(n, 2n, 3, 3)}{γ(n, 2n, 2, 3)} ≥ 2^{1/3}
lim inf_{n→∞} \frac{γ(n, 2n, 5, 5)}{γ(n, 2n, 2, 5)} ≥ 4^{1/5}

Bipartite graphs without 2k-cycles 3

The first inequality comes from [8] and the second inequality is implicit in the work of Lazebnik, Ustimenko and Woldar [6]. The next section is devoted to proving Theorem 1, and the construction for Theorem 4 is presented in Section 3.

2. Proof of Theorem 1

The main tool in our proof will be the first theorem in [9]. Although the next proposition is not the statement of this theorem, it is straightforward to verify, from the proof appearing in [9]:

Proposition 5. Let G be a bipartite graph of average degree at least 4d and girth 2g. Then G contains cycles of \frac{1}{2}c(2d, 2g) consecutive even lengths, the shortest of which has length at most twice the radius of G.

Proof of Theorem 1 We proceed by induction on m+n. Suppose, for a contradiction, that G is a bipartite graph without cycles of length at most 2g − 2 and containing no 2k-cycle, with parts A and B of sizes m and n, respectively, and with more edges than the corresponding upper bound in Theorem 1. By Proposition 5, and using the definition of d in the statement of Theorem 1, it is sufficient to show that G contains a subgraph of radius at most k and average degree at least d. Indeed, since G has even girth 2g, Proposition 5 would then imply that there is an integer r such that g ≤ r ≤ k and such that G contains the cycles C_{2r}, C_{2r+2}, …, C_{2r+2k−2g}. Since 2k ∈ [2r, 2r + 2k − 2g] whenever g ≤ r ≤ k, one of these cycles has length 2k, as required.

Case 1. k is odd. In this case, we may assume that the minimum degree in A is at least

d_{A} = d\frac{m^{\frac{1}{2} + \frac{1}{2k}}}{n^{\frac{1}{2} − \frac{1}{2k}}} + d.

Indeed, if there was a vertex v ∈ A with degree less than d_{A} then by deleting it we would arrive at an m × (n − 1) bipartite graph G′ with

e(G′) > e(G) − d_{A} ≥ 2dm^{\frac{1}{2} + \frac{1}{2k}} (n^{\frac{1}{2} + \frac{1}{2k}} − \frac{1}{2}n^{− \frac{1}{2} + \frac{1}{2k}} ) + 2d(m + n) − d
> 2d ([m(n − 1)]^{\frac{1}{2} + \frac{1}{2k}} + (m + n − 1)) ,

so that G′ contains a 2k-gon by the inductive hypothesis. Similarly, we may assume that the minimum degree in B is at least

d_{B} = d\frac{n^{\frac{1}{2} + \frac{1}{2k}}}{m^{\frac{1}{2} − \frac{1}{2k}}} + d.

Choose a vertex v ∈ A and let H_{r} be the subgraph of G induced by vertices at distance at most r from v. Let us show that H_{r} has average degree at least d for some r ≤ k. Suppose this cannot be done. Let D_{r} denote the set of vertices of H_{r} at distance exactly r from v. Then the average number of neighbors in D_{r−1} of a vertex in D_{r} is less than d. It follows that if D_{r} ⊂ A, then |D_{r−1}| (d_{B} − d) < d|D_{r}| and if D_{r} ⊂ B, then |D_{r−1}| (d_{A} − d) < d|D_{r}|. Therefore,

|D_{r}| > \{ \begin{matrix}(\frac{d_{A}}{d} − 1) |D_{r−1}| = \frac{m^{\frac{1}{2} + \frac{1}{2k}}}{n^{\frac{1}{2} − \frac{1}{2k}}} |D_{r−1}| & if r is odd. \\ (\frac{d_{B}}{d} − 1) |D_{r−1}| = \frac{n^{\frac{1}{2} + \frac{1}{2k}}}{m^{\frac{1}{2} − \frac{1}{2k}}} |D_{r−1}| & if r is even. \end{matrix}

Iterating these inequalities for r = 1, 2, …, k we get that since k is odd,

|D_{k}| > (\frac{m^{\frac{1}{2} + \frac{1}{2k}}}{n^{\frac{1}{2} − \frac{1}{2k}}} )^{⌈^{\frac{k}{2}}⌉} (\frac{n^{\frac{1}{2} + \frac{1}{2k}}}{m^{\frac{1}{2} − \frac{1}{2k}}} )^{⌊^{\frac{k}{2}}⌋} = m.

On the other hand, using the fact that k is odd once more, D_{k} ⊂ B, so that |D_{k}| ≤ m, which is a contradiction. The proof of the second part is complete.

Case 2. k is even The proof here is similar, so we only indicate the necessary changes to the argument. The inductive hypothesis implies that the minimum degree in A is at least:

d′_{A} = d\frac{m^{\frac{1}{2} + \frac{1}{k}}}{\sqrt{n}} + d,

and the minimum degree in B is at least:

d_{B} = d\frac{\sqrt{n}}{m^{\frac{1}{2} − \frac{1}{k}}} + d.

We now start with a vertex v ∈ B, and repeat the above argument. Since k is even, D_{k} ⊂ B, so that |D_{k}| ≤ m, but

|D_{k}| > (\frac{m^{\frac{1}{2} + \frac{1}{k}}}{\sqrt{n}} )^{\frac{k}{2}} (\frac{\sqrt{n}}{m^{\frac{1}{2} − \frac{1}{k}}} )^{\frac{k}{2}} = m,

so we once more arrive at a contradiction.

3. Proof of Theorem 4

Suppose we are given an m by n bipartite graph H, of girth at least 2k + 2. From H, we construct a (k − 1)m by n bipartite graph constaining no 2k-cycles, and with k − 1 times as many edges as H. Let A, B be the parts of H, let A_{1}, A_{2}, …, A_{k−1} be disjoint sets, and let ϕ : ⋃_{i=1}^{k−1} A_{i} → A be defined so that ϕ restricted to A_{i} is a bijection A_{i} ↔ A. Define a new graph G with parts ⋃_{i=1}^{k−1} A_{i} and B, with edge set

E = {ab : ϕ(a)b ∈ H}.

In words, we are taking (k − 1) identical edge-disjoint copies of H which share B as one of their parts. We now show that G has no 2k-cycles.

Bipartite graphs without 2k-cycles 5

Suppose, for a contradiction, that G contains a 2k-cycle C = (a_{1}, b_{1}, a_{2}, a_{2}, …, a_{k}, b_{k}, a_{1}) with b_{i} ∈ B for all i ∈ {1, 2, …, k}. Then

W = (ϕ(a_{1}), b_{1}, ϕ(a_{2}), b_{2}, …, ϕ(a_{k}), b_{k}, ϕ(a_{1}))

is a closed walk of length 2k in H. As H has girth at least 2k + 2, W takes place on a tree T ⊂ H with at most k edges. On the other hand, the tree contains the k vertices in V (C)∩B, and there are at least two vertices a, a′ ∈ V (C)∩A_{i} for some i ∈ {1, 2, …, k−1}, by the pigeonhole principle. Now ϕ(a) and ϕ(a′) are distinct, since ϕ restricted to A_{i} is a bijection. Therefore the tree has at least k + 2 vertices, a contradiction. Therefore the graph G is 2k-cycle-free.

References

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

[2] Erdős, P.; Faudree, R. J.; Rousseau, C. C.; Schelp, R. H. The number of cycle lengths in graphs of given minimum degree and girth. Paul Erdős memorial collection. Discrete Math. 200 (1999), no. 1-3, 55–60.

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

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

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

[6] Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J. Polarities and 2k-cycle-free graphs. 16th British Combinatorial Conference (London, 1997). Discrete Math. 197/198 (1999), 503– 513.

[7] Lam, T. Graphs without cycles of even length. Bull. Austral. Math. Soc. 63 (2001), no. 3, 435–440.

[8] Naor, A.; Verstraëte, J. A. On the Turán number for the hexagon. To appear in Adv. Math (2005).

[9] Verstraëte, J. A. Arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput 9 (2000) no 4. 369–373.