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.

Improve this question
$\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$
    – Brendan McKay
    Commented Oct 3, 2018 at 5:31

1 Answer 1

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your response. Could you please give a reference for the twisted triality hexagon? $\endgroup$
    – Kim
    Commented 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
    Commented 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
    Commented Oct 3, 2018 at 15:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .