Fetching the paper…

Reading the bibliography…

Invariant random matchings in Cayley graphs · Around

2012

Invariant random matchings in Cayley graphs

Csoka, Endre, Lippner, Gabor

Original
PDF
Post on X

Understand

We prove that any non-amenable Cayley graph admits a factor of IID perfect matching.

We also show that any connected d-regular vertex tran- sitive graph admits a perfect matching.
The two results together imply that every Cayley graph admits an invariant random perfect matching.
A key step in the proof is a result on graphings that also applies to finite graphs.

Built on

M. Jerrum, U. Vazirani, A Mildly Exponential Approximation Algorithm for the Permanent, Algorithmica 16
1996
Earlier work this paper cites.
D. Gaboriau, R. Lyons. A measurable-group-theoretic solution to von NeumannÕs problem, Invent. Math. 177
2009
Earlier work this paper cites.

Similar

M. Bayati, D. Gamarnik, P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, ACM Symposium on Theory of Computing , STOC 2010
2010
Cited alongside, same era.
G. Elek, G. Lippner, Borel oracles. An analytical approach to constant-time algorithms, Proc. Amer. Math. Soc. 138
2010
Cited alongside, same era.
T. Conley, A. Kechris, R. Tucker-Drob, Ultraproducts of measure preserving actions and graph combinatorics, to appear in Ergodic Theory and Dynam. Systems
Cited in the paper.
H. Hatami, L. Lovász, B. Szegedy, Limits of local-global convergent graph sequences, preprint, arXiv:1205.4356
Original
Cited in the paper.

Then

R. Lyons, F. Nazarov, Perfect matchings as IID factors on non-amenable groups, Eur. J. Comb
2011
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…