On regular induced subgraphs of generalized polygons

DOI10.1016/J.JCTA.2018.03.015zbMATH Open1391.05066arXiv1708.01095OpenAlexW2743155091WikidataQ130074747 ScholiaQ130074747MaRDI QIDQ721048FDOQ721048

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)

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$.

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

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

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)

Cites Work

• Interlacing eigenvalues and graphs
• The nonexistence of certain generalized polygons
• Title not available (Why is that?)
• Expander graphs and their applications
• Finite generalized quadrangles
• On Moore Graphs with Diameters 2 and 3
• Sur la trialité et certains groupes qui s'en déduisent
• On (minimal) regular graphs of girth \(6\)
• New upper bounds on the order of cages
• On geometric constructions of \((k,g)\)-graphs
• Title not available (Why is that?)
• General Galois Geometries
• Dynamic cage survey
• Title not available (Why is that?)
• 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
• On Hamiltonian Regular Graphs of Girth Six
• Title not available (Why is that?)
• Regular graphs constructed from the classical generalized quadrangle Q(4, q)
• Substructures in finite classical polar spaces
• Title not available (Why is that?)
• On upper bounds and connectivity of cages
• Large incidence-free sets in geometries
• Connectivity of cages
• Finite geometry and combinatorial applications

Cited In (8)

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

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)