BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that every amenable one-ended Cayley graph has an invariant spanning tree of one end. More generally, for any 1-ended amenable unimodular random graph we construct a factor of iid percolation (jointly unimodular subgraph) that is almost surely a spanning tree of one end. In [2] and [1] similar claims were proved, but the resulting spanning tree had 1 or 2 ends, and one had no control of which of these two options would be the case.
We prove that the infinite components of the Free Uniform Spanning Forest of a Cayley graph are indistinguishable by any invariant property, given that the forest is different from its wired counterpart. Similar result is obtained for the Free Minimal Spanning Forest. We also show that with the above assumptions there can only be 0, 1 or infinitely many components. These answer questions by Benjamini, Lyons, Peres and Schramm. Our methods apply to a more general class of percolations, those satisfying "weak insertion tolerance", and work beyond Cayley graphs, in the more general setting of unimodular random graphs.
We show that there exists an ergodic conductance environment such that the weak (annealed) invariance principle holds for the corresponding continuous time random walk but the quenched invariance principle does not hold.
We present a random isometry-invariant subgraph of a Cayley graph such that with probability 1 its exponential growth rate does not exist.
We construct a sequence of finite graphs that weakly converge to a Cayley graph, but there is no labelling of the edges that would converge to the corresponding Cayley diagram. A similar construction is used to give graph sequences that converge to the same limit, and such that a spanning tree in one of them has a limit that is not approximable by any subgraph of the other. We give an example where this subtree is a Hamiltonian cycle, but convergence is meant in a stronger sense. These latter are related to whether having a Hamiltonian cycle is a testable graph property.
We generalize theorems of Kesten and Deuschel-Pisztora about the connectedness of the exterior boundary of a connected subset of Zd, where "connectedness" and "boundary" are understood with respect to various graphs on the vertices of Zd. We provide simple and elementary proofs of their results. It turns out that the proper way of viewing these questions is graph theory, instead of topology.
Initial steps in the study of inner expansion properties of infinite Cayley graphs and other infinite graphs, such as hyperbolic ones, are taken, in a flavor similar to the well-known Lipton-Tarjan square root separation result for planar graphs. Connections to relaxed versions of quasi-isometries are explored, such as regular and semiregular maps.
Let Γ 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-Č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.
Generalizing the notion of split graphs to uniform hypergraphs, we prove that the class of these hypergraphs can be characterized by a finite list of excluded induced subhypergraphs. We show that a characterization by generalized degree sequences is impossible, unlike in the well-known case of split graphs. We also give an algorithm to decide whether a given uniform hypergraph is a split hypergraph. If it is, the algorithm gives a splitting of it; the running time is O(NlogN). These answer questions of Sloan, Gy. Turán and Peled.
Consider Bernoulli(1/2) percolation on Zd, and define a perfect matching between open and closed vertices in a way that is a deterministic equivariant function of the configuration. We want to find such matching rules that make the probability that the pair of the origin is at distance greater than r decay as fast as possible. For two dimensions, we give a matching of decay cr1/2, which is optimal. For dimension at least 3 we give a matching rule that has an exponential tail. This substantially improves previous bounds. The construction has two major parts: first we define a sequence of coarser and coarser partitions of Zd in an equivariant way, such that with high probability the cell of a fixed point is like a cube, and the labels in it are i.i.d. Then we define a matching for a fixed finite cell, which stabilizes as we repeatedly apply it for the cells of the consecutive partitions. Our methods also work in the case when one wants to match points of two Poisson processes, and they may be applied to allocation questions.
We study isomorphism invariant point processes of Rd whose groups of symmetries are almost surely trivial. We define a 1-ended, locally finite tree factor on the points of the process, that is, a mapping of the point configuration to a graph on it that is measurable and equivariant with the point process. This answers a question of Holroyd and Peres. The tree will be used to construct a factor isomorphic to Zn. This perhaps surprising result (that any d and n works) solves a problem by Steve Evans. The construction, based on a connected clumping with 2i vertices in each clump of the i'th partition, can be used to define various other factors.
We answer three questions posed in a paper by Babson and Benjamini. They introduced a parameter CG for Cayley graphs G that has significant application to percolation. For a minimal cutset of G and a partition of this cutset into two classes, take the minimal distance between the two classes. The supremum of this number over all minimal cutsets and all partitions is CG. We show that if it is finite for some Cayley graph of the group then it is finite for any (finitely generated) Cayley graph. Having an exponential bound for the number of minimal cutsets of size n separating o from infinity also turns out to be independent of the Cayley graph chosen. We show a 1-ended example (the lamplighter group), where CG is infinite. Finally, we give a new proof for a question of de la Harpe, proving that the number of n-element cutsets separating o from infinity is finite unless G is a finite extension of Z.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.