Search

Whether Borel amenability implies hyperfiniteness is a main open question in the theory of Borel equivalence relations. Under a mild extra uniformity condition, we prove that Borel amenability of bounded degree Borel graphs is equivalent to a randomized version of hyperfiniteness. Our new approach yields simple proofs and generalizations for the Ornstein-Weiss theorem, the Quasi-Tiling theorem and the Connes-Feldman-Weiss theorem. One result is that the main conjecture holds up to a compressible set (that is, a set that admits no invariant probability measure)., Comment: A small error in Definition 1.1 is corrected

A countable, bounded degree graph is almost finite if it has a tiling with isomorphic copies of finitely many F\o lner sets, and we call it strongly almost finite, if the tiling can be randomized so that the probability that a vertex is on the boundary of a tile is uniformly small. We give various equivalents for strong almost finiteness. In particular, we prove that Property A together with the F\o lner property is equivalent to strong almost finiteness. Using these characterizations, we show that graphs of subexponential growth and Schreier graphs of amenable groups are always strongly almost finite, generalizing the celebrated result of Downarowicz, Huczek and Zhang about amenable Cayley graphs, based on graph theoretic rather than group theoretic principles. We give various equivalents to Property A for graphs, and show that if a sequence of graphs of Property A (in a uniform sense) converges to a graph $G$ in the neighborhood distance (a purely combinatorial analogue of the classical Benjamini-Schramm distance), then their Laplacian spectra converge to the Laplacian spectrum of $G$ in the Hausdorff distance. We apply the previous theory to construct a new and rich class of classifiable $C^{\star}$-algebras. Namely, we show that for any minimal strong almost finite graph $G$ there are naturally associated simple, nuclear, stably finite $C^{\star}$-algebras that are classifiable by their Elliott invariants., Comment: A line is added to the Introduction about a preprint

Almost forty years ago, Connes, Feldman and Weiss proved that for measurable equivalence relations the notions of amenability and hyperfiniteness coincide. In this paper we define the uniform version of amenability and hyperfiniteness for measurable graphed equivalence relations of bounded vertex degrees and prove that these two notions coincide as well. Roughly speaking, a measured graph $\cG$ is uniformly hyperfinite if for any $\eps>0$ there exists $K\geq 1$ such that not only $\cG$, but all of its subgraphs of positive measure are $(\eps,K)$-hyperfinite. We also show that this condition is equivalent to weighted hyperfiniteness and a strong version of fractional hyperfiniteness, a notion recently introduced by Lov\'asz. As a corollary, we obtain a characterization of exactness of finitely generated groups via uniform hyperfiniteness., Comment: 21 pages

Approximate proof labeling schemes were introduced by \\Censor-Hillel, Paz and Perry \cite{CPP}. Roughly speaking, a graph property~$\cP$ can be verified by an approximate proof labeling scheme in constant-time if the vertices of a graph having the property can be convinced, in a short period of time not depending on the size of the graph, that they are having the property $\cP$ or at least they are not far from being having the property $\cP$. The main result of this paper is that bounded-degree planar graphs (and also outer-planar graphs, bounded genus graphs, knotlessly embeddable graphs etc.) can be verified by an approximate proof labeling scheme in constant-time., Comment: 18 pages, the title has changed, to appear in Journal of Combinatorial Theory A

Motivated by the work of Lov\'asz and Szegedy on the convergence and limits of dense graph sequences, we investigate the convergence and limits of finite trees with respect to sampling in normalized distance. Based on separable real trees, we introduce the notion of a dendron and show that the limits of finite trees are exactly the dendrons. We also prove that the limit dendron is unique., Comment: 27 pages, no figures

In this short note we answer a query of Brodzki, Niblo, \v{S}pakula, Willett and Wright by showing that all bounded degree uniformly locally amenable graphs have Property A. For the second result of the note recall that Kaiser proved that if $\Gamma$ is a finitely generated group and $\{H_i\}^\infty_{i=1}$ is a Farber sequence of finite index subgroups, then the associated Schreier graph sequence is of Property A if and only if the group is amenable. We show however, that there exist a non-amenable group and a nested sequence of finite index subgroups $\{H_i\}^\infty_{i=1}$ such that $\cap H=\{e_\Gamma\}$, and the associated Schreier graph sequence is of Property A., Comment: to appear in the Proceedings of the American Mathematical Society

Recently, Goldreich introduced the notion of property testing of bounded-degree graphs with an unknown distribution. We propose a slight modification of his idea: the Radon-Nikodym Oracles. Using these oracles any reasonable graph property can be tested in constant-time against any reasonable unknown distribution in the category of planar graphs. We also discuss Randomized Local Distributed Algorithms, which work on very large graphs with unknown distributions. Finally, we discuss how can we learn graph properties using observations instead of samplings., Comment: Change in the title. The property testing process is explained in details, some short sections are added, the exposition is made more reader friendly. 22 pages

The goal of the paper is to lay the foundation for the qualitative analogue of the classical, quantitative sparse graph limit theory. In the first part of the paper we introduce the qualitative analogues of the Benjamini-Schramm and local-global graph limit theories for sparse graphs. The natural limit objects are continuous actions of finitely generated groups on totally disconnected compact metric spaces. We prove that the space of weak equivalent classes of free Cantor actions is compact and contains a smallest element, as in the measurable case. We will introduce and study various notions of almost finiteness, the qualitative analogue of hyperfiniteness, for classes of bounded degree graphs. We prove the almost finiteness of a new class of \'etale groupoids associated to Cantor actions and construct an example of a nonamenable, almost finite totally disconnected \'etale groupoid, answering a query of Suzuki. Motivated by the notions and results on qualitative graph limits, in the second part of our paper we give a precise definition of constant-time distributed algorithms on sparse graphs. We construct such constant-time algorithms for various approximation problems for hyperfinite and almost finite graph classes. We also prove the Hausdorff convergence of the spectra of convergent graph sequences in the strongly almost finite category., Comment: Typos are corrected, references and the converse of the statement of Prop. 5.2 are added

We prove that for any countable group G there exists a free minimal continuous action of G on the Cantor set admitting an invariant Borel probability measure., Comment: to appear in Ergodic Theory and Dynamical Systems. arXiv admin note: text overlap with arXiv:1803.05461

Using the notion of proper Cantor colorings we prove the following theorem. For any countably infinite group $\Gamma$, there exists a free continuous action $\zeta: \Gamma \curvearrowright C$ on the Cantor set, which is universal in the following sense: for any free Borel action $\alpha: \Gamma \curvearrowright X$ on the standard Borel space, there exists an injective Borel map $\Theta_\alpha: X\to C$ such that $\Theta_\alpha\circ \alpha=\zeta \circ \Theta_\alpha$. We extend our theorem for (nonfree) Borel $(\Gamma,Z)$-actions, where $Z$ is a uniformly recurrent subgroup.

We prove that any countable non-amenable group G admits a free minimal amenable purely infinite action on the non-compact Cantor set. This answers a question of Kellerhals, Monod and R{\o}rdam., Comment: 16 pages

In this survey we give a concise introduction to a continuous version of Borel combinatorics. Our approach will have a certain algorithm-theoretic nature and we will give special emphasis to the notion of almost finiteness introduced by Matui as a continuous analogue of Borel hyperfiniteness. We also show how the theory can be used to study spectral convergence for graph Laplacians., Comment: 12 pages

We show that if A_1, A_2, ... , A_n are square matrices, each of them is either unitary or self-adjoint, and they almost commute with respect to the rank metric, then one can find commuting matrices B_1, B_2, ... , B_n that are close to the matrices A_i in the rank metric., Comment: 23 pages, final accepted version, to appear in Groups Geom. Dyn

We study uniformly recurrent subgroups (URS) introduced by Glasner and Weiss \cite{GW}. Answering their query we show that any URS $Z$ of a finitely generated group is the stability system of a minimal $Z$-proper action. We also show that for any sofic $URS$ $Z$ there is a $Z$-proper action admitting an invariant measure. We prove that for a $URS$ $Z$ all $Z$-proper actions admits an invariant measure if and only if $Z$ is coamenable. In the second part of the paper we study the separable $\C^*$-algebras associated to URS's. We prove that if an URS is generic then its $\C^*$-algebra is simple. We give various examples of generic URS's with exact and nuclear $\C^*$-algebras and an example of a URS $Z$ for which the associated simple $\C^*$-algebra is not exact and not even locally reflexive, in particular, it admits both a uniformly amenable trace and a nonuniformly amenable trace., Comment: The section "Exactness and nuclearity" is added

We prove that if $G$ is a finitely generated group and $Z$ is a uniformly recurrent subgroup of $G$ then there exists a minimal system $(X,G)$ with $Z$ as its stability system. This answers a query of Glasner and Weiss \cite{GW} in the case of finitely generated groups. Using the same method (introduced by Alon, Grytczuk, Haluszczak and Riordan \cite{AGHR}) we will prove that finitely generated sofic groups have free Bernoulli-subshifts admitting an invariant probability measure., Comment: 8 pages

Equationally compact subgroups of countable groups were introduced by Banaschewski. For all known cases the orbit closure of such a subgroup is a countable subset in the space of subgroups and has finite Cantor-Bendixson rank. We show that there exists a finitely generated group $\Gamma$ such that for any countable ordinal $\alpha$ we have an equationally compact subgroup $H\subset \Gamma$ for which the Cantor-Bendixson rank of the orbit closure of $H$ equals to $\alpha+2$. Then we give an explicite construction of continuum many equationally compact subgroups of $\Gamma$ such that the associated ergodic Bernoulli shift actions are pairwise weakly incomparable. We also answer two questions on equational compactness posed by Prest and Rajani.

We present a novel approach to the representation theory of finite dimensional algebras motivated by the emerging theory of graph limits. We introduce the rank spectrum of a finite dimensional algebra $R$ over a finite field. The elements of the rank spectrum are representations of the algebra into von Neumann regular rank algebras, and two representations are considered to be equivalent if they induce the same Sylvester rank functions on $R$-matrices. Based on this approach, we can divide the finite dimensional algebras into three types: finite, amenable and non-amenable representation types. We prove that string algebras are of amenable representation type, but the wild Kronecker algebras are not. Here, the amenability of the rank algebras associated to the limit points in the rank spectrum plays a very important part. We also show that the limit points of finite dimensional representations of algebras of amenable representation type can always be viewed as representations of the algebra in the continuous ring invented by John von Neumann in the 1930's. As an application in algorithm theory, we introduce and study the notion of testing of parameters of modules over finite dimensional algebras, that is analogous to the property testing of bounded degree graphs introduced by Goldreich and Ron. We shall see that for string algebras all the reasonable (stable) parameters are testable., Comment: Some typos have been corrected

Motivated by the theory of graph limits, we introduce and study the convergence and limits of linear representations of finite groups over finite fields. The limit objects are infinite dimensional representations of free groups in continuous algebras. We show that under a certain integrality condition, the algebras above are skew fields. Our main result is the extension of Schramm's characterization of hyperfiniteness to linear representations., Comment: Final version. To appear in the Journal of Algebra

Let $\Gamma$ be a discrete group. Following Linnell and Schick one can define a continuous ring $c(\Gamma)$ associated with $\Gamma$. They proved that if the Atiyah Conjecture holds for a torsion-free group $\Gamma$, then $c(\Gamma)$ is a skew field. Also, if $\Gamma$ has torsion and the Strong Atiyah Conjecture holds for $\Gamma$, then $c(\Gamma)$ is a matrix ring over a skew field. The simplest example when the Strong Atiyah Conjecture fails is the lamplighter group $\Gamma=Z_2\wr Z$. It is known that $C(Z_2\wr Z)$ does not even have a classical ring of quotients. Our main result is that if $H$ is amenable, then $c(Z_2\wr H)$ is isomorphic to a continuous ring constructed by John von Neumann in the $1930's$., Comment: 16 pages

First, we answer a question of Pestov, by proving that the full group of a sofic equivalence relation is a sofic group. Then, we give a short proof of the theorem of Grigorchuk and Medynets that the topological full group of a minimal Cantor homeomorphism is LEF. Finally, we show that for certain non-amenable groups all the generalized lamplighter groups are sofic.

In the paper we are dealing with metric measure spaces of diameter at most one and of total measure one. Gromov introduced the sampling compactification of the set of these spaces. He asked whether the metric measure space invariants extend to the compactification. Using ideas of the newly developed theory of graph limits we identify the elements of the compactification with certain geometric objects and show how to extend various invariants to this space. We will introduce the notion of ultralimit of metric measure spaces, that will be the main technical tool of our paper., Comment: Many corrections. The title has changed

Hyperfiniteness or amenability of measurable equivalence relations and group actions has been studied for almost fifty years. Recently, unexpected applications of hyperfiniteness were found in computer science in the context of testability of graph properties. In this paper we propose a unified approach to hyperfiniteness. We establish some new results and give new proofs of theorems of Schramm, Lov\'asz, Newman-Sohler and Ornstein-Weiss.

Grigorchuk and Medynets recently announced that the topological full group of a minimal Cantor Z-action is amenable. They asked whether the statement holds for all minimal Cantor actions of general amenable groups as well. We answer in the negative by producing a minimal Cantor Z^2-action for which the topological full group contains a non-abelian free group., Comment: 3 pages (some comments added)

Let $\Gamma$ be a countable group acting on a countable set $X$ by permutations. We give a necessary and sufficient condition for the action to have a quasi-invariant mean with a given cocycle. This can be viewed as a combinatorial analogue of the condition for the existence of a quasi-invariant measure in the Borel case given by Miller. Then we show a geometric condition that guarantees that the corresponding action on the Stone-\v{C}ech compactification is Zimmer amenable. The geometric condition (weighted hyperfiniteness) resembles Property A. We do not know the exact relation between the two notions, however, we can show that amenable groups and groups of finite asymptotic dimension are weighted hyperfinite.

We introduce a natural pseudometric on the space of actions of $d$-generated groups, such that the zero classes are exactly the weak equivalence classes and the metric identification with respect to this pseudometric is compact. We analyze convergence in this space and prove that every class contains an action that properly satisfies every combinatorial type condition that it satisfies with arbitrarily small error. We also show that the class of every free non-amenable action contains an action that satisfies the measurable von Neumann problem. The results have analogues in the realm of unitary representations as well.

We introduce the notion of hyperfiniteness for permutation actions of countable groups on countable sets and give a geometric and analytic characterization, similar to the known characterizations for amenable actions. We also answer a question of van Douwen on actions of the free group on two generators on countable sets., Comment: 19 pages, added a more general result and corrected typos

Using probabilistic methods, Collins and Dykema proved that the free product of two sofic groups amalgamated over a monotileably amenable subgroup is sofic as well. We show that the restriction is unnecessary; the free product of two sofic groups amalgamated over an arbitrary amenable subgroup is sofic. We also prove a group theoretical analogue of a result of Kenley Jung. A finitely generated group is amenable if and only if it has only one sofic representation up to conjugacy equivalence., Comment: Reference added

The analytic von Neumann regular closure $R(\Gamma)$ of a complex group algebra $\C\Gamma$ was introduced by Linnell and Schick. This ring is the smallest $*$-regular subring in the algebra of affiliated operators $U(\Gamma)$ containing $\C\Gamma$. We prove that all the algebraic von Neumann regular closures corresponding to sofic representations of an amenable group are isomorphic to $R(\Gamma)$. This result can be viewed as a structural generalization of L\"uck's Approximation Theorem. \noindent The main tool of the proof which might be of independent interest is that an amenable group algebra $K\Gamma$ over any field $K$ can be embedded to the rank completion of an ultramatricial algebra.

We study profinite actions of residually finite groups in terms of weak containment. We show that two strongly ergodic profinite actions of a group are weakly equivalent if and only if they are isomorphic. This allows us to construct continuum many pairwise weakly inequivalent free actions of a large class of groups, including free groups and linear groups with property (T). We also prove that for chains of subgroups of finite index, Lubotzky's property ($\tau$) is inherited when taking the intersection with a fixed subgroup of finite index. That this is not true for families of subgroups in general leads to answering the question of Lubotzky and Zuk, whether for families of subgroups, property ($\tau$) is inherited to the lattice of subgroups generated by the family. On the other hand, we show that for families of normal subgroups of finite index, the above intersection property does hold. In fact, one can give explicite estimates on how the spectral gap changes when passing to the intersection. Our results also have an interesting graph theoretical consequence that does not use the language of groups. Namely, we show that an expander covering tower of finite regular graphs is either bipartite or stays bounded away from being bipartite in the normalized edge distance., Comment: Corrections made based on the referee's comments

We prove that the Betti numbers of simplicial complexes of bounded vertex degrees are testable in constant time., Comment: to appear in the volume "Fete of Combinatorics and Computer Science"

Nguyen and Onak constructed the first constant-time algorithm for the approximation of the size of the maximum matching in bounded degree graphs. The Borel oracle machinery is a tool that can be used to convert some statements in Borel graph theory to theorems in the field of constant-time algorithms. In this paper we illustrate the power of this tool to prove the existence of the above mentioned constant-time approximation algorithm.

We introduce the notion of sofic measurable equivalence relations. Using them we prove that Connes' Embedding Conjecture as well as the Measurable Determinant Conjecture of L\"uck, Sauer and Wegner hold for treeable equivalence relations., Comment: 18 pages

We prove that any involution-invariant probability measure on the space of trees with maximum degrees at most d arises as the local limit of a convergent large girth graph sequence. This answers a question of Bollobas and Riordan.

In this paper we develop a measure-theoretic method to treat problems in hypergraph theory. Our central theorem is a correspondence principle between three objects: An increasing hypergraph sequence, a measurable set in an ultraproduct space and a measurable set in a finite dimensional Lebesgue space. Using this correspondence principle we build up the theory of dense hypergraphs from scratch. Along these lines we give new proofs for the Hypergraph Removal Lemma, the Hypergraph Regularity Lemma, the Counting Lemma and the Testability of Hereditary Hypergraph Properties. We prove various new results including a strengthening of the Regularity Lemma and an Inverse Counting Lemma. We also prove the equivalence of various notions for convergence of hypergraphs and we construct limit objects for such sequences. We prove that the limit objects are unique up to a certain family of measure preserving transformations. As our main tool we study the integral and measure theory on the ultraproduct of finite measure spaces which is interesting on its own right., Comment: 49 pages, 1 figure

We show that a sufficiently large graph of bounded degree can be decomposed into quasi-homogeneous pieces. The result can be viewed as a "finitarization" of the classical Farrell-Varadarajan Ergodic Decomposition Theorem., Comment: Corrected an error in the proof of the Homogeneity Lemma. A new result is proved about edge-colorings of convergent graph sequences

Parameter testing algorithms are using constant number of queries to estimate the value of a certain parameter of a very large finite graph. It is well-known that graph parameters such as the independence ratio or the edit-distance from 3-colorability are not testable in bounded degree graphs. We prove, however, that these and several other interesting graph parameters are testable in bounded degree graphs of subexponential growth., Comment: To appear in Random Structures and Algorithms. (note that the title has changed)

Using the spectral theory of weakly convergent sequences of finite graphs, we prove the uniform existence of the integrated density of states for a large class of infinite graphs.

We show that every countable non-abelian free group $\Gamma $ admits a spherically transitive action on a rooted tree $T$ such that the action of $\Gamma $ on the boundary of $T$ is not essentially free. This reproves a result of Bergeron and Gaboriau. The existence of such an action answers a question of Grigorchuk, Nekrashevich and Sushchanskii.

We study the integral and measure theory of the ultraproduct of finite sets. As a main application we construct limit objects for hypergraph sequences. We give a new proof for the Hypergraph Removal Lemma and the Hypergraph Regularity Lemma., Comment: 25 pages

We construct a minimal topological action $\wp$ of a non-amenable group on a Cantor set $C$, which is non-uniquely ergodic and furthermore there exist ergodic invariant measures $\mu_1$ and $\mu_2$ such that $(\wp,C,\mu_1)$ and $(\wp,C,\mu_2)$ are not orbit equivalent measurable equivalence relations.

We study the combinatorial analogues of the classical invariants of measurable equivalence relations. We introduce the notion of cost and $\beta$-invariants (the analogue of the first $L^2$-Betti number introduced by Gaboriau) for sequences of finite graphs with uniformly bounded vertex degrees and examine the relation of these invariants and the rank gradient resp. mod $p$ homology gradient invariants introduced by Lackenby for residually finite groups.

Introducing and studying the pattern frequency algebra, we prove the analogue of L\"uck's approximation theorems on $L^2$-spectral invariants in the case of aperiodic order. These results imply a uniform convergence theorem for the integrated density of states as well as the positivity of the logarithmic determinant of certain discrete Schrodinger operators.

Lenz and Stollmann recently proved the existence of the integrated density of states in the sense of uniform convergence of the distributions for certain operators with aperiodic order. The goal of this paper is to establish a relation between aperiodic order, uniform spectral convergence and the continuous algebras invented by John von Neumann. We illustrate the technique by proving the uniform spectral convergence for random Schodinger operators on lattices with finite site probabilities, percolation Hamiltonians and for the pattern-invariant operators of self-similar graphs.