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.
Abstract
Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative model of hyperbolic random graphs (HRGs), which provides a theoretical framework for studying such networks. Motivated by the observation that several algorithms perform better on real-world networks than their worst-case guarantees suggest, we design and analyse distributed algorithms under the assumption that the input graph is an HRG. Indeed, prior work has shown that the classical symmetry-breaking problem of $\Delta+1$ colouring, where $\Delta$ is the maximum degree of the graph, can be solved in 2 rounds on HRGs [Maus and Ruff; SODA'26]. In stark contrast to this 2-round algorithm for $\Delta+1$ colouring, we prove that the related symmetry-breaking problems of maximal independent set (MIS) and maximal matching (MM) are substantially harder: we establish a lower bound of $\Omega\left(\frac{\log\log n}{\log\log\log n}\right)$ for MIS and MM on HRGs. Our lower bound techniques rely on new structural insights that may be of independent interest: we show that HRGs contain $d$-ary trees with large height and degree which enables us to adapt and lift prior impossibility results for distributed algorithms to the setting of HRGs. We also show that these lower bounds are polynomial tight: we design algorithms tailored to HRGs that solve MIS and MM in $\tilde{\mathcal{O}}(\log^{5/3}\log n)$ rounds with high probability in the LOCAL model, improving over the general worst-case lower bound of $\Omega\left(\min\left\{\log \Delta, \sqrt{\log n}\right\}\right)$ rounds [Khoury and Schild; FOCS'25].
We study distributed vertex colouring on Hyperbolic Random Graphs (HRGs), a geometric random graph model capturing key structural features of real-world networks. This provides a natural setting for analysing distributed algorithms beyond worst-case general graphs. We introduce Sequential Radial Colouring, a CONGEST algorithm using only efficient local computation. The algorithm achieves a near-optimal palette, colouring HRGs with $\frac{4}{3}\chi$ colours and running in $O((\log\log n)^2)$ rounds a.a.s. We also give a variant that speeds this up to $O(\log\log n)$ rounds a.a.s., at the price of using $O(\chi\log\log n)$ colours. Finally, for every constant $\varepsilon>0$, it runs in $O(1)$ rounds a.a.s. when $\chi^{1+\varepsilon}$ colours are used. This greatly reduces the number of colours over the previous constant-round algorithm of Maus and Ruff (SODA 2026) by a factor of at least $n^{1/6}$. Our analysis contains a phase in which we consider a classical randomised colouring protocol on a (large) clique of the graph. We also delve deeper into this part of the analysis and improve upon previous results for colouring a clique $C$, bounding the number of rounds required as a function of the additive slack $s = |\Psi| - \chi$, where $\Psi$ is the set of colours used. In particular, constant-round colouring is possible if and only if $s=|C|^{1+\Omega(1)}$, while $s=|C|/\log |C|$ already gives the optimal $\Theta(\log\log |C|)$ round complexity.
Kostas Lakis, Johannes Lengler, Adeline Pittet· 0 citations
Mixing time bounds for Markov chains play a central role in characterizing the sample complexity of learning and inference from correlated data. While the mixing behavior of symmetric random walks on standard graph structures such as cycles, tori, and hypercubes is well understood, the impact of transition asymmetry remains less explored. In this work, we study the mixing times of lazy, asymmetric random walks on cycles, tori, and hypercubes, motivated by their relevance in practical applications. For the $n$-cycle, we develop a novel coupling construction that yields an order-wise tight upper bound $O\left(\frac{n^{2}}{p+q}\right)$, explicitly capturing the dependence on asymmetric transition probabilities $p$ and $q$. Numerical results indicate that this dependence is highly accurate. Building on this result, we derive corresponding bounds for $d$-dimensional tori. For asymmetric random walks on $n$-dimensional hypercubes, motivated by applications, we consider the problem of estimating expectations of functions that depend only on a subset $\Delta \ll n$ of coordinates. We show that the effective sample complexity improves to $O(n \log \Delta)$, compared to $O(n \log n)$ for the full chain. In all cases, our bounds recover the tightest known results for symmetric walks as special cases.
Mrudula A Mahindrakar, Hrushikesh A Kant, Avhishek Chatterjee· International Conference on...· 0 citations
For graph instances both for the min-max and the min-disagreement objectives, this work proves approximation guarantees that are substantially better than the bounds achievable for general graphs.
N. RajathRaoK., Jens Schlöter, Sami Davies et al.· 0 citations
The novel Radial Graphlet Distribution Distance is effective, and comparable in performance to state-of-the-art methods, and the easy-to-compute Joint Degree Distance is a viable alternative to graphlet-based distances, especially for measuring randomness in sets of very large networks.
Bram Mornie, D. Colle, P. Audenaert et al.· Computing· 0 citations
We investigate metric dimension and the localization game for several families of directed analogues of strongly regular graphs and their generalizations, adapting a probabilistic method of Babai (1980) for bounding the size of resolving sets in undirected strongly regular graphs. We derive upper bounds on the localization number and metric dimension depending on the order of the graph and the maximum number of common out-neighbours for a pair of vertices. We consider normally regular digraphs, so-called"ordinary graphs", classes of Deza digraphs, divisible design digraphs, nearly doubly regular tournaments, and certain doubly regular team tournaments. In particular, for asymmetric normally regular digraphs on $n$ vertices, we show that these invariants are bounded above by $O(\sqrt{n} \log n)$, and improve this to $O(\log n)$ for a class of doubly regular team tournaments.
For a given $d$-regular graph $G$, a Maker-Breaker degree game is played by two players who alternately claim previously unclaimed edges of $G$. In the standard variant, the goal of Maker is to maximize the maximum degree of their induced subgraph, while Breaker aims to minimize it, or equivalently, to guarantee a certain minimum degree in their own subgraph. A classic pairing strategy shows that Breaker can secure at least $\lfloor d/4 \rfloor$ edges at every vertex of any $d$-regular graph. Breaking this bound for general or even for specific classes of graphs has been a long-standing open problem in combinatorial game theory; indeed, J. Beck characterized this challenge in his monograph as the first among the seven most humiliating open problems of positional game theory. In this paper, we improve the $d/4$ bound for some infinite graph families, such as the hypercube graph $Q_d$, grids and tori. We first show that Breaker can secure a degree of one at every vertex in $Q_3$, then lift this to higher dimensions, where Breaker can guarantee a degree of at least $\lfloor d/3 \rfloor$.