Properties of certain families of \(2k\)-cycle-free graphs (Q1322024)

Where, for a fixed family \(\mathcal F\) of graphs, and a sequence \({\mathcal H}= \{H_ i\}_{i\geq 1}\) of \({\mathcal F}\)-free graphs with \(\{v_ i= v(H_ i)\}_{i\geq 1}\) increasing, there exists a minimum \(r\) such that \(e(H_ i)= (\lambda+ o(1)) v_ i^ r\) as \(i\to \infty\), \(r= r({\mathcal H})\) is called the magnitude of \(\mathcal H\); where a maximum \(\lambda\) exists with this property, it is called the constant of \(\mathcal H\), and denoted by \(\lambda({\mathcal H})\). All sequences \(\mathcal H\) of extremal graphs (such that \(e(H_ i)=\text{ex}(v_ i,{\mathcal F})\)) have the same magnitude and constant (where these exist), denoted by \(r_{{\mathcal F}}\), \(\lambda_{{\mathcal F}}\) respectively. \(\mathcal H\) is magnitude extremal if, while it need not be extremal, \(r({\mathcal H})= r_{{\mathcal F}}\). In the present paper \({\mathcal F}= \{C_{2k}\}\). The authors begin with the observation that, wherever \(r_{\{C_{2k}\}}\) is known, there exists a magnitude extremal sequence of ``high'' girth bipartite graphs. ``In this note we show that while \(\{C_{2k}\}\)-magnitude extremality can be achieved with (sequences of) bipartite graphs of high girth, ordinary extremality cannot.'' ``Theorem. Let \(k\geq 3\), and let \(\mathcal G\) be a family of \(2k\)-cycle-free graphs with magnitude \(r> 1\) and constant \(\lambda> 0\), the members of which are bipartite graphs of girth at least \(2k+2\). Then, for any \(t\), \(2\leq t\leq k-1\), there exists a family \(\widetilde{{\mathcal G}_ t}\) of \(2k\)-cycle-free graphs with magnitude \(r\) and constant \(\widetilde\lambda \geq t(2/(t+1))^ r\lambda> \lambda\), all of whose members are bipartite and contain each of the cycles \(C_ 4,C_ 6,\dots,C_{2t}\), and none of the cycles \(C_{2t+ 2},\dots,C_{2k}\). Consequently, any family of \(\{C_{2k}\}\)-extremal graphs must consist (with finitely many exceptions) either of graphs that are non-bipartite or (of graphs that) have girth at most \(2k- 2\).'' ``Recently, the authors proved that \(\text{ex}(v,\{C_ 3,C_ 4,\dots, C_{2k+1}\})= \Omega(v^{1+\frac 2{3k-3+\varepsilon}})\), where \(\varepsilon= 0\) if \(k\) is odd and \(\varepsilon= 1\) is \(k\) is even. To our knowledge this is the best known asymptotic lower bound for all \(k\), \(k\geq 2\), \(k\neq 5\). (The result will appear elsewhere.)''.