$0/1$-Polytopes with Exponentially Small Edge Expansion

Technical Summary: 0/1-Polytopes with Exponentially Small Edge Expansion

Problem Statement
The paper addresses the Mihail–Vazirani conjecture, which posits that the graph (1-skeleton) of every 0/1-polytope has an edge expansion (Cheeger constant) of at least one. Edge expansion is a critical metric in polyhedral combinatorics and Markov chain Monte Carlo methods, as it governs the mixing times of random walks used for approximate sampling and counting. While the conjecture has been verified for numerous subclasses (e.g., matching polytopes, matroid base polytopes, and low-dimensional cases), it remained open in full generality. A weaker version of the conjecture suggested only an inverse-polynomial lower bound in the dimension, which would suffice for polynomial-time algorithmic applications.

Methodology and Construction
The author presents an explicit construction of a family of 0/1-polytopes, denoted $(P_n)_{n \ge 1}$, designed to exhibit exponentially small edge expansion as the dimension increases. The construction relies on the Cayley sum of two specific sets of Boolean points.

1. Base Components:
   • Let $C = \{0, 1\}^2$ (the vertices of a unit square) and $D = \{0, e_1, e_2\}$ (vertices of a standard 2-simplex).
   • Define $Q = \text{conv}(C)$ and $\Delta = \text{conv}(D)$.
2. Layer Construction:
   • Two sets of points in $\mathbb{R}^{4n}$ are defined: $X_n = C^n \times D^n$ and $Y_n = D^n \times C^n$.
   • The polytope $P_n$ is constructed as the Cayley sum $X_n * Y_n = \text{conv}((X_n \times \{0\}) \cup (Y_n \times \{1\}))$. This results in a polytope in $\mathbb{R}^{4n+1}$.
3. Structural Analysis:
   • Vertices: By Fact 3, the vertex set $V(P_n)$ is exactly the generating set $V_n = (X_n \times \{0\}) \cup (Y_n \times \{1\})$.
   • Edges: The edges are classified into two types:
     • Same-layer edges: Edges within the lower ($t=0$) or upper ($t=1$) layers. These correspond to edges in the Cartesian products $Q^n \times \Delta^n$ and $\Delta^n \times Q^n$.
     • Cross-layer edges: Edges connecting a vertex in the lower layer to one in the upper layer. These are characterized by a "compatibility relation" $R \subseteq C \times D$, where a pair $(c, d)$ is compatible if a single linear objective uniquely maximizes at $c$ over $C$ and at $d$ over $D$.
   • Invariant Decomposition: The author identifies an invariant for cross-layer edges based on the "active blocks" of a vertex. Specifically, for a vertex $u$, let $I(u)$ be the set of indices where the first $n$ blocks are non-zero, and $J(u)$ be the set of indices where the last $n$ blocks are non-zero. Cross-layer edges preserve these sets ($I(u)=I(v)$ and $J(u)=J(v)$).

Key Results and Proof Strategy
The core of the paper is the demonstration that the edge expansion $h(G(P_n))$ decays exponentially with $n$ (and consequently with the dimension $4n+1$).

1. The Cut: The author constructs a specific subset of vertices $S_n \subset V(P_n)$ defined by the condition $|I(u)| < |J(u)|$.
   • $S_n$ consists of vertices where the number of active blocks in the first group is strictly less than in the second group.
   • Due to the invariance of $I$ and $J$ under cross-layer edges, no cross-layer edges cross the cut $(S_n, V_n \setminus S_n)$. The boundary $\delta(S_n)$ consists entirely of same-layer edges.
2. Size of the Cut:
   • The size of the set $S_n$ is calculated by summing the counts of vertices with profiles $(k, \ell)$ where $k < \ell$. The total number of vertices is $2 \cdot 12^n$. The size of $S_n$ is shown to be $12^n - \sum_{r=0}^n A_{r,r}$, where $A_{r,r}$ represents the count of vertices with diagonal profiles ($k=\ell=r$).
   • It is proven that $|S_n| < |V_n|/2$, making it a valid set for the edge expansion definition.
3. Boundary Size:
   • The boundary edges must connect a vertex with a diagonal profile $(r, r)$ to a vertex with a non-diagonal profile.
   • The number of such edges is bounded by a sum involving $A_{r,r}$ and a factor related to the number of ways to activate/deactivate blocks.
4. Asymptotic Decay:
   • The ratio $h(G(P_n)) = \frac{|\delta(S_n)|}{|S_n|}$ is bounded by $\frac{4n \sum A_{r,r}}{12^n - \sum A_{r,r}}$.
   • Using the identity $\sum A_{r,r} \le (1+\sqrt{6})^{2n}$, the author defines $\beta = \frac{(1+\sqrt{6})^2}{12} \approx 0.96 < 1$.
   • The expansion is shown to be bounded by $O(n \beta^n)$, which decays exponentially.

Main Theorem
The paper proves Theorem 1: There exists a constant $c > 0$ and an infinite sequence of full-dimensional 0/1-polytopes $(P_n)$ with dimensions tending to infinity such that for all sufficiently large $n$:
$$h(G(P_n)) \le \exp(-c \cdot \dim(P_n))$$
Consequently, $h(G(P_n)) < 1$ for large $n$.

Significance and Claims

• Disproof of the Conjecture: The construction explicitly disproves the Mihail–Vazirani conjecture in its strongest form (expansion $\ge 1$) and its weaker form (inverse-polynomial lower bound).
• Scope: The result applies to full-dimensional 0/1-polytopes, distinguishing it from previous negative evidence involving half-integral polytopes (Cardinal and Pournin) or poor vertex expansion (Kwok et al.), which did not necessarily imply poor edge expansion for 0/1-polytopes.
• AI Attribution: The paper explicitly states that the construction and analysis were generated by GPT-5.6 Sol in a "one-shot" manner, with the author independently verifying and streamlining the proof.
• Limitations: The paper does not propose new algorithmic applications or future directions beyond the disproof of the conjecture. It focuses strictly on the existence of this counterexample family.

In summary, the paper provides a rigorous counterexample to a long-standing conjecture in polyhedral combinatorics, demonstrating that 0/1-polytopes can possess edge expansion that vanishes exponentially with dimension, thereby invalidating the assumption that such polytopes universally support rapid mixing random walks.