The isoperimetric number of the incidence graph of PG(n,q)

MaRDI QIDQ1658768zbMATH OpenFDO

Authors Andrew Elvey Price, Muhammad Adib Surani, Sanming Zhou

Publication date 15 August 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.03293, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p20

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

incidence-free numberisoperimetric numberprojective planeprojective spacevertex-isoperimetric number

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Connectivity (05C40) General theory of linear incidence geometry and projective geometries (51A05)

Abstract: Let $Gamm{a}_{n,q}$ be the point-hyperplane incidence graph of the projective space $operatornamePG(n,q)$, where $nge2$ is an integer and $q$ a prime power. We determine the order of magnitude of $1-i_V(Gamm{a}_{n,q})$, where $i_V(Gamm{a}_{n,q})$ is the vertex-isoperimetric number of $Gamm{a}_{n,q}$. We also obtain the exact values of $i_V(Gamm{a}_{2,q})$ and the related incidence-free number of $Gamm{a}_{2,q}$ for $qle16$.

Review text

Summary: Let \(\Gamma_{n,q}\) be the point-hyperplane incidence graph of the projective space \(\operatorname{PG}(n,q)\), where \(n \geq 2\) is an integer and \(q\) a prime power. We determine the order of magnitude of \(1-i_V(\Gamma_{n,q})\), where \(i_V(\Gamma_{n,q})\) is the vertex-isoperimetric number of \(\Gamma_{n,q}\). We also obtain the exact values of \(i_V(\Gamma_{2,q})\) and the related incidence-free number of \(\Gamma_{2,q}\) for \(q \leq 16\).

Recommendations

• The vertex-isoperimetric number of the incidence and non-incidence graphs of unitals
• Expansion properties of Levi graphs.
• On resolving sets in the point-line incidence graph of \(\mathrm{PG}(n,q)\)
• scientific article; zbMATH DE number 841633
• Large incidence-free sets in geometries

Cites work

• An Isoperimetric Inequality on the Discrete Torus
• Classification of 2-arc-transitive dihedrants
• Expander graphs and their applications
• Expansion properties of Levi graphs.
• scientific article; zbMATH DE number 18980 (Why is no real title available?)
• scientific article; zbMATH DE number 3521984 (Why is no real title available?)
• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• scientific article; zbMATH DE number 1382769 (Why is no real title available?)
• scientific article; zbMATH DE number 841633 (Why is no real title available?)
• scientific article; zbMATH DE number 3074559 (Why is no real title available?)
• Large incidence-free sets in geometries
• Local Expansion of Symmetrical Graphs
• Nonincident points and blocks in designs
• On an isoperimetric problem for Hamming graphs
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• On the number of coprime integer pairs within a circle
• Optimal numberings and isoperimetric problems on graphs
• Some maximal arcs in finite projective planes
• The complete \((k, 3)\)-arcs of \(\mathrm{PG}(2,q), q\leq 13\)

Cited in

(5)

• The vertex-isoperimetric number of the incidence and non-incidence graphs of unitals
• On resolving sets in the point-line incidence graph of \(\mathrm{PG}(n,q)\)
• Incidence‐free sets and edge domination in incidence graphs
• Edge isoperimetric method: at least \(2 / 3\) of \(h\)-extra edge-connectivity of a kind of cube-based graphs concentrates on \(2^{n - 1}\)
• Lower bound for independence covering in C₄-free graphs

This page was built for publication: The isoperimetric number of the incidence graph of \(\operatorname{PG}(n,q)\)

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