WorksMathematics
The Lovász Local Lemma Is Sharp for the Hat Guessing Number
Abstract
In the hat guessing game on a graph , each vertex is occupied by a player wearing a hat whose color is chosen from a set of 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 , denoted by , is the largest integer 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 for every graph of maximum degree at most . We prove that this bound is asymptotically sharp: for every and every sufficiently large , there exists a graph of maximum degree at most with . This answers a question of Alon et al., disproves the conjecture of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves . The hat guessing number thus provides a natural combinatorial problem in which the Lovász Local Lemma is asymptotically tight.
Introduction
The Lovász Local Lemma (LLL) is a classical result from the probabilistic method for proving the existence of objects avoiding a collection of local obstructions [5]. Its symmetric form says that a finite family of events, each of probability at most with a dependency graph of maximum degree at most , can be simultaneously avoided provided1 . In many applications, the lemma is used as a convenient black box, and the constants it gives are not expected to be optimal. The events often have additional structure that matters when seeking sharp results. Many stronger variants of the LLL allow us to exploit this structure. Shearer’s theorem [16] gives the optimal abstract criterion for arbitrary event systems with a prescribed dependency graph. More precisely, it characterizes the probability vectors that guarantee a positive probability of avoiding all events in every event system with the prescribed dependency graph. Thus, any improvement over Shearer’s criterion must exploit additional structure of the events themselves.
In a more concrete setting, Gebauer, Szabó, and Tardos [8] showed that the lopsided Local Lemma (see [6]) is asymptotically tight for bounded-occurrence -SAT. It is natural to ask how much of this abstract optimality is visible in concrete combinatorial problems.
In this paper, we prove that the symmetric LLL bound is asymptotically optimal for the hat guessing number of bounded-degree graphs. The hat guessing number is a graph-theoretic generalization of a famous hat guessing puzzle [1, 4]. All graphs considered in this paper are finite and simple. Let be a graph, and suppose that each vertex is assigned a color from . Each vertex sees the colors assigned to its neighbors and, according to a previously fixed deterministic strategy, tries to guess its own color. The hat guessing number is the largest for which there is a strategy that guarantees that at least one vertex guesses correctly for every coloring. Note that the strategy is fixed in advance for all the vertices with complete knowledge of the graph. Applying the LLL to bound the hat guessing number of a bounded-degree graph is straightforward. Fix a strategy for the vertices, and assign each vertex a hat color independently and uniformly at random from . The event that vertex guesses correctly has probability , even conditional on all hat colors other than the one at . Since the events with are determined by those other colors, is independent of the family of all such events. Thus, is a dependency graph for . For , the symmetric Local Lemma therefore implies that if , then with positive probability no vertex guesses correctly. Consequently, every graph of maximum degree at most satisfies
For , each component has at most two vertices, giving . Thus the bound holds for all . This standard argument was previously observed by Farnik [7].
Several papers have studied the extremal hat guessing number of bounded-degree graphs [1, 3, 9]. In particular, it was conjectured in [3, 9] that . Latyshev and Kokhas later disproved this conjecture by constructing a family of graphs with and unbounded maximum degree [13]. In response, the journal version of [3] replaced the original conjecture by . More recently, Shurman and Sibley [17] obtained upper bounds depending jointly on the order and maximum degree of the graph, improving the trivial bound in the regime where the LLL bound is insufficient. Here, we show that the constant in the Local Lemma bound is asymptotically sharp.
Theorem 1. For every and every sufficiently large , there exists a graph of maximum degree at most such that
Our construction relies on a generalized hat game in which vertices may have different numbers of available colors. We define a hat game as a pair in which is a graph and is a function giving the number of colors available at each vertex. We call the hatness function of the game, and is the hatness of . Without loss of generality, we always assume that the colors available at vertex are . We say that a game is winning if there exists a strategy such that for every coloring assigning to each vertex a color from , at least one vertex guesses correctly. Decreasing any hatness to a positive integer preserves winnability: restrict the strategy to the remaining colors and replace any guess outside the new color set by an arbitrary permitted color. We build winning games by composing smaller winning games and, although the final game can be reduced to uniform hatness, the intermediate games have a small clique of “bad” vertices with lower hatness. The construction is guided by a careful analysis of how the maximum degree and the hatness of the bad clique evolve under the composition operations. A clique-join operation preserves winnability and multiplies the hatness on the interface. Generalized hat games and related join operations have previously been used to construct winning games with specific properties [2, 11, 12, 13, 14]. By iterating these operations, we keep the number and hatness of the distinguished vertices fixed while controlling their degrees and those of their neighbors. At the final step, the bad clique disappears, leaving a winning game in which all vertices have hatness at least and the graph has maximum degree at most . We note that our proof does not merely establish existence: it is constructive throughout, and every step can be carried out explicitly.
The constant appears in the analysis of the degree growth. Ignoring lower-order errors, the key quantity in the construction behaves like
The largest intermediate degree term is governed by
since the function is maximized at with value .
The paper is organized as follows. In Section 2, we provide hat game constructors and operators that preserve winnability. In Section 3, we describe how we track the degrees and hatnesses of the distinguished vertices and their neighbors under these operations. Finally, in Section 4, we use the operations as black boxes and track only their numerical parameters to reach the desired quantities. For this purpose, we first give an informal description of the construction and then prove the lemmas used to implement it. The whole construction is then analyzed in the proof of Theorem 18.
Constructors
In this section, we recall useful lemmas from the literature, together with some of their generalizations. These lemmas will help us analyze the construction presented in Section 4. The notion of the join of two games will be the basic operation of our construction. It was first introduced for a pair of vertices in [11] and was generalized to a vertex and a clique in [2]. It was also used in [13] to construct a graph with .
Definition 2. Let and be two games on disjoint vertex sets. Let be a set of vertices that induce a clique, and let . We define the join of and with respect to and , denoted , to be the game where
is the graph such that
, and
.
is defined by
Intuitively, is obtained by replacing in with the clique in . More precisely, takes disjoint copies of and , deletes , and finally connects every former neighbor of in to every vertex of . Figure 1 illustrates this operation. The hatness function is chosen so that the join of two winning games is also winning.
Figure 1. The effect of joining two games on their underlying graphs.
Lemma 3 (Blažej et al. [2], 2023). Let , be two winning games, be a clique, and . Then the game is also winning.
We generalize this notion further by defining the join on two cliques as follows.
Definition 4. Let and be two games on disjoint vertex sets, and let and be cliques. Whenever a game is used repeatedly, disjoint copies are understood. We define the clique-join of two games and with respect to and , denoted , inductively on the size of :
If , then .
If with , then, using a fresh disjoint copy of and its clique , we set .
In Definition 4, the inductive step decomposes as for an arbitrary vertex . A priori, the result might depend on the order in which the vertices of are processed. We show that the order of the joins does not affect the result up to isomorphism, and hence that the clique-join is well-defined, by giving an equivalent description of the operation.
To do so, we describe the hat game . The graph consists of copies of and one copy of . Thus,
The graph contains all the edges within each copy of and within . It also contains an edge between every two distinct vertices of , and an edge between and whenever , , , and . This gives
The hatness function is given by
This description is independent of the ordering of , so the clique-join is well-defined up to isomorphism. Figure 2 illustrates the operation. In , each vertex of has been replaced, and there are copies of each vertex of . In fact, the vertices corresponding to copies of form the clique with vertex set , and we call this set of vertices the resulting clique of the clique-join .
Figure 2. An illustration of the graphs in the clique-join of two games.
Remark 5. The resulting clique of the clique-join is of order .
Additionally, we will abuse notation by writing to denote the graph of the game , and to denote the hatness function of the game .
The notion of clique-joins generalizes the notion of joins of games of Blažej et al. from [2] since the two notions coincide whenever is a singleton. The underlying graph operation can also be defined for arbitrary vertex subsets. Here, the clique assumptions ensure that the resulting set is a clique and allow us to preserve winnability. The clique-join is defined inductively, with each step consisting of a join of two games. Hence, Lemma 3 and induction on show that clique-joins preserve winnability.
Lemma 6. Let , be two winning hat games and let , be two cliques. Then is a winning hat game.
In addition to clique-joins of hat games, we will use the following notion of powers of hat games. Figure 3 illustrates the first powers of a hat game.
Figure 3. An illustration of the action of the power of a game on its graph. The red boxes represent the distinguished clique in . Some edges within these cliques are omitted for readability.
Definition 7. Given a hat game and a set of vertices of such that is a clique, we define the -th power of with respect to , denoted , as follows:
.
.
For all , let be the resulting clique from the last clique-join in the construction of . Then .
We will abuse notation by writing to denote the graph of the game and to denote the hatness function of . Like clique-joins, powers of hat games are defined inductively and each step is a clique-join. By induction using Lemma 6, every positive integer power of a winning hat game is winning.
Lemma 8. For any winning hat game , any set inducing a clique in , and for every integer , the hat game is winning.
Lemma 6 and Lemma 8 allow us to combine winning games in order to produce new winning games. The following lemma from [11] characterizes winning games on cliques, which provide the building blocks for our construction.
Lemma 9 (Kokhas and Latyshev [11]). The hat game is winning if and only if
Tracking the bad vertices
In order to analyze how winning games evolve under the previous constructors, we need lemmas tracking the degrees and hatnesses of distinguished vertices and their neighbors. Throughout the construction, all but a few vertices will have hatness at least a prescribed target. We use the following terminology for the remaining vertices.
Definition 10. Let be a hat game and let be a positive integer. We define the set of -bad vertices of as .
We then give the following definition that consists in a tuple of quantities allowing us to track the degree and hatness of -bad vertices and their neighbors. An illustration of the following quantities is given in Figure 4.
Figure 4. A game with property and distinguished set . The vertices and are neighbors and the vertices and are not neighbors.
Definition 11. We say that a hat game has property
if and only if is winning and there exists a distinguished set of order , inducing a clique in , and such that
for all , and ;
for all , ;
for all , , and
and .
We allow . Notice that in Definition 11,
Throughout the remainder of this article, we analyze this property for clique-joins and powers of winning hat games. By Lemmas 6 and 8, these operations preserve winnability. We therefore invoke these lemmas implicitly whenever we form a clique-join or a power, and only verify the remaining conditions of the property. Finally, if is clear from context, then we might refer to the set of -bad vertices of as the set of bad vertices of .
The following lemma describes the hatness of the vertices from the resulting clique of the product of two hat games with a fixed property, and shows that in this specific context, the notion of resulting clique and -bad vertices coincide (whenever ).
Lemma 12. Let and be hat games with properties and , and distinguished sets and respectively. Then the resulting clique of is of order , every vertex of has hatness , and every vertex outside has hatness at least .
Proof. By Remark 5, . A vertex has hatness . Every vertex outside is either a copy of a vertex of or a vertex of , and its hatness is unchanged. In either case, it is at least .
Consequently, whenever , is the set of -bad vertices of and there are no -bad vertices otherwise. The following two lemmas describe the evolution of property under clique-joins and clique-join powers.
Lemma 13. Let and be hat games with properties and , and with distinguished sets and respectively. If , then the hat game has property with
,
,
,
, and
.
Additionally, the resulting clique of is the distinguished set witnessing the property.
Proof. Let be the resulting clique of . For 1) and 2), we can apply Lemma 12. We thus only need to prove the remaining items.
Let . The vertices and have at most and neighbors outside and , respectively. Thus has at most neighbors outside , and exactly neighbors inside . Therefore .
Let be a vertex in . If belongs to a copy of , then its corresponding vertex belongs to . Its degree is unchanged, and hence is at most . If comes from , then let
We thus have
Moreover, . Therefore,
since by hypothesis, .
If a vertex of does not belong to , then it is of degree at most . Therefore the maximum degree of is at most by definition of and .
This proves the lemma.
Lemma 14. Let be a hat game with property with and distinguished set . Then for every integer , the hat game has property with
,
,
,
, and
.
Additionally, the distinguished set witnessing this property is when , and the resulting clique of the last clique-join when .
Proof. We proceed by induction on . For , the game is , and the formulas give , , , , and , since . Assume that the statement holds for some integer and prove it for . If we let , and otherwise we let be the resulting clique of the last clique-join in the construction of . By the induction hypothesis, has property
with distinguished set . Moreover, by the definition of powers,
Therefore, we can apply Lemma 13 to obtain that has property
with
,
,
,
, and
, since each term of the internal maximum is dominated by the corresponding term of the external maximum.
Moreover, by Lemma 13, the resulting clique of witnesses the property as desired.
The construction: description and analysis
Informal description of the construction
Our goal is to construct a winning hat game such that has maximum degree at most and for every vertex of , . In this informal description, we implicitly reduce any larger hatness to , which preserves winnability.
The construction starts with the following observation. For every integer , we can apply Lemma 9 to construct a winning game such that is a complete graph of order , with a set of distinguished vertices and such that
For sufficiently large and sufficiently large compared with , the maximum degree is small compared with . Moreover, the proportion of distinguished vertices is , which is small when is large compared with . If the degrees of the vertices in were sufficiently small, we could finish by taking a clique-join of and a suitable winning game on a clique. We will use Lemma 15 to reduce the degree bound on the distinguished vertices while keeping their number and hatness fixed. Suppose that we have constructed a winning hat game with a set of vertices such that
Then, with the right parameters, Lemma 15 constructs a winning hat game with a set of vertices such that
and a smaller degree bound on the vertices in than on those in . Repeating the construction with suitable parameters allows us to obtain a winning hat game in which the distinguished vertices have sufficiently small degrees for the final step. The repeated construction is formalized in Lemma 16, and the final clique-join with a winning game on a clique is described in Lemma 17.
Formal construction
The whole construction is defined by Lemmas 15, 16, and 17. Figure 5 illustrates the construction in Lemma 15.
Figure 5. Illustration of the construction from Lemma 15 with parameters , and a hat game with distinguished set . First, we construct the -th power , with distinguished set . We then take its clique-join with the game , where is a clique. For every vertex , we replace by a clique on vertices and attach a fresh copy of by identifying its distinguished vertices with the vertices .
Lemma 15. Let and suppose there exists a hat game with property
Then for all integers and such that , there exists a hat game with property
with
and
Proof. Let be a hat game with property and distinguished set as in the statement. Fix and as in the statement. By
Lemma 14. is a hat game with property .
Let be the set of vertices witnessing this property. Consider now the hat game where is the complete graph of order
with a set of vertices of such that for every , if then and if then . By Lemma 9, is winning since
where the inequality comes from the fact that for every real number and positive integer , . So has property
with distinguished set , and where . We can finally construct the hat game
The set of vertices of corresponding to is the new set of distinguished vertices. By construction, and for every vertex , , and has degree at most
For every vertex , is a copy of a vertex of . If is a copy of a vertex not in , then so . In this case, no neighbor of is in . Otherwise, is a copy of a vertex in and therefore in which case .
Every neighbor of is in this second case, and has degree at most
as needed.
has maximum degree at most
using the fact that by definition and .
We have verified that has property
with the distinguished set , as desired.
Lemma 16. For every nonnegative integer and all positive integers , there exists a hat game with property
with
and
where
Proof. Let be the clique of size , let be a subset of of size , and let be the function such that for all and for all . By Lemma 9, the hat game is winning since
Hence, the hat game has property with . We now proceed by induction on . Suppose there exists a hat game with property
where
and
Applying Lemma 15 to with and exponent , we obtain a hat game with property
with
and
Now let
So in particular has maximum degree at most , and has property
as desired.
To interpret Lemma 16 asymptotically, suppose , , and . Since and the rounding error in is , we obtain . The graph in Lemma 16 has distinguished vertices, all of hatness . The degree bounds for these vertices and their neighbors are respectively of order and ; the global maximum-degree bound is tracked separately.
We now provide the last step of the construction.
Lemma 17. For all positive integers with , there exists a hat game with property
such that
and
and
where
Proof. Let be the hat game with property
constructed by Lemma 16 using , and . In particular,
and
We can thus apply Lemma 15 with the hat game and parameters and in order to construct a hat game with property
where
and
as desired.
The game from Lemma 17 has no vertex of hatness less than , so it remains to verify that for any there is a choice of parameters such that the maximum degree of the graph is at most
Theorem 18. For every and for every sufficiently large integer (depending only on ), there exists a winning hat game such that, for every vertex , and .
Proof. Fix and let
For , we apply Lemma 17 with parameters , and . It produces a winning hat game in which every vertex has hatness at least , and such that
where
with
We show that each of these bounds is at most when is sufficiently large.
By hypothesis, , that is, so and . By comparing with the last term of the maximum in we get . So it is enough to bound and .
Using the classical inequality for every , we have
This implies for all ,
where the case is trivial. Applying (1) to the first term of , followed by (2), we get
where the last inequality follows from the choice of . This implies the desired as soon as .
To bound , set . By (2), for every integer (with checked directly),
Viewing as a function of a nonnegative real variable, differentiation shows that it is maximized at . Thus,
The penultimate inequality follows from (1). For the last one, the choice of gives . Finally, we get
which implies the desired as soon as .
Combining the thresholds, it suffices to require
Since and depend only on , so does this threshold which concludes the proof.
To deduce Theorem 1, assume , put , and let . For sufficiently large , Theorem 18 with parameter gives a winning game of maximum degree at most and hatness at least at every vertex. Reducing all hatnesses to preserves winnability. Since , we obtain for sufficiently large .
Experiments leading to the construction
We now describe the computer-assisted experimentation that led to the construction. Our initial goal was to refine the construction of [13] and improve the ratio . More precisely, we sought to iterate a construction in which most vertices have the desired hatness , the graph has maximum degree , and a small distinguished clique has lower hatness. It was not clear that the constant was attainable. The first step was to generalize the join of two games from [2] to the clique-join in Definition 4.
We first constructed and analyzed examples obtained by applying clique-joins to winning games on cliques. We quickly found a construction that appeared to improve the ratio from [13], but the computations and graph drawings became tedious. We therefore wrote a small interactive program to approximate the evolution of the relevant parameters.
The program first took the initial values of and as input. Ignoring integer rounding, it represented the starting clique game by a tuple of parameters: vertices had hatness , and vertices had hatness (which corresponds to a winning game by Lemma 9). At each subsequent step, the program displayed the tuple and asked which operation to apply next, with the option of undoing the previous operation. It then updated the tuple according to heuristic rules intended to approximate the effect of that operation. These were numerical approximations rather than certified calculations, and we assumed that taking sufficiently large would make the approximation errors negligible. The parameters ultimately led to the property in Definition 11, and the update rules were formalized in Lemma 13.
Using this tool, we quickly found a candidate construction that appeared to achieve . The observation that then guided us toward a construction resembling the one presented in this paper. In particular, this motivated the notion of a power of a game from Definition 7. However, our initial approximations overlooked the fact that the degrees of the neighbors of the bad vertices could continue to grow. As a result, our first versions of the construction were not quite correct, although this issue could be fixed. Finally, while writing up the proof, we noticed that the construction could be substantially simplified, leading to its present form. In particular, an intermediate version involved many additional steps after Lemma 16, instead of the single final step given in Lemma 17.
Conclusion
We have shown that the bound obtained from the Lovász Local Lemma is asymptotically tight, even for chordal graphs. Indeed, our construction starts from cliques and uses operations that preserve chordality. Moreover, the resulting graphs contain cliques of order . Since the treewidth of a chordal graph equals its maximum clique size minus one, our construction also satisfies . This leaves open the question, raised in [3], of whether the hat guessing number can be bounded in terms of treewidth alone.
Question 19. Does there exist a function such that every graph of treewidth satisfies ?
He and Li [10] constructed graphs of pathwidth with hat guessing number , where is Sylvester’s sequence, defined by and . Thus, if such a function exists, it must grow at least doubly exponentially.
Finally, the chordality of our construction suggests a possible connection with the Lefthanded Local Lemma. Pegden [15] proved that, for chordal dependent dency graphs, Shearer’s condition is equivalent to the Lefthanded Local Lemma. Since itself is a valid dependency graph for the events used in the LLL upper bound on , it would be interesting to investigate whether this characterization could lead to a more direct construction of asymptotically extremal hat games.
Declaration of AI assistance
Large language models (OpenAI’s ChatGPT, GPT-6, and Anthropic’s Claude, Claude Opus 5.5) were used during the final proofreading of this manuscript, to improve the English, identify typographical errors, check calculations, and suggest improvements to the \LaTeX typesetting. Then authors reviewed all suggested changes and take full responsibility for the manuscript. These tools were not used to develop the mathematical results, constructions, or proofs.
References
- [1]Noga Alon, Omri Ben-Eliezer, Chong Shangguan, and Itzhak Tamo. The hat guessing number of graphs. Journal of Combinatorial Theory, Series B, 144:119–149, 2020.arxiv.org/abs/1812.09752
- [2]Václav Blažej, Pavel Dvořák, and Michal Opler. Bears with hats and independence polynomials. Discrete Mathematics & Theoretical Computer Science, 25(2), 2023.
- [3]Bartłomiej Bosek, Andrzej Dudek, Michał Farnik, Jarosław Grytczuk, and Przemysław Mazur. Hat chromatic number of graphs. Discrete Mathematics, 344(12):112620, 2021.arxiv.org/abs/1905.04108
- [4]Steve Butler, Mohammad T. Hajiaghayi, Robert D. Kleinberg, and Tom Leighton. Hat guessing games. SIAM Journal on Discrete Mathematics, 22(2):592–605, 2008.
- [5]Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, Vol. II, volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 609–627. North-Holland, Amsterdam, 1975.
- [6]Paul Erdős and Joel Spencer. Lopsided Lovász Local Lemma and Latin transversals. Discrete Applied Mathematics, 30(2):151–154, 1991.DOI
- [7]Michal Farnik. A hat guessing game. PhD thesis, Jagiellonian University, 2015.
- [8]Heidi Gebauer, Tibor Szabó, and Gábor Tardos. The Local Lemma is asymptotically tight for SAT. Journal of the ACM, 63(5):43, 2016.arxiv.org/abs/1006.0744
- [9]Xiaoyu He, Yuzu Ido, and Benjamin Przybocki. Hat guessing on books and windmills. The Electronic Journal of Combinatorics, 29(1):P1.12, Jan. 2022.arxiv.org/abs/2010.13249
- [10]Xiaoyu He and Ray Li. Hat guessing numbers of degenerate graphs. The Electronic Journal of Combinatorics, 27(3):P3.58, September 2020.arxiv.org/abs/2003.04990
- [11]Konstantin Kokhas and Aleksei Latyshev. Cliques and constructors in “hats” game. I. Journal of Mathematical Sciences, 255(1):39–57, 2021.DOI
- [12]Konstantin Kokhas, Aleksei Latyshev, and V. I. Retinskiy. Cliques and constructors in “hats” game. II. Journal of Mathematical Sciences, 255(1):58–70, 2021.DOI
- [13]Aleksei Latyshev and Konstantin Kokhas. The Hats game. On maximum degree and diameter. Discrete Mathematics, 345(7):112868, 2022.DOI
- [14]Aleksei Latyshev and Konstantin Kokhas. Hat guessing number for the class of planar graphs is at least 22. Discrete Mathematics, 347(3):113820, 2024.DOI
- [15]Wesley Pegden. The Lefthanded Local Lemma characterizes chordal dependency graphs. Random Structures & Algorithms, 41(4):546–556, 2012.arxiv.org/abs/1204.5922
- [16]James B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241–245, 1985.DOI
- [17]Mason Shurman and Scott Albert Sibley. An upper bound on the hat guessing number of graphs, 2026.arxiv.org/abs/2607.07994




