Random Latin squares and 2-dimensional expanders

Abstract

Let X be a 2-dimensional simplicial complex. The degree of an edge e is the number of 2-faces of X containing e. The complex X is an ε-expander if the coboundary d_1(ϕ) of every Z_2-valued 1-cochain ϕ\in C^1(X;Z_2) satisfies |support(d_1(ϕ))| \geq ε|\supp(ϕ+d_0(ψ))| for some 0-cochain ψ. Using a new model of random 2-complexes we show the existence of an infinite family of 2-dimensional ε-expanders with maximum edge degree d, for some fixed ε>0 and d.

20 pages