# Lower bound construction for the extremal number of $C_{2k}$-free bipartite graph

Suppose $$G(V_1 \cup V_2, E)$$ is a bipartite graph with parts $$|V_1|=n$$ and $$|V_2|=m.$$ What is the best known lower bound construction for the maximum number of edges in $$G$$ when $$G$$ does not have a cycle of length $$8.$$

I'm looking for some references.

• If $N=m+n$ and there no restrictions on $m$ and $n$, the unique extremal graph for $N\le 63$ is $K_{3,N-3}$. Clearly this doesn't continue forever, but when does the first exception occur? Oct 3, 2018 at 5:31

It's a major open question to determine this value, even up to constant factors, even when $$n=m$$. In this special case, the best upper bound has the form $$|E| = O(n^{1 + 1/4})$$ (see this paper or many others), while the best lower bound has the form $$|E| = \Omega(n^{1 + 1/5})$$ (the only lower bound graph I'm aware of is the incidence graph of the Split Cayley Hexagon, but unfortunately I can't point you at a good reference for how to build this, and I don't know if there's a simpler construction out there. Maybe someone can help me out here).

For the general case when $$n < m$$, it should be easy to extend the results of the above upper bound paper to prove $$|E| = O(n^{3/4} m^{1/2} + m)$$ (I did some back-of-the-envelope computations here but I haven't totally verified this, so beware). The only interesting lower bound graph I'm aware of is the incidence graph of the twisted triality hexagon, which I believe requires $$m = n^{5/4}$$ and then gives $$|E| = \Omega(n^{11/8})$$.

• Thanks for your response. Could you please give a reference for the twisted triality hexagon?
– Kim
Oct 3, 2018 at 3:57
• I'd go for the book "Generalized Polygons" by Maldeghem, pp114-116, if you're comfortable with the algebra: books.google.com/…
– GMB
Oct 3, 2018 at 15:27
• Also see en.wikipedia.org/wiki/Generalized_polygon for a more intro description of why these generalized polygon constructions are relevant to your question.
– GMB
Oct 3, 2018 at 15:28