Sieving and expanders

Let V be an orbit in ${\mathbb{Z}}^n$ of a finitely generated subgroup Λ of ${\mathrm{GL}}_n(\mathbb{Z})$ whose Zariski closure $\mathrm{Zcl}(\Lambda )$ is suitably large (e.g. isomorphic to ${\mathrm{SL}}_2$). We develop a Brun combinatorial sieve for estimating the number of points on V for which a fixed set of integral polynomials take prime or almost prime values. A crucial role is played by the expansion property of the ‘congruence graphs’ that we associate with V. This expansion property is established when $\mathrm{Zcl}(\Lambda )={\mathrm{SL}}_2$. To cite this article: J. Bourgain et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Eigenvalues and expanders

Linear expanders have numerous applications to theoretical computer science. Here we show that a regular bipartite graph is an expanderif and only if the second largest eigenvalue of its adjacency matrix is well separated from the first. This result, which has an analytic analogue for Riemannian manifolds enables one to generate expanders randomly and check efficiently their expanding properties. It also supplies an efficient algorithm for approximating the expanding properties of a graph. The exact determination of these properties is known to be coNP-complete. The research was supported by the Weizmann Fellowship for Scientific Research and by Air Force Contract OSR 82-0326.     

New results on expanders

Based on purely analytical methods, we exhibit new families of expanders in ${\mathrm{SL}}_2(p)$ (p prime) and $\mathrm{SU}(2)$, contributing to conjectures of A. Lubotzky and P. Sarnak. To cite this article: J. Bourgain, A. Gamburd, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Random Cayley graphs and expanders

For every 1 > δ > 0 there exists a c = c(δ) > 0 such that for every group G of order n, and for a set S of c(δ) log n random elements in the group, the expected value of the second largest eigenvalue of the normalized adjacency matrix of the Cayley graph X(G, S) is at most (1 - δ). This implies that almost every such a graph is an ?(δ)-expander. For Abelian groups this is essentially tight, and explicit constructions can be given in some cases. © 1994 John Wiley & Sons, Inc.     

Random Schreier graphs and expanders

Journal of Algebraic Combinatorics - Let the group G act transitively on the finite set $$Omega $$ , and let $$S subseteq G$$ be closed under taking inverses. The Schreier graph $$Sch(G...     

Remarks on partitions into expanders

Aequationes mathematicae - In this note we give a short proof that graphs having no linearly small Følner sets can be partitioned into a union of expanders. We use this fact to prove a...     

Towards dimension expanders over finite fields

In this paper we study the problem of explicitly constructing a dimension expander raised by [3]: Let \mathbbFⁿ \mathbb{F}^n be the n dimensional linear space over the field \mathbbF\mathbb{F}. Find a small (ideally constant) set of linear transformations from \mathbbFⁿ \mathbb{F}^n to itself {A _i } _i∈I such that for every linear subspace V ⊂ \mathbbFⁿ \mathbb{F}^n of dimension dim(V)<n/2 we have

Universal lattices and unbounded rank expanders

We study the representations of non-commutative universal lattices and use them to compute lower bounds of the τ-constant for the commutative universal lattices G _d,k =SL _d (ℤ[x ₁,...,x _k ]), for d≥3 with respect to several generating sets. As an application we show that the Cayley graphs of the finite groups can be made expanders with a suitable choice of generators. This provides the first example of expander families of groups of Lie type, where the rank is not bounded and provides counter examples to two conjectures of A. Lubotzky and B. Weiss.     

Recursive construction for 3-regular expanders

We present an algorithm which inn ³ (logn)³ time constructs a 3-regular expander graph onn vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of lengths=clogn decreases (for some fixed absolute constantc). When we reach a local minimum in the number of cycles of lengths the graph is an expander.     

Ramanujan complexes and high dimensional expanders

Expander graphs in general, and Ramanujan graphs in particular, have been of great interest in the last four decades with many applications in computer science, combinatorics and even pure mathematics. In these notes we describe various efforts made in recent years to generalize these notions from graphs to higher dimensional simplicial complexes.     

Computation of best possible low degree expanders

We present an algorithm for computing a best possible bipartite cubic expander for a given number of vertices. Such graphs are needed in many applications and are also the basis for many results in theoretical computer science. Known construction methods for expander graphs yield expanders that have a fairly poor expansion compared to the best possible expansion. Our algorithm is based on a lemma which allows to calculate an upper bound for the expansion of cubic bipartite graphs.     

On embedding expanders into ℓ p spaces

In this note we show that the minimum distortion required to embed alln-point metric spaces into the Banach space ℓ _p is between (c ₁/p) logn and (c ₂/p) logn, wherec ₂>c ₁>0 are absolute constants and 1≤p<logn. The lower bound is obtained by a generalization of a method of Linial et al. [LLR95], by showing that constant-degree expanders (considered as metric spaces) cannot be embedded any better. Research supported by Czech Republic Grant GAČR 201/94/2167 and Charles University grants No. 351 and 361.     

Random Latin squares and 2-dimensional expanders

Expander graphs have been playing an important role in combinatorics and computer science over the last four decades. In recent years a theory of high dimensional expanders is emerging, but as of now all known examples of expanders (random and explicit) have unbounded degrees. The question of existence of bounded degree high dimensional expanders was raised by Gromov and by Dotterrer and Kahle. In this paper we present a new model, based on Latin squares, of 2-dimensional complexes of bounded edge degrees that are expanders with probability tending to 1.     

Entropy and reduced distance for Ricci expanders

Perelman has discovered two integral quantities, the shrinker entropy W and the (backward) reduced volume, that are monotone under the Ricci flow ∂_gij/∂t = − 2R_ij and constant on shrinking solitons. Tweaking some signs, we find similar formulae corresponding to the expanding case. The expanding entropy W₊ is monotone on any compact Ricci flow and constant precisely on expanders; as in Perelman, it follows from a differential inequality for a Harnack-like quantity for the conjugate heat equation, and leads to functionals μ₊ and v₊. The forward reduced volume θ₊ is monotone in general and constant exactly on expanders. A natural conjecture asserts that g(t)/t converges as t → ∞ to a negative Einstein manifold in some weak sense (in particular ignoring collapsing parts). If the limit is known a-priori to be smooth and compact, this statement follows easily from any monotone quantity that is constant on expanders; these include vol(g)/t^n/2 (Hamilton) and -λ (Perelman), as well as our new quantities. In general, we show that, if vol(g) grows like t^n/2(maximal volume growth) then W⁺, θ⁺ and -λ remain bounded (in their appropriate ways) for all time. We attempt a sharp formulation of the conjecture.     

CAT(0) spaces and expanders

We construct a CAT(0) space Y with Izeki–Nayatani invariant δ(Y) =?1. By a similar construction, we also prove that there exists a CAT(0) space which does not have Markov type p for every p?>?1.     

Selfsimilar expanders of the harmonic map flow

We study the existence, uniqueness, and stability of self-similar expanders of the harmonic map heat flow in equivariant settings. We show that there exist selfsimilar solutions to any admissible initial data and that their uniqueness and stability properties are essentially determined by the energy-minimising properties of the so-called equator maps.     

Cayley graph expanders and groups of finite width

We present new infinite families of expander graphs of vertex degree 4, which is the minimal possible degree for Cayley graph expanders. Our first family defines a tower of coverings (with covering indices equal to 2) and our second family is given as Cayley graphs of finite groups with very short presentations with only two generators and four relations. Both families are based on particular finite quotients of a group G of infinite upper triangular matrices over the ring .We present explicit vector space bases for the finite abelian quotients of the lower exponent-2 groups of G by upper triangular subgroups and prove a particular 3-periodicity of these quotients. We also conjecture that the group G has finite width 3 and finite average width 8/3.     

A concentration theorem of expanders on Hadamard manifolds

In this note, we prove a concentration theorem of expanders. As a simple corollary, one can prove that expanding sequences of graphs do not admit coarse embeddings into Hadamard manifolds with bounded sectional curvatures.