A Note on the Asymptotic Value of the Isoperimetric Number of $J(n,2)$

Abstract

Let $G$ be a graph on $n$ vertices and $S$ a subset of vertices of $G$; the boundary of $S$ is the set, $\partial S$, of edges of $G$ connecting $S$ to its complement in $G$. The isoperimetric number of $G$, is the minimum of $\left|\partial S\right|/\left|S\right|$ overall $S\subset V(G)$ of at most $n/2$ vertices. Let $k\le n$ be positive integers. The Johnson graph is the graph, $J(n,k)$, whose vertices are all the subsets of size $k$ of $\{1,\dots ,n\}$, two of which are adjacent if their intersection has cardinality equal to $k-1$. In this paper we show that the asymptotic value of the isoperimetric number of the Johnson graph $J(n,2)$ is equal to $(2-\sqrt{2})n$.