Properties of certain families of \(2k\)-cycle-free graphs (Q1322024): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Felix Lazebnik / rank | |||
Property / author | |||
Property / author: Q917018 / rank | |||
Property / author | |||
Property / author: Andrew J. Woldar / rank | |||
Property / reviewed by | |||
Property / reviewed by: William G. Brown / rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56698341 / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Felix Lazebnik / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Vasiliy A. Ustimenko / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Andrew J. Woldar / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: William G. Brown / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1994.1020 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2093219044 / rank | |||
Normal rank |
Latest revision as of 01:34, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Properties of certain families of \(2k\)-cycle-free graphs |
scientific article |
Statements
Properties of certain families of \(2k\)-cycle-free graphs (English)
0 references
2 January 1995
0 references
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.)''.
0 references
cycle-free graphs
0 references
extremal graphs
0 references
magnitude
0 references
constant
0 references
extremal sequence
0 references
bipartite graphs
0 references
girth
0 references
lower bound
0 references