Erdős Problem 1080
Statement and result.
There are bipartite graphs of arbitrarily large order $n$, with one part of size exactly $\lfloor n^{2/3}\rfloor$, which have no $6$-cycle and have $e(G)/n\to\infty$. In fact the construction below gives $e(G)\gg n^{16/15}$. This disproves the proposed linear edge bound.
A finite Hermitian incidence geometry.
Let $q$ tend to infinity through odd primes and let $F=\mathbb F_{q^2}$. On $F^4$ use the nondegenerate Hermitian form \[
h(x,y)=\sum_{i=1}^4 x_i y_i^q.
\] The points $\mathcal P$ are the one-dimensional $F$-subspaces spanned by nonzero vectors $x$ with $h(x,x)=0$. The lines $\mathcal L$ are the two-dimensional totally isotropic subspaces: $h$ vanishes on every pair of their vectors. Join a point to a line when it is contained in that line. We use the standard finite-field facts that $F$ exists, its multiplicative group is cyclic, and the norm $z\mapsto z^{q+1}$ maps onto $\mathbb F_q^\times$, with exactly $q+1$ preimages of each nonzero value.
Counting points and lines.
Let $N_d$ count vectors in $F^d$ whose coordinate norms sum to zero, including the zero vector. Considering the first $d-1$ coordinates, the final norm equation has one solution if its right side is zero and $q+1$ otherwise. Hence \[
N_1=1,\qquad
N_d=(q+1)q^{2d-2}-qN_{d-1}.
\] In particular \[
N_2=q^3+q^2-q,\qquad
N_4=q^7+(q-1)q^3.
\] Every point has $q^2-1$ nonzero representatives, so \[
v:=|\mathcal P|=\frac{N_4-1}{q^2-1}
=(q^3+1)(q^2+1).
\tag{1}
\] Each line contains $q^2+1$ points. If $P$ is a point, the quotient $P^\perp/P$ is a nondegenerate Hermitian space of dimension two. Its isotropic one-spaces correspond exactly to the lines through $P$, and their number is \[
\frac{N_2-1}{q^2-1}=q+1.
\tag{2}
\] For completeness, a nondegenerate Hermitian form over $F$ has an orthogonal basis with all diagonal entries equal to one: first choose a vector of nonzero norm, rescale by norm-surjectivity, and continue on its orthogonal complement. Such a vector exists because if every $h(x,x)$ vanished, substituting $x+y$ and $x+\lambda y$ for $\lambda\notin\mathbb F_q$ would force every $h(x,y)$ to vanish. This justifies applying the $N_2$ count to the quotient. Double-counting incidences now gives \[
|\mathcal L|=\frac{v(q+1)}{q^2+1}
=(q^3+1)(q+1).
\tag{3}
\]
Why a $6$-cycle is impossible.
Suppose distinct points $P_1,P_2,P_3$ and distinct lines formed a $6$-cycle. Every pair of these points lies on one of its lines, so their vector representatives are pairwise orthogonal and individually isotropic. If the three representatives were linearly independent, their span $U$ would be a three-dimensional totally isotropic subspace. But $U\subseteq U^\perp$ in a nondegenerate four-dimensional space implies $2\dim U\leq4$, a contradiction. If the representatives are dependent, they span a two-dimensional subspace, and all three lines must equal that span: two distinct one-spaces determine their two-dimensional span uniquely. This again contradicts the cycle. Thus the incidence graph is $C_6$-free.
Choosing the smaller part and the exact order.
Set \[
M=\left\lceil2v^{2/3}\right\rceil,\qquad
n=\left\lceil M^{3/2}\right\rceil.
\] As $q\to\infty$, we have $v\asymp q^5$, $M\asymp q^{10/3}$, and $|\mathcal L|\asymp q^4$, so $M\leq|\mathcal L|$ for all sufficiently large $q$. Select any $M$ lines and retain all $v$ points and their incidences with those lines. Since \[
\frac{n}{v}\longrightarrow2^{3/2},\qquad
\frac{M}{v}\longrightarrow0,
\] we also have $n-M\geq v$ eventually. Add $n-M-v$ isolated vertices to the point part. The resulting graph has total order $n$. For every positive integer $M$, the interval $[M^{3/2},(M+1)^{3/2})$ has length greater than one. Therefore \[
M^{3/2}\leq n<(M+1)^{3/2},
\qquad \lfloor n^{2/3}\rfloor=M.
\] The selected-line part has exactly the required size. Each selected line still has all its $q^2+1$ neighbours, so \[
e(G)=M(q^2+1)\asymp q^{16/3}
\asymp n^{16/15},\qquad
\frac{e(G)}n\asymp q^{1/3}\longrightarrow\infty.
\] Deleting lines and adding isolated vertices cannot introduce a cycle. This completes the disproof.
Attribution and assessment.
The geometry used is the classical Hermitian generalized quadrangle, and the argument explains the finite-field counts and the absence of $6$-cycles directly. The exponent $16/15$ is recorded for this problem in the work of Lazebnik--Ustimenko--Woldar; no novelty is claimed for this reconstruction. Apart from the explicitly stated standard finite-field facts, the counting and graph argument are proved above. Source statement and bibliographic record checked 24 September 2026:
https://www.erdosproblems.com/1080. No local formal verification is claimed.
Completion estimate.
COMPLETION: 100%