Perfect matchings as IID factors on non-amenable groups
From MaRDI portal
Publication:648969
DOI10.1016/J.EJC.2011.03.008zbMATH Open1229.05115arXiv0911.0092OpenAlexW2963876272MaRDI QIDQ648969FDOQ648969
Authors: Russell Lyons, Fedor Nazarov 
Publication date: 29 November 2011
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: We prove that in every bipartite Cayley graph of every non-amenable group, there is a perfect matching that is obtained as a factor of independent uniform random variables. We also discuss expansion properties of factors and improve the Hoffman spectral bound on independence number of finite graphs.
Full work available at URL: https://arxiv.org/abs/0911.0092
Recommendations
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- On the Shannon capacity of a graph
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Ergodic theory of amenable group actions. I: The Rohlin lemma
- Symmetric Random Walks on Groups
- TWO THEOREMS IN GRAPH THEORY
- Title not available (Why is that?)
- Poisson matching
- On groups with full Banach mean value
- On the independence and chromatic numbers of random regular graphs
- Induced Forests in Regular Graphs with Large Girth
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Measurable chromatic and independence numbers for ergodic graphs and group actions
- Large independent sets in regular graphs of large girth
- Non-abelian free group actions: Markov processes, the Abramov-Rohlin formula and Yuzvinskii's formula
- Group-invariant percolation on graphs
- Borel oracles. An analytical approach to constant-time algorithms
- Borel chromatic numbers
- Poisson trees, succession lines and coalescing random walks
- Trees and matchings from point processes
- Tree and grid factors for general point processes
- Stationary map coloring
- Factors of independent and identically distributed processes with non-amenable group actions
- Rigidity theorems for actions of product groups and countable Borel equivalence relations
- Amenable actions and almost invariant sets
- Invariant colorings of random planar maps
- Closed Sets Without Measurable Matching
- Sets with doubleton sections, good sets and ergodic theory
Cited In (37)
- MEASURABLE PERFECT MATCHINGS FOR ACYCLIC LOCALLY COUNTABLE BOREL GRAPHS
- Measurable equidecompositions for group actions with an expansion property
- Factor of IID Percolation on Trees
- Measurable versions of the Lovász local lemma and measurable graph colorings
- A Markovian and Roe-algebraic approach to asymptotic expansion in measure
- KŐNIG’S LINE COLORING AND VIZING’S THEOREMS FOR GRAPHINGS
- A spectral strong approximation theorem for measure-preserving actions
- Groups and dynamics: topology, measure, and Borel structure. Abstracts from the workshop held January 16--22, 2022
- Orienting Borel graphs
- Controllability, matching ratio and graph convergence
- Følner tilings for actions of amenable groups
- Suboptimality of local algorithms for a class of max-cut problems
- Continuity of the Ising phase transition on nonamenable groups
- Ramanujan graphings and correlation decay in local algorithms
- An antibasis result for graphs of infinite Borel chromatic number
- Ultraproducts of measure preserving actions and graph combinatorics
- Entropy and expansion
- Factor-of-iid balanced orientation of non-amenable graphs
- Correlation Bounds for Distant Parts of Factor of IID Processes
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- Independence ratio and random eigenvectors in transitive graphs
- Weak containment of measure-preserving group actions
- Baire measurable paradoxical decompositions via matchings
- Equivalence relations that act on bundles of hyperbolic spaces
- On Baire measurable colorings of group actions
- Finitary codings for spatial mixing Markov random fields
- Markovian properties of continuous group actions: algebraic actions, entropy and the homoclinic group
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
- BROOKS’ THEOREM FOR MEASURABLE COLORINGS
- A determinacy approach to Borel combinatorics
- On the almost eigenvectors of random regular graphs
- Measurable graph combinatorics
- MEASURABLE REALIZATIONS OF ABSTRACT SYSTEMS OF CONGRUENCES
- Factors of IID on Trees
- Uniform even subgraphs and graphical representations of Ising as factors of i.i.d.
- Ising model on trees and factors of IID
This page was built for publication: Perfect matchings as IID factors on non-amenable groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648969)
