CS Paper Radar

The Lovász Local Lemma Is Sharp for the Hat Guessing Number

Thomas Delépine, Matthieu Rosenfeld

cs.DM math.CO ·submitted 2026-11-03 09:38 UTC · v1
theory

Abstract

In the hat guessing game on a graph $G$, each vertex is occupied by a player wearing a hat whose color is chosen from a set of $q$ colors. Each player knows the graph and their position in it and sees only the hat colors of their neighbors. The players may agree on a strategy beforehand but must simultaneously try to guess their own hat colors without communicating. They win if at least one player guesses their own hat color correctly. The hat guessing number of $G$, denoted by $\textrm{HG}(G)$, is the largest integer $q$ for which the players have a strategy that guarantees a win for every assignment of hat colors. A direct application of the symmetric Lovász Local Lemma shows that $\textrm{HG}(G) < eΔ$ for every graph $G$ of maximum degree at most $Δ\ge 1$. We prove that this bound is asymptotically sharp: for every $\varepsilon > 0$ and every sufficiently large $Δ$, there exists a graph $G$ of maximum degree at most $Δ$ with $\textrm{HG}(G) \ge (e - \varepsilon)Δ$. This answers a question of Alon et al., disproves the conjecture $\textrm{HG}(G) \le 2Δ(G)$ of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves $\textrm{HG}(G) = 4Δ(G)/3$. The hat guessing number thus provides a natural combinatorial problem in which the Lovász Local Lemma is asymptotically tight.

Closest papers

Nearest neighbours by meaning across the whole index.

Structural and computational aspects of majority coloring games

cs.DM math.CO ·2026-09-29 ·Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan, Eshwar Srinivasan
theory similarity 0.69
Abstract · 47 pages, 22 figures, 2 tables

A majority coloring of a graph $G = (V,E)$ is a coloring of $V(G)$ such that, for each vertex $v$, the number of neighbors of $v$ with the same color as $v$ is at most $deg(v)/2$. A strong majority coloring is a coloring of $V(G)$ such that, for each vertex $v$, every monochromatic subset of $N(v)$ has size at most $deg(v)/2$. The (strong) majority coloring game is a two-player Maker-Breaker-type game, in which two players Alice and Bob color the vertices of a graph $G$ alternately, maintaining the (strong) majority condition. The least number of colors such that Alice has a winning strategy in such a game is called the (strong) majority game chromatic number of the graph $G$, denoted $μ_g(G)$ (or $\mathrm{Maj}_g(G)$ for the strong version). For the majority coloring game, we prove that $μ_g(G) \le 3$ under the following cases: $G$ is a $2$-caterpillar, $G$ is a rooted tree with all leaves at depth $k \le 4$, and $G$ is a subdivision of some graph. The latter resolves a problem posed by Bosek--Grytczuk--Jakóbczak in 2019, who also asked whether $μ_g(T) \le 3$ for every tree $T$. For the latter question, we discuss various difficulties that arise when natural strategies are attempted by Alice to win the majority coloring game on trees. We include a comparison with the marking game and relaxed coloring game on trees, and with the majority coloring game on locally finite acyclic graphs $G$ with $δ(G) > 1$. For the strong majority coloring game, we compute $\mathrm{Maj}_g(C_n)$ exactly for each cycle $C_n$, $n \ge 3$. We also initiate the study of the computational complexity of the strong majority coloring game; specifically, we prove that the decision version of the Strong Majority Game Chromatic Number problem is PSPACE-complete. We also show that the Strong Majority 2-Coloring problem is NP-complete on Eulerian graphs.

0.19

On the majority game chromatic number of forests and other graphs

cs.DM math.CO ·2026-09-20 ·Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan
published similarity 0.66
Abstract · 22 pages, 9 figures, accepted at FSTTCS 2026

A majority coloring of a graph $G$ is a vertex coloring of $G$ in which no vertex has more than half of its neighbors colored with its own color. The least number of colors required for a majority coloring of $G$ is the majority chromatic number $μ(G)$. The majority coloring game, introduced by Bosek et al. (2019), is a two-player Maker-Breaker-type game where the players alternately color vertices while maintaining the majority condition at each vertex; the least number of colors required for the first player to have a winning strategy on $G$ is the majority game chromatic number $μ_g(G)$. In contrast with the static case, Bosek et al. show that $μ_g(G)$ is unbounded in general, while $μ_g(G)\le col_g(G)$, where $col_g(G)$ is the game coloring number of $G$. It is known (cf. Faigle et al. (1993)) that, for any acyclic graph $G$, $col_g(G) \leq 4$, so $μ_g(G) \leq 4$ as well. We improve this bound by showing that $μ_g(G) \leq 3$ for any acyclic graph $G$ of maximum degree at most $4$. We also show that $μ_g(G) = 2$ if $G$ is a nonempty path, star, or complete graph, or a disjoint union of such graphs. These improve the results of Bosek et al. We also initiate the study of the computational complexity of the pre-coloring extension problem for the static and game versions of majority coloring. We show that the Majority $k$-precoloring Extension problem is NP-complete for each $k \geq 2$. When $k = 2$, it remains NP-complete on the class of bipartite graphs where maximum degrees of each part are $5$ and $6$, and when $k = 3$ it remains NP-complete on the class of $12$-regular planar graphs. We show that the game version is PSPACE-complete, even when the number of colors $k=χ(G)$, and even when $k=2$ and $G$ is a bipartite graph in which one part has maximum degree equal to $9$. The results on the game versions also hold for the variation where Bob starts the game.

0.46

Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games

cs.GT math.OC ·2026-10-04 ·Hritiz Gogoi
theory similarity 0.66
Abstract · 16 pages

In Max-$k$-Cut games, optimal colorings maximize social welfare, but are they stable against coordinated deviations that strictly benefit every participating player? A recurring conjecture in the literature asserts that, for unweighted graphs, every optimal coloring has this stability property, known as strong equilibrium. We disprove the conjecture for every $k\ge3$ by exhibiting a finite, simple, connected, unweighted graph with an optimal coloring that is not a strong equilibrium. The profitable coalitional deviation leads to another optimal coloring: every coalition member gains, while players outside the coalition bear the corresponding losses and social welfare remains unchanged. We also give an exact identity relating coalitional gains, changes in cut value, and internal conflicts, recovering the known stability guarantee for optimal colorings when the maximum degree is at most $2k-1$. For strong deviations from general Nash equilibria, we establish a sharp upper bound on the number of monochromatic edges remaining within the coalition and show that this number can exceed the coalition size.

0.09

Communication-Efficient $(1+\varepsilon)Δ$-Edge Coloring and Lovász Local Lemma

cs.DC ·2026-09-30 ·Yi-Jun Chang, Nima Dolatabadi, Hung Thuan Nguyen
similarity 0.65
Abstract

We study edge coloring in the two-party edge-partition model, where Alice and Bob each know part of the edge set and must jointly produce a proper coloring with little communication. Previous work gave a deterministic $(2Δ-1)$-edge-coloring protocol using $O(n)$ bits, leaving open whether fewer colors can be obtained efficiently. We simultaneously reduce both the number of colors and the communication. For every fixed $\varepsilon>0$ and all sufficiently large $Δ$, we give a public-coin Las Vegas protocol that finds a proper $(1+\varepsilon)Δ$-edge coloring using $O(ne^{-γΔ} + 1)$ expected bits and $O\left(\frac{\log n}Δ+1\right)$ expected rounds, where $γ>0$ depends only on $\varepsilon$. Thus, the expected communication is $o(n)$ when $Δ=ω(1)$ and $O(1)$ when $Δ\ge C_\varepsilon\log n$, for a sufficiently large constant $C_\varepsilon$. Using only private coins adds $O(\log n)$ expected bits. Our key idea is a new randomized coloring procedure that allows Alice and Bob to color their edges using essentially the same color space with only a small amount of coordination, so most of their random choices remain private. To make this procedure succeed, we develop a communication-efficient constructive Lovász local lemma (LLL) for two parties. Our two-party constructive LLL is also of independent interest. We illustrate its broader applicability by applying it to standard LLL formulations of several other classical problems, obtaining communication-efficient two-party protocols.

0.16

Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

cs.DC cs.DS ·2026-10-15 ·Yann Bourreau, Sebastian Brandt, Ananth Narayanan
theoryhot direction similarity 0.64
Abstract

We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.

0.21

Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL

cs.DS ·2026-11-04 ·Mohsen Ghaffari, Sijin Peng
similarity 0.63
Abstract

We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update. For every fixed $ε>0$, the algorithm maintains a $(1+ε)Δ$ edge coloring under edge insertions and deletions in $\mathrm{poly}(1/ε)$ worst-case expected update time against an oblivious adversary, provided $Δ\geΔ_ε=\widetildeΘ(1/ε^2)$. The previous constant-time algorithm of Bhattacharya, Costa, Panski, and Solomon (BCPS) required $Δ\ge(\log n/ε^4)^{Θ(\log(1/ε)/ε)}$, where $n$ is the number of vertices. We remove this dependence on $n$, answering their open question. Our approach differs substantially from that of BCPS, which relied on coloring in locally tree-like subgraphs. Instead, we draw on distributed algorithms that organize partial coloring through successive applications of the Lovász Local Lemma (LLL). We develop a dynamic LLL solver with worst-case expected update bounds and a dynamic splitting algorithm that partitions edges into low-degree subgraphs. A key technical contribution is a bottom-up method for iterative splitting, which avoids the logarithmic overhead of maintaining successive levels. It achieves constant expected update time by adaptively choosing which levels to inspect and repair, rather than inspecting every level after each update. We believe these dynamic splitting and LLL tools can be of interest beyond edge coloring.

0.20

Distributed Near-Equitable Coloring in the LOCAL Model

cs.DC cs.DS ·2026-08-10 ·Amit Nir, David Peleg
similarity 0.62
Abstract · 54 pages, 5 figures, 1 table

For an $n$-vertex graph of maximum degree $Δ$, an equitable $(Δ+1)$-coloring is a proper coloring all of whose color classes have size $σ= n/(Δ+1)$ up to rounding. Known algorithms for relaxations of this target aggregate along a spanning structure, at cost scaling with the diameter $D$. We study near-equitable coloring in the LOCAL model and prove that, for deterministic algorithms, exact balance is inherently global: already on the cycle $C_n$, exact balanced free $3$-coloring requires $Ω(n)$ rounds. More generally, additive imbalance $g$ requires $Ω(n/g)$ rounds, matching a deterministic $O((n/g)\log^* n)$-round algorithm up to the $\log^* n$ factor, and these problems realize a dense family of intermediate deterministic LOCAL complexities $\tildeΘ(n^α)$, $α\in (0,1)$, on cycles. The exact bound is sharp in two further senses: the identifier-universe threshold is exactly $N=n+1$, and the $\log^* n$ gap cannot be closed via faster ruling-set anchors. The bound then extends to twisted fiber products, an explicit family realizing, for every $Δ\ge 3$, every diameter scale from the Moore bound $Θ(\log n/\logΔ)$ up to $Θ(n/Δ)$. Exact equitable $(Δ+1)$-coloring requires $Θ(D)$ rounds deterministically on this family, so exactness costs diameter time already on bounded-degree graphs of logarithmic diameter. In contrast, coarse balance admits local algorithms. On cycles, constant multiplicative equity costs $Θ(\log^* n)$ rounds. On general graphs with large color classes, all class sizes can be kept within $(1\pmη)$ times the average in time independent of the diameter: with palette exactly $Δ+1$ for $Δ\le 2^{\sqrt{\log n}/C}$, and with palette $(1+η)(Δ+1)$ for every $Δ\le n^{1-o(1)}$, the latter in $O(\log n\,(\log\log n)^2)$ rounds.

0.42

The price of anarchy in the max-distance network creation game is not constant

cs.GT cs.DM ·2026-09-15 ·Christoph Schlegel
theory similarity 0.61
Abstract

At edge price $α=1$, we construct an infinite family of pure Nash equilibria of the unilateral max-distance network creation game with $\PoA\ge2^{\sqrt{\log_2 n}-O(\log\log n)}$. Together with the known upper bound, this gives $2^{Θ(\sqrt{\log n})}$ along the constructed sequence of population sizes. We subdivide every edge of the bipartite double cover of a distance-uniform graph with large diameter constructed by Lavrov, Loh and Messegué, and let each subdivision vertex buy its two incident edges. A distance calculation rules out every profitable unilateral deviation. The equilibria are not strict. We also give a short proof that the price of anarchy is constant for every polynomially vanishing edge price.

0.30