Constructions of point-line arrangements in the plane with large girth

arXiv1911.11713MaRDI QIDQ6329918FDOQ6329918

Authors: Mozhgan Mirzaei, Andrew Suk, J. Verstraëte 

Publication date: 26 November 2019

Abstract: A classical result by ErdH{o}s, and later on by Bondy and Simonivits, states that every $n$-vertex graph with no cycle of length $2k$ has at most $O(n^{1+1/k})$ edges. This bound is known to be tight when $kin2,3,5,$ but it is a major open problem in extremal graph theory to decide if this bound is tight for all $k$. In this paper, we study the effect of forbidding short even cycles in incidence graphs of point-line arrangements in the plane. It is not known if the ErdH{o}s upper bound stated above can be improved to $o(n^{1+1/k})$ in this geometric setting, and in this note, we establish non-trivial lower bounds for this problem by modifying known constructions arising in finite geometries. In particular, by modifying a construction due to Labeznik and Ustimenko, we construct an arrangement of $n$ points and $n$ lines in the plane, such that their incidence graph has girth at least $k+5$, and determines at least $Omega(n^{1+frac4k^2+6k-3})$ incidences. We also apply the same technique to Wenger graphs, which gives a better lower bound for $k=5.$

This page was built for publication: Constructions of point-line arrangements in the plane with large girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6329918)