Coboundary expansion of random balanced Cayley complexes
Fix an integer $k \ge 2$. For a finite group $G$ let $$D(G) = \sum_{\rho \in \widehat G} \dim \rho,$$ the sum of the degrees of its irreducible complex representations, and let $V_i = \{i\} \times G$ for $1 \le i \le k + 1$. For $A \subseteq G$ the balanced Cayley complex $Y_{A,k}$ is the subcomplex of the join $V_1 * \cdots * V_{k+1}$ that contains its full $(k-1)$-skeleton and whose $k$-simplices are exactly the sets $\{(1, g_1), \ldots, (k+1, g_{k+1})\}$ with $g_1 g_2 \cdots g_{k+1} \in A$. Take cochains over $\mathbb{F}_2$, with coboundary $\delta$, let $|\phi|$ be the number of faces on which $\phi$ is nonzero, and put $B^{k-1}(Y) = \operatorname{im} \delta_{k-2}$. The coboundary expansion constant is $$h_{k-1}(Y) = \min_{\phi \notin B^{k-1}(Y)} \frac{|\delta \phi|}{\min_{b \in B^{k-1}(Y)} |\phi + b|},$$ with unnormalized counts. Meshulam proved a real-coefficient counterpart: for fixed $k$ and $\varepsilon > 0$, if $|G| = n > 10^6 (k/\varepsilon)^8$ and $A$ is a uniformly random subset of $G$ of size $m = \lceil 9k^2 \log D(G) / \varepsilon^2 \rceil$, then the $(k-1)$-th spectral gap of $Y_{A,k}$, the smallest eigenvalue of its reduced $(k-1)$-th Laplacian on real cochains, is less than $(1 - \varepsilon) m$ with probability less than $6/n$.
Problem. Do there exist constants $C_k, \varepsilon_k > 0$ such that, for a uniformly random subset $A \subseteq G$ of size $\lceil C_k \log D(G) \rceil$, $$\Pr\{h_{k-1}(Y_{A,k}) \ge \varepsilon_k\} \longrightarrow 1 \quad \text{as } |G| \to \infty,$$ the constants working along every sequence of finite groups whose orders tend to infinity?
Source: Meshulam (2024), Conjecture 8.1, for every k ≥ 1. Stated by AIM — Open Applied Problems for k ≥ 2, with sample size ⌈C_k log D(G)⌉.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- AT, GR
- Keywords
- AIM Open Applied Problems, Cayley complexes, coboundary expansion, random simplicial complexes
References
@article{meshulam2024,
author = {Meshulam, Roy},
title = {Random balanced {C}ayley complexes},
journal = {J. Appl. Comput. Topol.},
volume = {8},
number = {6},
year = {2024},
pages = {1701--1721},
doi = {10.1007/s41468-023-00137-6},
eprint = {2211.02085},
archivePrefix = {arXiv},
}
@misc{aim-random-balanced-cayley-expansion,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Coboundary expansion of random balanced Cayley complexes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/640-random-balanced-cayley-expansion.md},
note = {Entry 640 at commit 24edaad, 2026-10-15},
}
Resolution claims
The proposed coboundary expansion of random balanced Cayley complexes with binary coefficients and logarithmically many group-product layers fails in every fixed dimension $k\ge2$. For $G=(\F)^d$ and every $A\subseteq G$, we prove \[ _{}H^{k-1}(Y_{A,k};) _{j=0}^{(k,d)} dj-|A|. \] The proof maps a Boolean polynomial vanishing on $A$ to a cohomology class by writing the polynomial of a total group sum as a …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Needs verification → Solution claimed | — | Recorded here: AIM @ 24edaad, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00826, "Coboundary expansion of random balanced Cayley complexes", clopen.solutions.