Point-line incidence conjecture for even-cycle-free graphs

Let k3k\geq 3 be an integer. Let PP be a set of nn points in the plane and let L\mathcal{L} be a set of nn lines in the plane. Define the incidence set and incidence graph by

I=I(P,L)={(p,)P×L:p},G=(PL,I).I=I(P,\mathcal{L})=\{(p,\ell)\in P\times\mathcal{L}:p\in\ell\},\qquad G=(P\cup\mathcal{L},I).

The incidence graph has vertex parts PP and L\mathcal{L}, and is C2kC_{2k}-free when it contains no cycle of length 2k2k.

Point-line incidence conjecture. If GG is C2kC_{2k}-free, then

I(P,L)=o(n1+1/k).|I(P,\mathcal{L})|=o\left(n^{1+1/k}\right).

This conjecture asks whether the geometric setting admits a bound strictly smaller than the general extremal-graph upper bound. The paper presents it as an open problem and develops lower-bound constructions for point-line arrangements with prescribed girth.

Sources & referencesView supporting material

Primary source

Mozhgan Mirzaei, Andrew Suk and Jacques Verstraëte, “Constructions of point-line arrangements in the plane with large girth”, arXiv:1911.11713 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.