Definitions.
For a finite simple graph $G=(V, E)$, the Cheeger constant for $G$ is defined as
$$
h(G) = \inf_{S} \frac{e(S, S^c)}{\min\{|S|, |S^c|\}}
$$
where $S$ runs over all non-empty proper subsets of $V$, $e(S, S^c)$ is the number of edges with one end-point in $S$ and the other end-point in $S^c$.
The Cheeger constant is a measure of connectivity of the graph.
The higher the Cheeger constant, the more connected the graph is.
A $d$-regular expander family is a sequence $G_1, G_2, G_3, \ldots$ of finite simple $d$-regular graphs such that:
$\bullet$ $|V(G_n)|\to \infty$ as $n\to \infty$, and
$\bullet$there exists a positive constant $c$ such that $h(G_n)>c$ for all $n$.
(It is intuitively repugnant that such a family exists, since the graphs become sparser and sparser, but still remain highly connected.)
Question.
It is a theorem (Marcus, Spielman, and Srivastava) that for any $d$, there is a $d$-regular expander family $G_1, G_2, G_3, …$ such that $h(G_n)\geq (d-2\sqrt{d-1})/2$ for all $n$.
Question. Is there some $d$ (or preferably a family of $d$'s) for which it is known that there is a $d$-regular expander family $G_1, G_2, G_3, \ldots$ such that $h(G_n)>d/2$?
Best Answer
No no such family exists. This is a rough sketch of the proof: Let $G$ be an arbitrary $d$-regular graph. Each $v \in G$ flips a fair coin independently of the other vertices, heads it is in $S$ then tails it is in $\bar{S}$.
Then on the one hand, with probability $1-\frac{1}{n}$ both $|S|$ and $\bar{S}$ have at least $\frac{n-\log n\sqrt{n}}{2}$ vertices each.
Then on the other hand, the expected fraction of edges $e$ with one endpoint of $e$ in $S$ and the other in $\bar{S}$ is only $\frac{1}{2}$. So as the least it can be is 0, [you can show that] with probability at least $\frac{1}{\log n}$ the number of edges $E$ with one endpoint in $S$ and the other in $\bar{S}$ is only $\frac{1}{2}+\frac{1}{\log n}$.
Thus the above randomized algorithm returns with positive probability e.g., at least $\frac{1}{\log n}-\frac{1}{n}$ a set $S$ s.t. $S,\bar{S}$ s.t. $\frac{e(S,\bar{S}}{\min\{|S|,|\bar{S}|\}} \le \frac{d}{2}+o(1)$. So at least the lim inf of the Cheeger constant of an infinite family of $d$-regular graphs cannot be greater than $\frac{d}{2}$.
OR this would be another way to prove the answer is no: Partition $V(G)$ into two sets $S$ and $T$ of equal cardinality (exactly equal to within one vertex). If more than $\frac{d|S|}{2} + d^2$ edges of $G$ have one endpoint in $S$ and the other in $T$ then there are two nonadjacent vertices $u \in S$ and $v \in T$; $u$ and $v$ not adjacent in $G$, s.t. more than $d/2$ neighbours of $u$ are in $T$ and more than $d/2$ neighbours of $v$ are in $S$. So take $u$ out of $S$ and put $u$ into $T$ and take $v$ out of $T$ nd put $v$ into $S$.Then the resulting sets $S'$ and $T'$ still partition $V(G)$ and have equal cardinality, but $e(S,T') < e(S,T)$ [strict inequality].