OctoInformBeta

Bounded-degree coboundary expanders

Let XX be a finite pure dd-dimensional simplicial complex. An ii-cochain ff on XX is an 𝔽2\mathbb F_2-valued function on its ii-faces. Its normalized weighted norm ∥f∥i\|f\|_i is the probability that ff is nonzero on an ii-face sampled by first choosing a uniform dd-face and then a uniform ii-face within it. The coboundary δif\delta_i f assigns to each (i+1)(i+1)-face the sum of ff over its ii-faces. Write Bi(X)=im⁡δi−1B^i(X)=\operatorname{im}\delta_{i-1} for the actual coboundaries when i>0i>0. In degree zero, B0(X)B^0(X) is the space of constant functions. The distance to coboundaries is dist⁡i(f,Bi(X))=min⁡b∈Bi(X)∥f−b∥i\operatorname{dist}_i(f,B^i(X))=\min_{b\in B^i(X)}\|f-b\|_i. A coboundary expansion bound with constant ε>0\varepsilon>0 is the inequality ∥δif∥i+1≥εdist⁡i(f,Bi(X))\|\delta_i f\|_{i+1}\ge\varepsilon\operatorname{dist}_i(f,B^i(X)) for every ii-cochain ff. The cocycles are the cochains ff with δif=0\delta_i f=0. The question is whether arbitrarily large complexes can satisfy this bound in every degree 0≤i<d0\le i<d with one positive constant while the number of dd-faces containing each vertex remains uniformly bounded.

Evra and Kaufman obtained bounded-degree complexes in every dimension with a uniform lower bound on the coboundary norm in terms of distance to cocycles. Chapman and Lubotzky proved the existence of bounded-degree two-dimensional coboundary expanders over 𝔽2\mathbb F_2.

For every d≥3d\ge3, the preprint proves the existence of finite connected pure dd-dimensional complexes XmX_m with vertex counts tending to infinity, uniformly bounded numbers of dd-faces at each vertex, and one positive coboundary expansion constant for all mm and all 0≤i<d0\le i<d. Together with the graph and two-dimensional cases, the preprint’s theorem gives bounded-degree 𝔽2\mathbb F_2 coboundary expanders in every positive dimension.

The Lean library is the reference because Lean has checked every result of the Lean library under its stated hypotheses. Each page states the Lean library’s result and links to the declaration behind it. Where the preprint states a result differently, its statement is given beside the Lean library’s statement. The preprint serves only as a guide to the order and names of the results. The Lean library assumes that a certain infinite complex has vanishing reduced homology. The Lean library also assumes a comparison between the homology of certain finite complexes and the group homology of certain subgroups. The Lean library’s conditional expansion theorem assumes a homological vanishing statement that the preprint deduces from Morrow’s pro Tor-unitality theorem and Iwasa’s homology pro-stability theorem. The Lean library’s conditional expansion theorem also assumes the uniform inequality against cocycles supplied by Oppenheim and Valentiner-Branth.

The Lean library: Coboundary

Coboundary is a Lean library: 15 items, in five groups. Each has a page written by OctoInform, listed below.