Polarities and \(2k\)-cycle-free graphs
type: Item
instance of: scholarly article
title: Polarities and \(2k\)-cycle-free graphs
zbMATH Open document ID: 0924.05043
DOI: 10.1016/S0012-365X(99)90107-3
author: Andrew J. Woldar
author: Felix Lazebnik
author: V. A. Ustimenko
published in: Discrete Mathematics
publication date: 1999-11-03T00:00:00Z
review text: 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}\)-…
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05E20
zbMATH DE Number: 1322034
zbMATH Keywords: minimum chromatic number
zbMATH Keywords: cycles
zbMATH Keywords: polarities
zbMATH Keywords: asymptotic lower bound
reviewed by: William G. Brown
MaRDI profile type: MaRDI publication profile
cites work: Minimal Regular Graphs of Girths Eight and Twelve
cites work: Q3852212
cites work: Cycles of even length in graphs
cites work: Q4276276
cites work: On Graphs that do not Contain a Thomsen Graph
cites work: Q5662096
cites work: Graphs without four-cycles
cites work: The finite Moufang hexagons coordinatized
cites work: Q5520566
cites work: Compactness results in extremal graph theory
cites work: The nonexistence of certain generalized polygons
cites work: On a class of degenerate extremal graph problems
cites work: Graphs without quadrilaterals
cites work: Q3771125
cites work: New examples of graphs without small cycles and of large size
cites work: Explicit construction of graphs with an arbitrary large girth and of large size
cites work: Properties of certain families of \(2k\)-cycle-free graphs
cites work: A new series of dense graphs of high girth
cites work: A characterization of the components of the graphs \(D(k,q)\)
cites work: Q3138195
cites work: Embeddings of small generalized polygons
cites work: Sur la trialité et certains groupes qui s'en déduisent
cites work: Q5685299
cites work: Q3312262
cites work: Q3980738
cites work: On the varieties of parabolic subgroups, their generalizations and combinatorial applications
cites work: Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
full work available at URL: s0012-365x(99)90107-3
OpenAlex ID: W4210755957
Recommended article: Properties of certain families of \(2k\)-cycle-free graphs
Recommended article: A note on graphs without short even cycles
Recommended article: Adjacency matrices of polarity graphs and of other \(C_{4}\)-free graphs of large size
Recommended article: Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle
description: scientific article; zbMATH DE number 1322034