The isoperimetric number of the incidence graph of \(\operatorname{PG}(n,q)\)

Andrew Elvey Price¹ ; Muhammad Adib Surani¹ ; Sanming Zhou¹

¹The University of Melbourne

The electronic journal of combinatorics, Tome 25 (2018) no. 3

Résumé

Let $\Gamma_{n,q}$ be the point-hyperplane incidence graph of the projective space $\operatorname{PG}(n,q)$, where $n \ge 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 \le 16$.

Détail

DOI : 10.37236/6980

Classification : 05C40, 05B25, 51A05
Mots-clés : isoperimetric number, vertex-isoperimetric number, incidence-free number, projective plane, projective space