The Isoperimetric Number of the Incidence Graph of $PG(n,q)$

  • Andrew Elvey Price
  • Muhammad Adib Surani
  • Sanming Zhou
Keywords: Isoperimetric number, Vertex-isoperimetric number, Incidence-free number, Projective plane, Projective space


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