# Cycles of length $8$

There is a construction of a bipartite graph $$G=(V_1 \cup V_2, E),$$ where $$|V_1|=|V_2|=n,$$ $$|E| \geq \Omega(n^{6/5}),$$ such that $$G$$ does not cotain any cycle of length $$8.$$

I was wondering if someone knows this construction or introduce me a reference for that?

• Is there some additional hypothesis (presumably related to cycles of length 8)? With no further hypothesis a bipartite graph on $n+n$ vertices can have as many as $n^2$ edges . . . – Noam D. Elkies May 12 at 3:57
• @NoamD.Elkies it got edited. – Ken May 12 at 4:16

## 2 Answers

Yes. These exist. See the following, which more than answers the question.

https://arxiv.org/pdf/math/9501231.pdf

Previous (some better/easier in your case) results also do this as well (regarding generalized hexagons). The well-known conjecture is that $$C_{2k}$$-free graphs exist with $$\approx n^{1+1/k}$$ edges. This would be best possible, but it’s still unknown for $$C_8$$-free graphs.

The incidence graphs of Generalized Hexagons provide a construction: Such a graph constructed fron the Lie group $$G_2(q)$$ ($$q$$ a prime power) has degree $$(q+1)$$ and $$2(q^6-1)/(q-1)$$ vertices, and is bipartite.

The problem better fits the cage problem framework: Such graphs correspond to girth $$10$$ or $$12$$. Cages of this girth would surely satisfy $$|E|≥Ω(n^{6/5})$$. Even if the cage is not known, there're methods to construct relatively small graphs for girth $$12$$ by removing a subgraph from a known cage. For girth $$10$$, there's no known general construction for $$|E|≥Ω(n^{5/4})$$.