Search

This paper, and its companion [BCV24], are devoted to a negative resolution of the Aldous--Lyons Conjecture [AL07, Ald07]. This conjecture, originated in probability theory, is well known (cf. [Gel18]) to be equivalent to the statement that every invariant random subgroup of the free group is co-sofic. We disprove this last statement. In this part we introduce subgroup tests. These tests are finite distributions over continuous functions from the space of subgroups of the free group to $\{0,1\}$. Subgroup tests provide a general framework in which one can study invariant random subgroups of the free group. Classical notions such as group soficity and group stability arise naturally in this framework. By the correspondence between subgroups of the free group and Schreier graphs, one can view subgroup tests as a property testing model for certain edge-labeled graphs. This correspondence also provides the connection to random networks. Subgroup tests have values, which are their asymptotic optimal expectations when integrated against co-sofic invariant random subgroups. Our first main result is that, if every invariant random subgroup of the free group is co-sofic, then one can approximate the value of a subgroup test up to any positive additive constant. Our second main result is an essentially value preserving correspondence between certain non-local games and subgroup tests. By composing this correspondence with a stronger variant of the reduction in MIP*=RE [JNV+21], proved in the companion paper [BCV24], we deduce that approximating the sofic value of a subgroup test is as hard as the Halting Problem, and in particular, undecidable. The combination of our two main results proves the existence of non co-sofic invariant random subgroups of the free group., Comment: 54 pages

We prove two results on some special generators of finite simple groups and use them to prove that every non-abelian finite simple group $S$ admits a non-congruence presentation (as conjectured in [CLT24]), and that if $S$ has a non-trivial Schur multiplier, then it admits a smooth cover (as conjectured in [CFLZ])., Comment: 29 pages

Property testing has been a major area of research in computer science in the last three decades. By property testing we refer to an ensemble of problems, results and algorithms which enable to deduce global information about some data by only reading small random parts of it. In recent years, this theory found its way into group theory, mainly via group stability. In this paper, we study the following problem: Devise a randomized algorithm that given a subgroup $H$ of $G$, decides whether $H$ is the whole group or a proper subgroup, by checking whether a single (random) element of $G$ is in $H$. The search for such an algorithm boils down to the following purely group theoretic problem: For $G$ of rank $k$, find a small as possible test subset $A\subseteq G$ such that for every proper subgroup $H$, $|H\cap A|\leq (1-\delta)|A|$ for some absolute constant $\delta>0$, which we call the detection probability of $A$. It turns out that the search for sets $A$ of size linear in $k$ and constant detection probability is a non-commutative analogue of the classical search for families of good error correcting codes. This paper is devoted to proving that such test subsets exist, which implies good universal error correcting codes exist -- providing a far reaching generalization of the classical result of Shannon. In addition, we study this problem in certain subclasses of groups -- such as abelian, nilpotent, and finite solvable groups -- providing different constructions of test subsets for these subclasses with various qualities. Finally, this generalized theory of non-commutative error correcting codes suggests a plethora of interesting problems and research directions., Comment: 26 pages, 1 figure, 1 table

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work. Derandomized direct product testing, also known as agreement testing, is the following problem. Let X be a family of k-element subsets of [n] and let $\{f_s:s\to\Sigma\}_{s\in X}$ be an ensemble of local functions, each defined over a subset $s\subset [n]$. Suppose that we run the following so-called agreement test: choose a random pair of sets $s_1,s_2\in X$ that intersect on $\sqrt k$ elements, and accept if $f_{s_1},f_{s_2}$ agree on the elements in $s_1\cap s_2$. We denote the success probability of this test by $Agr(\{f_s\})$. Given that $Agr(\{f_s\})=\epsilon>0$, is there a global function $G:[n]\to\Sigma$ such that $f_s = G|_s$ for a non-negligible fraction of $s\in X$ ? We construct a family X of k-subsets of $[n]$ such that $|X| = O(n)$ and such that it satisfies the low acceptance agreement theorem. Namely, $Agr (\{f_s\}) > \epsilon \; \; \longrightarrow$ there is a function $G:[n]\to\Sigma$ such that $\Pr_s[f_s\overset{0.99}{\approx} G|_s]\geq poly(\epsilon)$. A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family X is just the k-faces of the new symplectic HDXs. The later serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. We also give a polynomial-time algorithm to construct this family of symplectic HDXs., Comment: arXiv admin note: text overlap with arXiv:2312.15325

We revisit the paper of Alexander Grothendiek where he introduced Grothendieck pairs and discuss the relation between profinite rigidity and left/right Grothendieck rigidity. We also show that various groups are left and/or right Grothendieck rigid and, in particular, all ascending HNN extensiona of finitely generated free groups are right Grothendieck rigid. Along the way we present a number of questions and suggestions for further research., Comment: 16 pages

Coboundary expansion (with $\mathbb{F}_2$ coefficients), and variations on it, have been the focus of intensive research in the last two decades. It was used to study random complexes, property testing, and above all Gromov's topological overlapping property. In part I of this paper, we extended the notion of coboundary expansion (and its variations) to cochains with permutation coefficients, equipped with the normalized Hamming distance. We showed that this gives a unified language for studying covering stability of complexes, as well as stability of group homomorphisms -- a topic that drew a lot of attention in recent years. In this part, we extend the theory to the permutation coefficients setting. This gives some new results, even for $\mathbb{F}_2$ coefficients, opens several new directions of research, and suggests a pattern to proving the existence of non-sofic groups. Along the way, we solve the dimension $2$ case of a problem of Gromov, exhibiting a family of bounded degree coboundary expanders with $\mathbb{F}_2$ coefficients., Comment: 32 pages, Section 4.5 was added in version 2

This paper is motivated by recent developments in group stability, high dimensional expansion, local testability of error correcting codes and topological property testing. In Part I, we formulate and motivate three stability problems: 1. Homomorphism stability: Are almost homomorphisms close to homomorphisms? 2. Covering stability: Are almost coverings of a cell complex close to genuine coverings of it? 3. Cocycle stability: Are 1-cochains whose coboundary is small close to 1-cocycles? We then prove that these three problems are equivalent., Comment: 32 pages

Using cohomological methods, we show that lattices in semisimple groups are typically stable with respect to the Frobenius norm but not with respect to the operator norm., Comment: incorporated remarks and corrections of the reviewers

It is, by now, classical that lattices in higher rank semisimple groups have various rigidity properties. In this work, we add another such rigidity property to the list: uniform stability with respect to the family of unitary operators on finite-dimensional Hilbert spaces equipped with submultiplicative norms. Namely, we show that for (most) high-rank lattices, every finite-dimensional unitary "almost-representation" of $\Gamma$ is a small deformation of a (true) unitary representation. This extends a result of Kazhdan (1983) for amenable groups and of Burger-Ozawa-Thom (2013) for SL(n,Z) (for n>2). Towards this goal, we first build an elaborate cohomological theory capturing the obstruction to such stability, and show that the vanishing of second cohomology implies uniform stability in this setting. This cohomology can be roughly thought of as an asymptotic version of bounded cohomology, and sheds light on a question raised in Monod (2006) about a possible connection between vanishing of second bounded cohomology and Ulam stability., Comment: 71 pages, 3 figures, Added clarifications in Section 4.2, Corrected typos

We exhibit infinitely many pairs of non-isomorphic finitely presented, residually finite groups $\Delta$ and $\Gamma$ with $\Delta$ having Property FA, $\Gamma$ having a non-trivial action on a tree and $\Delta$ and $\Gamma$ having isomorphic profinite completions., Comment: 5 pages

An explicit construction of locally testable codes of constant rate, constant distance and constant number of queries is given. Hence answering affirmatively the $c^3$-problem., Comment: This is a revision of arxiv.org/2111.04808 that has been adapted to a mathematical audience

This paper is a journal counterpart to our FOCS 2021 paper, in which we initiate the study of property testing problems concerning a finite system of relations $E$ between permutations, generalizing the study of stability in permutations. To every such system $E$, a group $\Gamma=\Gamma_E$ is associated and the testability of $E$ depends only on $\Gamma$ (just like in Galois theory, where the solvability of a polynomial is determined by the solvability of the associated group). This leads to the notion of testable groups, and, more generally, Benjamini-Schramm rigid groups. The paper presents an ensemble of tools to check if a given group $\Gamma$ is testable/BS-rigid or not., Comment: 22 pages

By a classical result of Neukirch and Uchida, a number field K is determined by the structure of its absolute Galois group Gal(K). We show that K is not determined by the structure of the Sylow subgroups of Gal(K), answering a question raised by Florian Pop.

A locally testable code (LTC) is an error-correcting code that has a property-tester. The tester reads $q$ bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter $q$ is called the locality of the tester. LTCs were initially studied as important components of PCPs, and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code. An outstanding open question has been whether there exist "$c^3$-LTCs", namely LTCs with *c*onstant rate, *c*onstant distance, and *c*onstant locality. In this work we construct such codes based on a new two-dimensional complex which we call a left-right Cayley complex. This is essentially a graph which, in addition to vertices and edges, also has squares. Our codes can be viewed as a two-dimensional version of (the one-dimensional) expander codes, where the codewords are functions on the squares rather than on the edges., Comment: This new version corrects and polishes a few minor points, but more importantly, adds references to other related very recent works which were done independently

$ $Abert, Gelander and Nikolov [AGN17] conjectured that the number of generators $d(\Gamma)$ of a lattice $\Gamma$ in a high rank simple Lie group $H$ grows sub-linearly with $v = \mu(H / \Gamma)$, the co-volume of $\Gamma$ in $H$. We prove this for non-uniform lattices in a very strong form, showing that for $2-$generic such $H$'s, $d(\Gamma) = O_H(\log v / \log \log v)$, which is essentially optimal. While we can not prove a new upper bound for uniform lattices, we will show that for such lattices one can not expect to achieve a better bound than $d(\Gamma) = O(\log v)$.

We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple $(\sigma_1,\dotsc,\sigma_d)$ of permutations on $\{1,\dotsc,n\}$, and one wishes to determine whether this tuple satisfies a certain system of relations $E$, or is far from every tuple that satisfies $E$. If this computational problem can be solved by querying only a small number of entries of the given permutations, we say that $E$ is testable. For example, when $d=2$ and $E$ consists of the single relation $\mathsf{XY=YX}$, this corresponds to testing whether $\sigma_1\sigma_2=\sigma_2\sigma_1$, where $\sigma_1\sigma_2$ and $\sigma_2\sigma_1$ denote composition of permutations. We define a collection of graphs, naturally associated with the system $E$, that encodes all the information relevant to the testability of $E$. We then prove two theorems that provide criteria for testability and non-testability in terms of expansion properties of these graphs. By virtue of a deep connection with group theory, both theorems are applicable to wide classes of systems of relations. In addition, we formulate the well-studied group-theoretic notion of stability in permutations as a special case of the testability notion above, interpret all previous works on stability as testability results, survey previous results on stability from a computational perspective, and describe many directions for future research on stability and testability., Comment: 42 pages; this version was accepted to FOCS 2021

A graph $X$ is defined inductively to be $(a_0,\dots,a_{n-1})$-regular if $X$ is $a_0$-regular and for every vertex $v$ of $X$, the sphere of radius $1$ around $v$ is an $(a_1,\dots,a_{n-1})$-regular graph. Such a graph $X$ is said to be highly regular (HR) of level $n$ if $a_{n-1}\neq 0$. Chapman, Linial and Peled studied HR-graphs of level 2 and provided several methods to construct families of graphs which are expanders "globally and locally". They ask whether such HR-graphs of level 3 exist. In this paper we show how the theory of Coxeter groups, and abstract regular polytopes and their generalisations, can lead to such graphs. Given a Coxeter system $(W,S)$ and a subset $M$ of $S$, we construct highly regular quotients of the 1-skeleton of the associated Wythoffian polytope $\mathcal{P}_{W,M}$, which form an infinite family of expander graphs when $(W,S)$ is indefinite and $\mathcal{P}_{W,M}$ has finite vertex links. The regularity of the graphs in this family can be deduced from the Coxeter diagram of $(W,S)$. The expansion stems from applying superapproximation to the congruence subgroups of the linear group $W$. This machinery gives a rich collection of families of HR-graphs, with various interesting properties, and in particular answers affirmatively the question asked by Chapman, Linial and Peled., Comment: 22 pages, 2 tables. Dedicated to the memory of John Conway and Ernest Vinberg

The congruence subgroup problem for a finitely generated group $\Gamma$ and $G\leq Aut(\Gamma)$ asks whether the map $\hat{G}\to Aut(\hat{\Gamma})$ is injective, or more generally, what is its kernel $C\left(G,\Gamma\right)$? Here $\hat{X}$ denotes the profinite completion of $X$. In the case $G=Aut(\Gamma)$ we denote $C\left(\Gamma\right)=C\left(Aut(\Gamma),\Gamma\right)$. Let $\Gamma$ be a finitely generated group, $\bar{\Gamma}=\Gamma/[\Gamma,\Gamma]$, and $\Gamma^{*}=\bar{\Gamma}/tor(\bar{\Gamma})\cong\mathbb{Z}^{(d)}$. Denote $Aut^{*}(\Gamma)=\textrm{Im}(Aut(\Gamma)\to Aut(\Gamma^{*}))\leq GL_{d}(\mathbb{Z})$. In this paper we show that when $\Gamma$ is nilpotent, there is a canonical isomorphism $C\left(\Gamma\right)\simeq C(Aut^{*}(\Gamma),\Gamma^{*})$. In other words, $C\left(\Gamma\right)$ is completely determined by the solution to the classical congruence subgroup problem for the arithmetic group $Aut^{*}(\Gamma)$. In particular, in the case where $\Gamma=\Psi_{n,c}$ is a finitely generated free nilpotent group of class $c$ on $n$ elements, we get that $C(\Psi_{n,c})=C(\mathbb{Z}^{(n)})=\{e\}$ whenever $n\geq3$, and $C(\Psi_{2,c})=C(\mathbb{Z}^{(2)})=\hat{F}_{\omega}$ = the free profinite group on countable number of generators., Comment: 18 pages

By work of Belyi, the absolute Galois group $G_{\mathbb{Q}}=\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$ of the field $\mathbb{Q}$ of rational numbers can be embedded into $A=\mathrm{Aut}(\widehat{F_2})$, the automorphism group of the free profinite group $\widehat{F_2}$ on two generators. The image of $G_{\mathbb{Q}}$ lies inside $\widehat{GT}$, the Grothendieck-Teichm\"uller group. While it is known that every abelian representation of $G_{\mathbb{Q}}$ can be extended to $\widehat{GT}$, Lochak and Schneps put forward the challenge of constructing irreducible non-abelian representations of $\widehat{GT}$. We do this virtually, namely by showing that a rich class of arithmetically defined representations of $G_{\mathbb{Q}}$ can be extended to finite index subgroups of $\widehat{GT}$. This is achieved, in fact, by extending these representations all the way to finite index subgroups of $A=\mathrm{Aut}(\widehat{F_2})$. We do this by developing a profinite version of the work of Grunewald and Lubotzky, which provided a rich collection of representations for the discrete group $\mathrm{Aut}(F_d)$., Comment: 19 pages; some typos were fixed

In a 1937 paper B.H. Neumann constructed an uncountable family of $2$-generated groups. We prove that all of his groups are permutation stable by analyzing the structure of their invariant random subgroups.

We prove that all invariant random subgroups of the lamplighter group $L$ are co-sofic. It follows that $L$ is permutation stable, providing an example of an infinitely presented such a group. Our proof applies more generally to all permutational wreath products of finitely generated abelian groups. We rely on the pointwise ergodic theorem for amenable groups., Comment: 32 pages; small corrections

Ramanujan graphs are graphs whose spectrum is bounded optimally. Such graphs have found numerous applications in combinatorics and computer science. In recent years, a high dimensional theory has emerged. In this paper these developments are surveyed. After explaining their connection to the Ramanujan conjecture we will present some old and new results with an emphasis on random walks on these discrete objects and on the Euclidean spheres. The latter lead to "golden gates" which are of importance in quantum computation., Comment: To appear in the proceedings of the Ramanujan Centenary Celebration at the Royal Society

This paper describes in basic terms what a "Thin Group" is, as well as its uses in various subjects., Comment: 6 pages, 2 pictures

We show that for a fixed k, Gromov random groups with any positive density have no non-trivial degree-k representations over any field, a.a.s. This is especially interesting in light of the results of Agol, Ollivier and Wise that when the density is less than 1/6 such groups have a faithful linear representation over the rationals, a.a.s., Comment: 10 pages

In recent years, there has been a considerable amount of interest in the stability of a finitely-generated group $\Gamma$ with respect to a sequence of groups $\left\{G_{n}\right\}_{n=1}^{\infty}$, equipped with bi-invariant metrics $\left\{d_{n}\right\}_{n=1}^{\infty}$. We consider the case $G_{n}=\operatorname{U}\left(n\right)$ (resp. $G_{n}=\operatorname{Sym}\left(n\right)$), equipped with the normalized Hilbert-Schmidt metric $d_{n}^{\operatorname{HS}}$ (resp. the normalized Hamming metric $d_{n}^{\operatorname{Hamming}}$). Our main result is that if $\Gamma$ is infinite, hyperlinear (resp. sofic) and has Property $\operatorname{(T)}$, then it is not stable with respect to $\left(\operatorname{U}\left(n\right),d_{n}^{\operatorname{HS}}\right)$ (resp. $\left(\operatorname{Sym}\left(n\right),d_{n}^{\operatorname{Hamming}}\right)$). This answers a question of Hadwin and Shulman regarding the stability of $\operatorname{SL}_{3}\left(\mathbb{Z}\right)$. We also deduce that the mapping class group $\operatorname{MCG}\left(g\right)$, $g\geq 3$, and $\operatorname{Aut}\left(\mathbb{F}_n\right)$, $n\geq 3$, are not stable with respect to $\left(\operatorname{Sym}\left(n\right),d_{n}^{\operatorname{Hamming}}\right)$. Our main result exhibits a difference between stability with respect to the normalized Hilbert-Schmidt metric on $\operatorname{U}\left(n\right)$ and the (unnormalized) $p$-Schatten metrics, since many groups with Property $\operatorname{(T)}$ are stable with respect to the latter metrics, as shown by De Chiffre-Glebsky-Lubotzky-Thom and Lubotzky-Oppenheim. We suggest a more flexible notion of stability that may repair this deficiency of stability with respect to $\left(\operatorname{U}\left(n\right),d_{n}^{\operatorname{HS}}\right)$ and $\left(\operatorname{Sym}\left(n\right),d_{n}^{\operatorname{Hamming}}\right)$., Comment: 20 pages; v2 includes new results in Section 3 and an appendix

It was shown in a previous work of the first named author with De Chiffre, Glebsky and Thom that there exists a finitely presented group which cannot be approximated by almost-homomorphisms to the unitary groups $U(n)$ equipped with the Frobenius norms (a.k.a as $L^2$ norm, or the Schatten-2-norm). In his ICM18 lecture, Andreas Thom asks if this result can be extended to general Schatten-p-norms. We show that this is indeed the case for $1

Two short seminal papers of Margulis used Kazhdan's property $(T)$ to give, on the one hand, explicit constructions of expander graphs, and to prove, on the other hand, the uniqueness of some invariant means on compact simple Lie groups. These papers opened a rich line of research on expansion and spectral gap phenomena in finite and compact simple groups. In this paper we survey the history of this area and point out a number of problems which are still open., Comment: survey paper, 22 pages

Consider $\operatorname{Sym}(n)$, endowed with the normalized Hamming metric $d_n$. A finitely-generated group $\Gamma$ is \emph{P-stable} if every almost homomorphism $\rho_{n_k}\colon \Gamma\rightarrow\operatorname{Sym}(n_k)$ (i.e., for every $g,h\in\Gamma$, $\lim_{k\rightarrow\infty}d_{n_k}( \rho_{n_k}(gh),\rho_{n_k}(g)\rho_{n_k}(h))=0$) is close to an actual homomorphism $\varphi_{n_k} \colon\Gamma\rightarrow\operatorname{Sym}(n_k)$. Glebsky and Rivera observed that finite groups are P-stable, while Arzhantseva and P\u{a}unescu showed the same for abelian groups and raised many questions, especially about P-stability of amenable groups. We develop P-stability in general, and in particular for amenable groups. Our main tool is the theory of invariant random subgroups (IRS), which enables us to give a characterization of P-stability among amenable groups, and to deduce stability and instability of various families of amenable groups., Comment: 24 pages; v2 includes minor updates and new references

Expander graphs have been, during the last five decades, the subject of a most fruitful interaction between pure mathematics and computer science, with influence and applications going both ways (cf. [Lub94], [HLW06], [Lub12] and the references therein). In the last decade, a theory of "high dimensional expanders" has begun to emerge. The goal of the current paper is to describe some paths of this new area of study., Comment: Paper to be presented as a Plenary talk at ICM 2018

This is an item on Ramanujan Graphs for a planned encyclopedia on Ramanujan. The notion of Ramanujan graphs is explained, as well as the reason to name these graphs after Ramanujan.

This paper answers a question raised by Grothendieck in 1970 on the "Grothendieck closure" of an integral linear group and proves a conjecture of the first author made in 1980. This is done by a detailed study of the congruence topology of arithmetic groups, obtaining along the way, an arithmetic analogue of a classical result of Chevalley for complex algebraic groups. As an application we also deduce a group theoretic characterization of thin subgroups of arithmetic groups., Comment: 24 pages

If $\Gamma$ is an irreducible non-uniform higher-rank characteristic zero arithmetic lattice (for example, $SL_n(\mathbb{Z})$, $n \geq 3$) and $\Lambda$ is a finitely generated group that is elementarily equivalent to $\Gamma$, then $\Lambda$ is isomorphic to $\Gamma$., Comment: Preliminary version. Comments are welcome

A long standing problem in the area of error correcting codes asks whether there exist good cyclic codes. Most of the known results point in the direction of a negative answer. The uncertainty principle is a classical result of harmonic analysis asserting that given a non-zero function $f$ on some abelian group, either $f$ or its Fourier transform $\hat{f}$ has large support. In this note, we observe a connection between these two subjects. We point out that even a weak version of the uncertainty principle for fields of positive characteristic would imply that good cyclic codes do exist. We also provide some heuristic arguments supporting that this is indeed the case., Comment: 20 pages

Answering a question asked by Agol and Wise, we show that a desired stronger form of Wise's malnormal special quotient theorem does not hold. The counterexamples are generalizations of triangle groups, built using the Ramanujan graphs constructed by Lubotzky--Phillips--Sarnak., Comment: 12 pages, 2 figures. V2 incorporates changes suggested by the referee. This is the final version accepted for publication

The congruence subgroup problem for a finitely generated group $\Gamma$ asks whether $\widehat{Aut\left(\Gamma\right)}\to Aut(\hat{\Gamma})$ is injective, or more generally, what is its kernel $C\left(\Gamma\right)$? Here $\hat{X}$ denotes the profinite completion of $X$. In this paper we first give two new short proofs of two known results (for $\Gamma=F_{2}$ and $\Phi_{2}$) and a new result for $\Gamma=\Phi_{3}$: 1. $C\left(F_{2}\right)=\left\{ e\right\}$ when $F_{2}$ is the free group on two generators. 2. $C\left(\Phi_{2}\right)=\hat{F}_{\omega}$ when $\Phi_{n}$ is the free metabelian group on $n$ generators, and $\hat{F}_{\omega}$ is the free profinite group on $\aleph_{0}$ generators. 3. $C\left(\Phi_{3}\right)$ contains $\hat{F}_{\omega}$. Results 2. and 3. should be contrasted with an upcoming result of the first author showing that $C\left(\Phi_{n}\right)$ is abelian for $n\geq4$., Comment: 20 pages

The theory of $k$-regular graphs is closely related to group theory. Every $k$-regular, bipartite graph is a Schreier graph with respect to some group $G$, a set of generators $S$ (depending only on $k$) and a subgroup $H$. The goal of this paper is to begin to develop such a framework for $k$-regular simplicial complexes of general dimension $d$. Our approach does not directly generalize the concept of a Schreier graph, but still presents an extensive family of $k$-regular simplicial complexes as quotients of one universal object: the $k$-regular $d$-dimensional arboreal complex, which is itself a simplicial complex originating in one specific group depending only on $d$ and $k$. Along the way we answer a question from [PR12] on the spectral gap of higher dimensional Laplacians and prove a high dimensional analogue of Leighton's graph covering theorem. This approach also suggests a random model for $k$-regular $d$-dimensional multicomplexes., Comment: 40 pages, 7 figures

Let $M$ be a locally symmetric irreducible closed manifold of dimension $\ge 3$. A result of Borel [Bo] combined with Mostow rigidity imply that there exists a finite group $G = G(M)$ such that any finite subgroup of $\text{Homeo}^+(M)$ is isomorphic to a subgroup of $G$. Borel [Bo] asked if there exist $M$'s with $G(M)$ trivial and if the number of conjugacy classes of finite subgroups of $\text{Homeo}^+(M)$ is finite. We answer both questions: (1) For every finite group $G$ there exist $M$'s with $G(M) = G$, and (2) the number of maximal subgroups of $\text{Homeo}^+(M)$ can be either one, countably many or continuum and we determine (at least for $\dim M \neq 4$) when each case occurs. Our detailed analysis of (2) also gives a complete characterization of the topological local rigidity and topological strong rigidity (for dim$M\neq 4$) of proper discontinuous actions of uniform lattices in semisimple Lie groups on the associated symmetric spaces.

We introduce a new model of random $d$-dimensional simplicial complexes, for $d\geq 2$, whose $(d-1)$-cells have bounded degrees. We show that with high probability, complexes sampled according to this model are coboundary expanders. The construction relies on Keevash's recent result on designs [Ke14], and the proof of the expansion uses techniques developed by Evra and Kaufman in [EK15]. This gives a full solution to a question raised in [DK12], which was solved in the two-dimensional case by Lubotzky and Meshulam [LM13]., Comment: 14 pages

We go back and forth between, on the one hand, presentations of arithmetic and Kac-Moody groups and, on the other hand, presentations of profinite groups, deducing along the way new results on both.

Expander graphs have been intensively studied in the last four decades. In recent years a high dimensional theory of expanders has emerged, and several variants have been studied. Among them stand out coboundary expansion and topological expansion. It is known that for every $d$ there are unbounded degree simplicial complexes of dimension $d$ with these properties. However, a major open problem, formulated by Gromov, is whether bounded degree high dimensional expanders exist for $d \geq 2$. We present an explicit construction of bounded degree complexes of dimension $d=2$ which are topological expanders, thus answering Gromov's question in the affirmative. Conditional on a conjecture of Serre on the congruence subgroup property, infinite sub-family of these give also a family of bounded degree coboundary expanders. The main technical tools are new isoperimetric inequalities for Ramanujan Complexes. We prove linear size bounds on $F_2$ systolic invariants of these complexes, which seem to be the first linear $F_2$ systolic bounds. The expansion results are deduced from these isoperimetric inequalities.