Surprising identities for the greedy independent set on Cayley trees

DOI10.1017/jpr.2022.3zbMath1503.05055arXiv2103.03800OpenAlexW4293230675MaRDI QIDQ5049896

Alice Contat

Publication date: 14 November 2022

Published in: Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.03800

zbMATH Keywords

independent setgreedyCayley trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Randomized algorithms (68W20)

Related Items (1)

Parking on Cayley trees and frozen Erdős-Rényi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average performance of the greedy matching algorithm
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• The continuum random tree. I
• Random trees and applications
• Coalescent random forests
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• A combinatorial approach for discrete car parking on random labelled trees
• The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
• The jamming constant of uniform random graphs
• The continuum random tree. III
• Coding multitype forests: Application to the law of the total population of branching forests
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• The Greedy Independent Set in a Random Graph with Given Degrees

This page was built for publication: Surprising identities for the greedy independent set on Cayley trees