4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 . . . $\endgroup$ – Noam D. Elkies May 12 at 3:57
  • 1
    $\begingroup$ @NoamD.Elkies it got edited. $\endgroup$ – Ken May 12 at 4:16
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.