1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Oct 3, 2018 at 5:31

1 Answer 1

2
$\begingroup$

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

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

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.