Polarities and \(2k\)-cycle-free graphs
For nontrivial families \({\mathcal F}\) of undirected simple graphs, it is known that \(\text{ex}(v,{\mathcal F})=\frac{\chi-2}{2(\chi-1)}v^2+o(v^2)\) as \(v\to\infty\) where \(\chi\) is the minimum chromatic number for members of \({\mathcal F}\) [see \textit{P.\ Erdős} and \textit{M. Simonovits}, A limit theorem in graph theory, Stud. Sci. Math. Hung. 1, 51-57 (1966; Zbl 0178.27301)]. When \({\mathcal F}\) is ``degenerate'', i.e. when \(\chi=2\), one seeks more informative asymptotic information. From the authors' introduction and their abstract: `` \(\dots\) we discuss another method \dots{} to sometimes improve numerical constants in lower bounds for \(\text{ex}(v,C_{2k})\dots\). Our method is motivated by, and is a generalization of, an idea from [\textit{W. G. Brown}, On graphs that do not contain a Thomsen graph, Can. Math. Bull. 9, 281-285 (1966; Zbl 0178.27302 and Zbl 0553.05044); \textit{P. Erdős, A. Rényi} and \textit{V. T. Sós}, On a problem of graph theory, Stud. Sci. Math. Hung. 1, 215-235 (1966; Zbl 0144.23302)] of using a polarity of the projective plane \(\text{PG} (2,q)\) to show that \(\text{ex}(v,C_4)=\frac 12v^{\frac 32}+o(v^{\frac 32})\).'' \(\dots\) ``It is applied to refute some conjectures about the values of \(\text{ex}(v,C_{2k})\), and to construct some new examples of graphs having certain restrictions on the lengths of their cycles. In particular, we construct an infinite family \(\{G_i\}\) of \(C_6\)-free graphs with \(| E(G_i)| \sim | V(G_i)| ^{\frac 43}\), \(i\to\infty\), which improves the constant in the previous best lower bound on \(\text{ex}(v,C_6)\) from \(\frac 2{3^{\frac 43}}\approx 0.462\) to \(\frac 12\).'' \(\dots\) ``Though the polarities enable us to improve the constants in the asymptotic lower bound for \(\text{ex}(v,C_{2k})\) when \(k=4\) and \(k\geq 7\), these improvements are only marginally interesting since (i) better constants are provided by the method of [the authors, Properties of certain families of \({2k}\)-cycle free graphs, J. Comb. Theory, Ser. B 60, No. 2, 293-298 (1994; Zbl 0803.05028)], and (ii) it is not known whether these graphs are magnitude extremal for \(k=4\) and \(k\geq 7\)''.
scientific article; zbMATH DE number 1322034