Preprint
Jul 2026
Distributed Symmetry Breaking on Hyperbolic Random Graphs
It is proved that the related symmetry-breaking problems of maximal independent set (MIS) and maximal matching (MM) are substantially harder: a lower bound of $\Omega\left(\frac{\log\log n}{\log\log\log n}\right)$ for MIS and MM on HRGs is established.
Yannic Maus, Janosch Ruff, Sonia Simons et al.
· 0 citations