On regular induced subgraphs of generalized polygons

DOI10.1016/J.JCTA.2018.03.015MaRDI QIDQ721048zbMATH OpenOpenAlexWikidataFDO

Authors John Bamberg, Anurag Bishnoi, Gordon Royle

Publication date 18 July 2018

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.01095

zbMATH Keywords

expander mixing lemmageneralized polygonMoore graphcage\(t\)-good structure

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Combinatorial structures in finite projective spaces (51E20) Blocking sets, ovals, (k)-arcs (51E21) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Abstract: The cage problem asks for the smallest number $c(k,g)$ of vertices in a $k$-regular graph of girth $g$ and graphs meeting this bound are known as cages. While cages are known to exist for all integers $kge2$ and $gge3$, the exact value of $c(k,g)$ is known only for some small values of $k,g$ and three infinite families where $gin6,8,12$ and $k-1$ is a prime power. These infinite families come from the incidence graphs of generalized polygons. Some of the best known upper bounds on $c(k,g)$ for $gin6,8,12$ have been obtained by constructing small regular induced subgraphs of these cages. In this paper, we first use the Expander Mixing Lemma to give a general lower bound on the size of an induced $k$-regular subgraph of a regular bipartite graph in terms of the second largest eigenvalue of the host graph. We use this bound to show that the known construction of $(k,6)$-graphs using Baer subplanes of the Desarguesian projective plane is the best possible. For generalized quadrangles and hexagons, our bounds are new. In particular, we improve the known lower bound on the size of a $q$-regular induced subgraphs of the classical generalized quadrangle $mathsfQ(4,q)$ and show that the known constructions are asymptotically sharp. For prime powers $q$, we also improve the known upper bounds on $c(q,8)$ and $c(q,12)$ by giving new geometric constructions of $q$-regular induced subgraphs in the symplectic generalized quadrangle $mathsfW(3,q)$ and the split Cayley hexagon $mathsfH(q)$, respectively. Our constructions show that [c(q,8) le 2(q^3 - qsqrt{q} - q)] for $q$ an even power of a prime, and [c(q, 12) le 2(q^5 - 3q^3)] for all prime powers $q$. For $qin3,4,5$ we also give a computer classification of all $q$-regular induced subgraphs of the classical generalized quadrangles of order $q$.

Recommendations

• On upper bounds of odd girth cages
• Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages
• New upper bounds on the order of cages
• On generalized cages
• scientific article; zbMATH DE number 3885947

Cites work

• scientific article; zbMATH DE number 3668627 (Why is no real title available?)
• scientific article; zbMATH DE number 1219619 (Why is no real title available?)
• scientific article; zbMATH DE number 3432305 (Why is no real title available?)
• scientific article; zbMATH DE number 3412694 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• A characterization of the natural embedding of the split Cayley hexagon in \(\mathrm{PG}(6,q)\) by intersection numbers in finite projective spaces of arbitrary dimension
• Connectivity of cages
• Dynamic cage survey
• Expander graphs and their applications
• Finite generalized quadrangles
• Finite geometry and combinatorial applications
• General Galois Geometries
• Interlacing eigenvalues and graphs
• Large incidence-free sets in geometries
• New upper bounds on the order of cages
• On (minimal) regular graphs of girth \(6\)
• On Hamiltonian Regular Graphs of Girth Six
• On Moore Graphs with Diameters 2 and 3
• On geometric constructions of \((k,g)\)-graphs
• On upper bounds and connectivity of cages
• Regular graphs constructed from the classical generalized quadrangle Q(4, q)
• Substructures in finite classical polar spaces
• Sur la trialité et certains groupes qui s'en déduisent
• The nonexistence of certain generalized polygons

Cited in

(8)

• On the automorphisms of a family of small q-regular graphs of girth 8
• Edge-girth-regular graphs arising from biaffine planes and Suzuki groups
• Some induced subgraphs of strongly regular graphs with no triangles
• On a relation between bipartite biregular cages, block designs and generalized polygons
• The Zarankiewicz problem, cages, and geometries
• New values for the bipartite Ramsey number of the four-cycle versus stars
• Bipartite biregular Moore graphs
• Induced 2-regular subgraphs in \(k\)-chordal cubic graphs

Describes a project that uses

Uses Software

• MINION

This page was built for publication: On regular induced subgraphs of generalized polygons

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