betaFeedback

WorksMathematics

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

Abstract

In the hat guessing game on a graph GG, each vertex is occupied by a player wearing a hat whose color is chosen from a set of qq 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 GG, denoted by HG(G)\textrm{HG}(G), is the largest integer qq 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 HG(G)<eΔ\textrm{HG}(G) < eΔ for every graph GG of maximum degree at most Δ≥1Δ\ge 1. We prove that this bound is asymptotically sharp: for every ε>0\varepsilon > 0 and every sufficiently large ΔΔ, there exists a graph GG of maximum degree at most ΔΔ with HG(G)≥(e−ε)Δ\textrm{HG}(G) \ge (e - \varepsilon)Δ. This answers a question of Alon et al., disproves the conjecture HG(G)≤2Δ(G)\textrm{HG}(G) \le 2Δ(G) of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves HG(G)=4Δ(G)/3\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.

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 pp with a dependency graph of maximum degree at most D≥2D \ge2, can be simultaneously avoided provided1 epD≤1e p D \le1. 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 kk-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 GG be a graph, and suppose that each vertex is assigned a color from [q]:={1,…,q}[q] := \{1, \ldots, q\}. 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 HG⁡(G)\operatorname{HG}(G) is the largest qq 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 [q][q]. The event AvA_v that vertex vv guesses correctly has probability 1/q1/q, even conditional on all hat colors other than the one at vv. Since the events AwA_w with w∉NG(v)∪{v}w \notin N_G(v) \cup\{v\} are determined by those other colors, AvA_v is independent of the family of all such events. Thus, GG is a dependency graph for (Av)v∈V(G)(A_v)_{v \in V(G)}. For Δ≥2\Delta\ge2, the symmetric Local Lemma therefore implies that if q≥eΔq \ge e\Delta, then with positive probability no vertex guesses correctly. Consequently, every graph GG of maximum degree at most Δ≥2\Delta\ge2 satisfies

HG⁡(G)<eΔ.\operatorname{HG}(G) < e\Delta.

For Δ=1\Delta= 1, each component has at most two vertices, giving HG⁡(G)≤2<e\operatorname{HG}(G) \le2 < e. Thus the bound holds for all Δ≥1\Delta\ge1. 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 HG⁡(G)≤Δ(G)+1\operatorname{HG}(G) \le\Delta(G) + 1. Latyshev and Kokhas later disproved this conjecture by constructing a family of graphs GG with HG⁡(G)=43Δ(G)\operatorname{HG}(G) = \frac{4}{3}\Delta(G) and unbounded maximum degree [13]. In response, the journal version of [3] replaced the original conjecture by HG⁡(G)≤2Δ(G)\operatorname{HG}(G) \le2\Delta(G). 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 ee in the Local Lemma bound is asymptotically sharp.

Theorem 1. For every ε>0\varepsilon> 0 and every sufficiently large Δ\Delta, there exists a graph GG of maximum degree at most Δ\Delta such that

HG⁡(G)≥(e−ε)Δ.\operatorname{HG}(G) \ge(e - \varepsilon)\Delta.

Our construction relies on a generalized hat game in which vertices may have different numbers of available colors. We define a hat game G=(G,h)\mathcal{G}=(G,h) as a pair in which GG is a graph and h:V(G)→Nh:V(G)\to\mathbb{N} is a function giving the number of colors available at each vertex. We call hh the hatness function of the game, and h(v)h(v) is the hatness of vv. Without loss of generality, we always assume that the colors available at vertex vv are [h(v)][h(v)]. We say that a game is winning if there exists a strategy such that for every coloring assigning to each vertex vv a color from [h(v)][h(v)], 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 ℓ^\hat{\ell} and the graph has maximum degree at most (1/e+ε)ℓ^(1/e+\varepsilon)\hat{\ell}. We note that our proof does not merely establish existence: it is constructive throughout, and every step can be carried out explicitly.

The constant ee appears in the analysis of the degree growth. Ignoring lower-order errors, the key quantity in the construction behaves like

f(k,i)≈ℓ^kexp⁡(−i/k).f(k,i)\approx\frac{\hat{\ell}}{k}\exp(-i/k).

The largest intermediate degree term is governed by

i⋅f(k,i−1)≈ℓ^ike−i/k≤ℓ^e,i\cdot f(k,i-1)\approx\hat{\ell}\frac{i}{k}e^{-i/k}\le\frac{\hat{\ell}}{e},

since the function te−tte^{-t} is maximized at t=1t=1 with value 1/e1/e.

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 HG⁡(G)=4Δ/3\operatorname{HG}(G)=4\Delta/3.

Definition 2. Let G1=(G1,h1)\mathcal{G}_1=(G_1,h_1) and G2=(G2,h2)\mathcal{G}_2=(G_2,h_2) be two games on disjoint vertex sets. Let S⊆V(G1)S\subseteq V(G_1) be a set of vertices that induce a clique, and let v∈V(G2)v\in V(G_2). We define the join of G1\mathcal{G}_1 and G2\mathcal{G}_2 with respect to SS and vv, denoted G1+S,vG2\mathcal{G}_1+_{S,v}\mathcal{G}_2, to be the game G=(G,h)\mathcal{G}=(G,h) where

  • GG is the graph such that

    • V(G)=V(G1)∪(V(G2)∖{v})V(G)=V(G_1)\cup(V(G_2)\setminus\{v\}), and

    • E(G)=E(G1)∪{e∈E(G2)∣v∉e}∪{uu′∣u∈S and u′∈NG2(v)}E(G)=E(G_1)\cup\{e\in E(G_2)\mid v\notin e\}\cup\{uu'\mid u\in S\text{ and }u'\in N_{G_2}(v)\}.

  • h:V(G)→Nh:V(G)\to\mathbb{N} is defined by

h(u)={h1(u)if u∈V(G1)∖S,h2(u)if u∈V(G2)∖{v},h1(u)h2(v)if u∈S.h(u)= \begin{cases} h_1(u) & \text{if }u\in V(G_1)\setminus S,\\ h_2(u) & \text{if }u\in V(G_2)\setminus\{v\},\\ h_1(u)h_2(v) & \text{if }u\in S. \end{cases}

Intuitively, G1+S,vG2\mathcal{G}_1+_{S,v}\mathcal{G}_2 is obtained by replacing vv in G2G_2 with the clique SS in G1G_1. More precisely, G1+S,vG2\mathcal{G}_1+_{S,v}\mathcal{G}_2 takes disjoint copies of G1G_1 and G2G_2, deletes vv, and finally connects every former neighbor of vv in G2G_2 to every vertex of SS. Figure 1 illustrates this operation. The hatness function hh 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 G1=(G1,h1)\mathcal{G}_1=(G_1,h_1), G2=(G2,h2)\mathcal{G}_2=(G_2,h_2) be two winning games, S⊆V(G1)S\subseteq V(G_1) be a clique, and v∈V(G2)v\in V(G_2). Then the game G=G1+S,vG2\mathcal{G}=\mathcal{G}_1+_{S,v}\mathcal{G}_2 is also winning.

We generalize this notion further by defining the join on two cliques as follows.

Definition 4. Let G1=(G1,h1)\mathcal{G}_1=(G_1,h_1) and G2=(G2,h2)\mathcal{G}_2=(G_2,h_2) be two games on disjoint vertex sets, and let S1⊆V(G1)S_1\subseteq V(G_1) and S2⊆V(G2)S_2\subseteq V(G_2) be cliques. Whenever a game is used repeatedly, disjoint copies are understood. We define the clique-join of two games G1\mathcal{G}_1 and G2\mathcal{G}_2 with respect to S1S_1 and S2S_2, denoted G1⊕S1,S2G2\mathcal{G}_1\oplus_{S_1,S_2}\mathcal{G}_2, inductively on the size of S2S_2:

  • If S2=∅S_2=\varnothing, then G1⊕S1,S2G2=G2G_1\oplus_{S_1,S_2}G_2=G_2.

  • If S2=S2′∪{v}S_2=S'_2\cup\{v\} with v∉S2′v\notin S'_2, then, using a fresh disjoint copy of G1G_1 and its clique S1S_1, we set G1⊕S1,S2G2=G1+S1,v(G1⊕S1,S2′G2)G_1\oplus_{S_1,S_2}G_2=G_1+_{S_1,v}(G_1\oplus_{S_1,S'_2}G_2).

In Definition 4, the inductive step decomposes S2S_2 as S2′∪{v}S'_2\cup\{v\} for an arbitrary vertex v∈S2v\in S_2. A priori, the result might depend on the order in which the vertices of S2S_2 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 (G,h)=G1⊕S1,S2G2(G,h)=G_1\oplus_{S_1,S_2}G_2. The graph GG consists of ∣S2∣|S_2| copies of G1G_1 and one copy of G2−S2G_2-S_2. Thus,

V(G)=(V(G2)∖S2)∪{(v,u)∣v∈V(G1) and u∈S2}.V(G)=(V(G_2)\setminus S_2)\cup\{(v,u)\mid v\in V(G_1)\text{ and }u\in S_2\}.

The graph GG contains all the edges within each copy of G1G_1 and within G2−S2G_2-S_2. It also contains an edge between every two distinct vertices of S1×S2S_1\times S_2, and an edge between (v,u)(v,u) and ww whenever v∈S1v\in S_1, u∈S2u\in S_2, w∈V(G2−S2)w\in V(G_2-S_2), and uw∈E(G2)uw\in E(G_2). This gives

E(G)={{(v,u),(v′,u)}∣vv′∈E(G1) and u∈S2}∪E(G2−S2)∪{{(v,u),(v′,u′)}∣v,v′∈S1 and u,u′∈S2, (v,u)≠(v′,u′)}∪{{(v,u),w}∣v∈S1, u∈S2, w∈V(G2−S2) and uw∈E(G2)}.\begin{aligned} E(G)={}&\{ \{(v,u),(v',u)\}\mid vv'\in E(G_1)\text{ and }u\in S_2\}\\ &\cup E(G_2-S_2)\\ &\cup\{ \{(v,u),(v',u')\}\mid v,v'\in S_1\text{ and }u,u'\in S_2,\ (v,u)\ne(v',u')\}\\ &\cup\{ \{(v,u),w\}\mid v\in S_1,\ u\in S_2,\ w\in V(G_2-S_2)\text{ and }uw\in E(G_2)\}. \end{aligned}

The hatness function hh is given by

h((v,u))=h1(v)if v∈V(G1−S1) and u∈S2h((v,u))=h1(v)h2(u)if v∈S1 and u∈S2h(v)=h2(v)if v∈V(G2−S2).\begin{aligned} h((v,u))&=h_1(v) &&\text{if }v\in V(G_1-S_1)\text{ and }u\in S_2\\ h((v,u))&=h_1(v)h_2(u) &&\text{if }v\in S_1\text{ and }u\in S_2\\ h(v)&=h_2(v) &&\text{if }v\in V(G_2-S_2). \end{aligned}

This description is independent of the ordering of S2S_2, so the clique-join is well-defined up to isomorphism. Figure 2 illustrates the operation. In G1⊕S1,S2G2G_1\oplus_{S_1,S_2}G_2, each vertex of S2S_2 has been replaced, and there are ∣S2∣|S_2| copies of each vertex of S1S_1. In fact, the vertices corresponding to copies of S1S_1 form the clique with vertex set S1×S2S_1\times S_2, and we call this set of vertices the resulting clique of the clique-join G1⊕S1,S2G2G_1\oplus_{S_1,S_2}G_2.

Figure 2. An illustration of the graphs in the clique-join of two games.

Remark 5. The resulting clique of the clique-join G1⊕S1,S2G2G_1\oplus_{S_1,S_2}G_2 is of order ∣S1∣⋅∣S2∣|S_1|\cdot|S_2|.

Additionally, we will abuse notation by writing G1⊕S1,S2G2G_1\oplus_{S_1,S_2}G_2 to denote the graph of the game G1⊕S1,S2G2G_1\oplus_{S_1,S_2}G_2, and h1⊕S1,S2h2h_1\oplus_{S_1,S_2}h_2 to denote the hatness function of the game G1⊕S1,S2G2G_1\oplus_{S_1,S_2}G_2.

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 S2S_2 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 ∣S2∣|S_2| show that clique-joins preserve winnability.

Lemma 6. Let G1=(G1,h1)\mathcal{G}_1=(G_1,h_1), G2=(G2,h2)\mathcal{G}_2=(G_2,h_2) be two winning hat games and let S1⊆V(G1)S_1\subseteq V(G_1), S2⊆V(G2)S_2\subseteq V(G_2) be two cliques. Then G1⊕S1,S2G2\mathcal{G}_1\oplus_{S_1,S_2}\mathcal{G}_2 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 G⊕S(i)\mathcal{G}^{\oplus S(i)}. Some edges within these cliques are omitted for readability.

Definition 7. Given a hat game G=(G,h)\mathcal{G}=(G,h) and a set SS of vertices of GG such that G[S]G[S] is a clique, we define the ii-th power of G\mathcal{G} with respect to SS, denoted G⊕S(i)\mathcal{G}^{\oplus S(i)}, as follows:

  • G⊕S(1)=G\mathcal{G}^{\oplus S(1)}=\mathcal{G}.

  • G⊕S(2)=G⊕S,SG\mathcal{G}^{\oplus S(2)}=\mathcal{G}\oplus_{S,S}\mathcal{G}.

  • For all i>2i>2, let S′S' be the resulting clique from the last clique-join in the construction of G⊕S(i−1)\mathcal{G}^{\oplus S(i-1)}. Then G⊕S(i)=G⊕S,S′G⊕S(i−1)\mathcal{G}^{\oplus S(i)}=\mathcal{G}\oplus_{S,S'}\mathcal{G}^{\oplus S(i-1)}.

We will abuse notation by writing G⊕S(i)G^{\oplus S(i)} to denote the graph of the game G⊕S(i)\mathcal{G}^{\oplus S(i)} and h⊕S(i)h^{\oplus S(i)} to denote the hatness function of G⊕S(i)\mathcal{G}^{\oplus S(i)}. 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 G=(G,h)\mathcal{G}=(G,h), any set SS inducing a clique in GG, and for every integer i≥1i\ge1, the hat game G⊕S(i)\mathcal{G}^{\oplus S(i)} 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 (Kn,h)(K_n,h) is winning if and only if

∑v1h(v)≥1.\sum_v \frac{1}{h(v)} \ge1.

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 G=(G,h)\mathcal{G}=(G,h) be a hat game and let ℓ^\hat{\ell} be a positive integer. We define the set of ℓ^\hat{\ell}-bad vertices of G\mathcal{G} as {v∈V(G)∣h(v)<ℓ^}\{v\in V(G)\mid h(v)<\hat{\ell}\}.

We then give the following definition that consists in a tuple of quantities allowing us to track the degree and hatness of ℓ^\hat{\ell}-bad vertices and their neighbors. An illustration of the following quantities is given in Figure 4.

Figure 4. A game G=(G,h)\mathcal{G}=(G,h) with property (ℓ^,ℓ,k,d,d~,D)(\hat{\ell},\ell,k,d,\tilde{d},D) and distinguished set BB. The vertices uu and vv are neighbors and the vertices uu and ww are not neighbors.

Definition 11. We say that a hat game G=(G,h)\mathcal{G}=(G,h) has property

(ℓ^,ℓ,k,d,d~,D)(\hat{\ell},\ell,k,d,\tilde{d},D)

if and only if G\mathcal{G} is winning and there exists a distinguished set B⊆V(G)B\subseteq V(G) of order kk, inducing a clique in GG, and such that

  • for all v∈Bv\in B, h(v)=ℓh(v)=\ell and deg⁡(v)≤d\deg(v)\le d;

  • for all v∉Bv\notin B, h(v)≥ℓ^h(v)\ge\hat{\ell};

  • for all v∈N(B)∖Bv\in N(B)\setminus B, deg⁡(v)≤d~\deg(v)\le\tilde{d}, and

  • Δ(G)≤D\Delta(G)\le D and D≥max⁡{d,d~}D\ge\max\{d,\tilde{d}\}.

We allow B=∅B=\varnothing. Notice that in Definition 11,

{v∈V(G)∣h(v)<ℓ^}={Bif ℓ<ℓ^,∅if ℓ≥ℓ^.\{v\in V(G)\mid h(v)<\hat{\ell}\}= \begin{cases} B & \text{if }\ell<\hat{\ell},\\ \varnothing& \text{if }\ell\ge\hat{\ell}. \end{cases}

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 ℓ^\hat{\ell} is clear from context, then we might refer to the set of ℓ^\hat{\ell}-bad vertices of G\mathcal{G} as the set of bad vertices of G\mathcal{G}.

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 ℓ^\hat{\ell}-bad vertices coincide (whenever ℓ1ℓ2<ℓ^\ell_1\ell_2<\hat{\ell}).

Lemma 12. Let G1=(G1,h1)\mathcal{G}_1=(G_1,h_1) and G2=(G2,h2)\mathcal{G}_2=(G_2,h_2) be hat games with properties (ℓ^,ℓ1,k1,d1,d~1,D1)(\hat{\ell},\ell_1,k_1,d_1,\tilde{d}_1,D_1) and (ℓ^,ℓ2,k2,d2,d~2,D2)(\hat{\ell},\ell_2,k_2,d_2,\tilde{d}_2,D_2), and distinguished sets B1B_1 and B2B_2 respectively. Then the resulting clique BB of G:=G1⊕B1,B2G2=(G,h)\mathcal{G}:=\mathcal{G}_1\oplus_{B_1,B_2}\mathcal{G}_2=(G,h) is of order k1k2k_1k_2, every vertex of BB has hatness ℓ1ℓ2\ell_1\ell_2, and every vertex outside BB has hatness at least ℓ^\hat{\ell}.

Proof. By Remark 5, ∣B∣=k1k2|B|=k_1k_2. A vertex (u1,u2)∈B=B1×B2(u_1,u_2)\in B=B_1\times B_2 has hatness h1(u1)h2(u2)=ℓ1ℓ2h_1(u_1)h_2(u_2)=\ell_1\ell_2. Every vertex outside BB is either a copy of a vertex of G1−B1G_1-B_1 or a vertex of G2−B2G_2-B_2, and its hatness is unchanged. In either case, it is at least ℓ^\hat{\ell}.

Consequently, whenever ℓ1ℓ2<ℓ^\ell_1\ell_2<\hat{\ell}, BB is the set of ℓ^\hat{\ell}-bad vertices of G\mathcal{G} and there are no ℓ^\hat{\ell}-bad vertices otherwise. The following two lemmas describe the evolution of property (ℓ^,ℓ,k,d,d~,D)(\hat{\ell},\ell,k,d,\tilde{d},D) under clique-joins and clique-join powers.

Lemma 13. Let G1=(G1,h1)\mathcal{G}_1=(G_1,h_1) and G2=(G2,h2)\mathcal{G}_2=(G_2,h_2) be hat games with properties (ℓ^,ℓ1,k1,d1,d~1,D1)(\hat{\ell},\ell_1,k_1,d_1,\tilde{d}_1,D_1) and (ℓ^,ℓ2,k2,d2,d~2,D2)(\hat{\ell},\ell_2,k_2,d_2,\tilde{d}_2,D_2), and with distinguished sets B1B_1 and B2B_2 respectively. If k1≥1k_1\ge1, then the hat game G:=G1⊕B1,B2G2=(G,h)\mathcal{G}:=\mathcal{G}_1\oplus_{B_1,B_2}\mathcal{G}_2=(G,h) has property (ℓ^,ℓ,k,d,d~,D)(\hat{\ell},\ell,k,d,\tilde{d},D) with

  1. ℓ=ℓ1ℓ2\ell=\ell_1\ell_2,

  1. k=k1k2k=k_1k_2,

  1. d=(k1−1)(k2−1)+d1+d2d=(k_1-1)(k_2-1)+d_1+d_2,

  1. d~=max⁡{d~1,(k1−1)k2+d~2}\tilde{d}=\max\{\tilde{d}_1,(k_1-1)k_2+\tilde{d}_2\}, and

  1. D=max⁡{D1,D2,d,d~}D=\max\{D_1,D_2,d,\tilde{d}\}.

Additionally, the resulting clique of G\mathcal{G} is the distinguished set witnessing the property.

Proof. Let BB be the resulting clique of G1⊕B1,B2G2\mathcal{G}_1\oplus_{B_1,B_2}\mathcal{G}_2. For 1) and 2), we can apply Lemma 12. We thus only need to prove the remaining items.

  1. Let v=(v1,v2)∈B=B1×B2v=(v_1,v_2)\in B=B_1\times B_2. The vertices v1v_1 and v2v_2 have at most d1−k1+1d_1-k_1+1 and d2−k2+1d_2-k_2+1 neighbors outside B1B_1 and B2B_2, respectively. Thus vv has at most d1+d2−k1−k2+2d_1+d_2-k_1-k_2+2 neighbors outside BB, and exactly k1k2−1k_1k_2-1 neighbors inside BB. Therefore deg⁡G(v)≤(k1−1)(k2−1)+d1+d2=d\deg_G(v)\le(k_1-1)(k_2-1)+d_1+d_2=d.

  1. Let vv be a vertex in N(B)∖BN(B) \setminus B. If vv belongs to a copy of G1G_1, then its corresponding vertex belongs to NG1(B1)∖B1N_{G_1}(B_1) \setminus B_1. Its degree is unchanged, and hence is at most d~1≤d~\widetilde{d}_1 \le\widetilde{d}. If vv comes from G2−B2G_2 - B_2, then let

i=∣NG2(v)∩B2∣ando=deg⁡G2(v)−i.i = \lvert N_{G_2}(v) \cap B_2 \rvert\quad\text{and}\quad o = \deg_{G_2}(v) - i.

We thus have

i+o≤d~2andi≤k2.i + o \le\widetilde{d}_2 \quad\text{and}\quad i \le k_2.

Moreover, deg⁡G(v)=k1i+o\deg_G(v) = k_1i + o. Therefore,

deg⁡G(v)≤k1i+d~2−i≤(k1−1)k2+d~2≤d~\deg_G(v) \le k_1i + \widetilde{d}_2 - i \le(k_1 - 1)k_2 + \widetilde{d}_2 \le\widetilde{d}

since by hypothesis, k1≥1k_1 \ge1.

  1. If a vertex of G1⊕B1,B2G2G_1 \oplus_{B_1,B_2} G_2 does not belong to B∪N(B)B \cup N(B), then it is of degree at most max⁡{D1,D2}\max\{D_1,D_2\}. Therefore the maximum degree of G1⊕B1,B2G2G_1 \oplus_{B_1,B_2} G_2 is at most max⁡{D1,D2,d,d~}\max\{D_1,D_2,d,\widetilde{d}\} by definition of dd and d~\widetilde{d}.

This proves the lemma.

Lemma 14. Let G=(G,h)\mathcal{G} = (G,h) be a hat game with property (ℓ^,ℓ,k,d,d~,D)(\widehat{\ell},\ell,k,d,\widetilde{d},D) with k≥1k \ge1 and distinguished set BB. Then for every integer i≥1i \ge1, the hat game G⊕B(i)\mathcal{G}^{\oplus_B(i)} has property (ℓ^,ℓ′,k′,d′,d~′,D′)(\widehat{\ell},\ell',k',d',\widetilde{d}',D') with

  1. ℓ′=ℓi\ell' = \ell^i,

  1. k′=kik' = k^i,

  1. d′=ki+i(d−k)+i−1d' = k^i + i(d-k) + i - 1,

  1. d~′=d~+ki−k\widetilde{d}' = \widetilde{d} + k^i - k, and

  1. D′=max⁡{D,d′,d~′}D' = \max\{D,d',\widetilde{d}'\}.

Additionally, the distinguished set witnessing this property is BB when i=1i = 1, and the resulting clique of the last clique-join when i≥2i \ge2.

Proof. We proceed by induction on ii. For i=1i = 1, the game is G\mathcal{G}, and the formulas give ℓ′=ℓ\ell' = \ell, k′=kk' = k, d′=dd' = d, d~′=d~\widetilde{d}' = \widetilde{d}, and D′=DD' = D, since D≥max⁡{d,d~}D \ge\max\{d,\widetilde{d}\}. Assume that the statement holds for some integer i≥1i \ge1 and prove it for i+1i+1. If i=1i = 1 we let B′=BB' = B, and otherwise we let B′B' be the resulting clique of the last clique-join in the construction of G⊕B(i)\mathcal{G}^{\oplus_B(i)}. By the induction hypothesis, G⊕B(i)\mathcal{G}^{\oplus_B(i)} has property

(ℓ^,ℓi,ki,ki+i(d−k)+i−1,d~+ki−k,max⁡{D,ki+i(d−k)+i−1,d~+ki−k})\left(\widehat{\ell},\ell^i,k^i,k^i+i(d-k)+i-1,\widetilde{d}+k^i-k,\max\{D,k^i+i(d-k)+i-1,\widetilde{d}+k^i-k\}\right)

with distinguished set B′B'. Moreover, by the definition of powers,

G⊕B(i+1)=G⊕B,B′G⊕B(i).\mathcal{G}^{\oplus_B(i+1)}=\mathcal{G}\oplus_{B,B'}\mathcal{G}^{\oplus_B(i)}.

Therefore, we can apply Lemma 13 to obtain that G⊕B(i+1)\mathcal{G}^{\oplus_B(i+1)} has property

(ℓ^,ℓ′,k′,d′,d~′,D′)(\widehat{\ell},\ell',k',d',\widetilde{d}',D')

with

  1. ℓ′=ℓℓi=ℓi+1\ell'=\ell\ell^i=\ell^{i+1},

  1. k′=kki=ki+1k'=kk^i=k^{i+1},

  1. d′=(k−1)(ki−1)+d+ki+i(d−k)+i−1=ki+1+(i+1)(d−k)+id'=(k-1)(k^i-1)+d+k^i+i(d-k)+i-1=k^{i+1}+(i+1)(d-k)+i,

  1. d~′=max⁡{d~,(k−1)ki+(ki−k+d~)}=ki+1−k+d~\tilde{d}'=\max\{\tilde{d},(k-1)k^i+(k^i-k+\tilde{d})\}=k^{i+1}-k+\tilde{d}, and

  1. D′=max⁡{max⁡{D,ki+i(d−k)+i−1,d~+ki−k},D,d′,d~′}=max⁡{D,d′,d~′}D'=\max\{\max\{D,k^i+i(d-k)+i-1,\tilde{d}+k^i-k\},D,d',\tilde{d}'\}=\max\{D,d',\tilde{d}'\}, 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 G⊕B,B′G⊕B(i)\mathcal{G}\oplus_{B,B'}\mathcal{G}^{\oplus B(i)} witnesses the property as desired.

The construction: description and analysis

Informal description of the construction

Our goal is to construct a winning hat game G=(G,h)\mathcal{G}=(G,h) such that GG has maximum degree at most (1e+ε)ℓ^(\frac{1}{e}+\varepsilon)\hat{\ell} and for every vertex vv of GG, h(v)=ℓ^h(v)=\hat{\ell}. In this informal description, we implicitly reduce any larger hatness to ℓ^\hat{\ell}, which preserves winnability.

The construction starts with the following observation. For every integer k≥0k\ge0, we can apply Lemma 9 to construct a winning game G0=(G0,h0)\mathcal{G}_0=(G_0,h_0) such that G0G_0 is a complete graph of order ⌈ℓ^/(k+1)⌉+k\lceil\hat{\ell}/(k+1)\rceil+k, with a set S0S_0 of kk distinguished vertices and such that

h0(v)={ℓ^if v∈V(G0)∖S0k+1if v∈S0.h_0(v)= \begin{cases} \hat{\ell} & \text{if } v\in V(G_0)\setminus S_0\\ k+1 & \text{if } v\in S_0. \end{cases}

For sufficiently large kk and ℓ^\hat{\ell} sufficiently large compared with k2k^2, the maximum degree is small compared with (1e+ε)ℓ^(\frac{1}{e}+\varepsilon)\hat{\ell}. Moreover, the proportion of distinguished vertices is k/(k+⌈ℓ^/(k+1)⌉)k/(k+\lceil\hat{\ell}/(k+1)\rceil), which is small when ℓ^\hat{\ell} is large compared with k2k^2. If the degrees of the vertices in S0S_0 were sufficiently small, we could finish by taking a clique-join of G0\mathcal{G}_0 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 Gi=(Gi,hi)\mathcal{G}_i=(G_i,h_i) with a set SiS_i of kk vertices such that

hi(v)={ℓ^if v∈V(Gi)∖Sik+1if v∈Si.h_i(v)= \begin{cases} \hat{\ell} & \text{if } v\in V(G_i)\setminus S_i\\ k+1 & \text{if } v\in S_i. \end{cases}

Then, with the right parameters, Lemma 15 constructs a winning hat game Gi+1=(Gi+1,hi+1)\mathcal{G}_{i+1}=(G_{i+1},h_{i+1}) with a set Si+1S_{i+1} of kk vertices such that

hi+1(v)={ℓ^if v∈V(Gi+1)∖Si+1k+1if v∈Si+1.h_{i+1}(v)= \begin{cases} \hat{\ell} & \text{if } v\in V(G_{i+1})\setminus S_{i+1}\\ k+1 & \text{if } v\in S_{i+1}. \end{cases}

and a smaller degree bound on the vertices in Si+1S_{i+1} than on those in SiS_i. 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 ii, k′k' and a hat game G=(G,hG)\mathcal{G}=(G,h_G) with distinguished set BGB_G. First, we construct the ii-th power G⊕BG(i)\mathcal{G}^{\oplus B_G(i)}, with distinguished set BiB_i. We then take its clique-join with the game H=(H,hH)\mathcal{H}=(H,h_H), where HH is a clique. For every vertex v∈V(H)∖BHv \in V(H) \setminus B_H, we replace vv by a clique on ∣Bi∣|B_i| vertices v1,…,v∣Bi∣v_1,\ldots,v_{|B_i|} and attach a fresh copy of G⊕BG(i)\mathcal{G}^{\oplus B_G(i)} by identifying its distinguished vertices with the vertices v1,…,v∣Bi∣v_1,\ldots,v_{|B_i|}.

Lemma 15. Let k≥1k \ge1 and suppose there exists a hat game G=(G,hG)\mathcal{G}=(G,h_G) with property

(ℓ^,k+1,k,d,d~,D).(\hat{\ell}, k+1, k, d, \tilde{d}, D).

Then for all integers i≥1i \ge1 and k′k' such that 0≤k′<ℓ^0 \le k' < \hat{\ell}, there exists a hat game F=(F,hF)\mathcal{F}=(F,h_F) with property

(ℓ^,k′+1,k′,d′,d~′,max⁡{D,d~,d~+ki−k})(\hat{\ell}, k'+1, k', d', \tilde{d}', \max\{D,\tilde{d},\tilde{d}+k^i-k\})

with

d′=k′+ki⌊ℓ^(k+1)i(k′+1)⌋−1d'=k'+k^i\left\lfloor\frac{\hat{\ell}}{(k+1)^i(k'+1)}\right\rfloor-1

and

d~′=d′+i⋅d.\tilde{d}'=d'+i\cdot d.

Proof. Let G=(G,hG)\mathcal{G}=(G,h_G) be a hat game with property (ℓ^,k+1,k,d,d~,D)(\hat{\ell}, k+1, k, d, \tilde{d}, D) and distinguished set BGB_G as in the statement. Fix ii and k′k' as in the statement. By

Lemma 14. G⊕BG(i)\mathcal{G}^{\oplus B_{\mathcal{G}}(i)} is a hat game with property (ℓ^,(k+1)i,ki,ki+i(d−k)+i−1,d~+ki−k,max⁡{D,ki+i(d−k)+i−1,d~+ki−k})\left(\hat{\ell},(k+1)^i,k^i,k^i+i(d-k)+i-1,\tilde{d}+k^i-k,\max\{D,k^i+i(d-k)+i-1,\tilde{d}+k^i-k\}\right).

Let BiB_i be the set of vertices witnessing this property. Consider now the hat game H=(H,hH)\mathcal{H}=(H,h_{\mathcal{H}}) where HH is the complete graph of order

k′+⌈ℓ^(k+1)i(k′+1)⌉k'+\left\lceil\frac{\hat{\ell}}{(k+1)^i(k'+1)}\right\rceil

with a set BHB_{\mathcal{H}} of k′k' vertices of HH such that for every v∈V(H)v\in V(H), if v∈BHv\in B_{\mathcal{H}} then hH(v)=k′+1h_{\mathcal{H}}(v)=k'+1 and if v∉BHv\notin B_{\mathcal{H}} then hH(v)=⌈ℓ^(k+1)i⌉h_{\mathcal{H}}(v)=\left\lceil\frac{\hat{\ell}}{(k+1)^i}\right\rceil. By Lemma 9, H\mathcal{H} is winning since

∑v∈V(H)1hH(v)=k′k′+1+⌈ℓ^(k+1)i(k′+1)⌉⌈ℓ^(k+1)i⌉≥k′k′+1+ℓ^(k+1)i(k′+1)⌈ℓ^(k+1)i⌉=1,\begin{aligned} \sum_{v\in V(H)}\frac{1}{h_{\mathcal{H}}(v)} =\frac{k'}{k'+1}+ \frac{\left\lceil\frac{\hat{\ell}}{(k+1)^i(k'+1)}\right\rceil}{\left\lceil\frac{\hat{\ell}}{(k+1)^i}\right\rceil} \\ &\geq\frac{k'}{k'+1}+ \frac{\frac{\hat{\ell}}{(k+1)^i(k'+1)}}{\left\lceil\frac{\hat{\ell}}{(k+1)^i}\right\rceil} \\ &=1, \end{aligned}

where the inequality comes from the fact that for every real number xx and positive integer yy, ⌈x/y⌉=⌈⌈x⌉/y⌉≥⌈x⌉/y\lceil x/y\rceil=\lceil\lceil x\rceil/y\rceil\geq\lceil x\rceil/y. So H\mathcal{H} has property

(⌈ℓ^(k+1)i⌉,k′+1,k′,δ,δ,δ)\left(\left\lceil\frac{\hat{\ell}}{(k+1)^i}\right\rceil,k'+1,k',\delta,\delta,\delta\right)

with distinguished set BHB_{\mathcal{H}}, and where δ=k′+⌈ℓ^(k+1)i(k′+1)⌉−1\delta=k'+\left\lceil\frac{\hat{\ell}}{(k+1)^i(k'+1)}\right\rceil-1. We can finally construct the hat game

F=(F,hF)=G⊕BG(i)⊕Bi,V(H)∖BHH.\mathcal{F}=(F,h_{\mathcal{F}})=\mathcal{G}^{\oplus B_{\mathcal{G}}(i)}\oplus_{B_i,V(H)\setminus B_{\mathcal{H}}}\mathcal{H}.
  • The set BFB_{\mathcal{F}} of vertices of FF corresponding to BHB_{\mathcal{H}} is the new set of distinguished vertices. By construction, ∣BF∣=∣BH∣=k′|B_{\mathcal{F}}|=|B_{\mathcal{H}}|=k' and for every vertex v∈BFv\in B_{\mathcal{F}}, hF(v)=k′+1h_{\mathcal{F}}(v)=k'+1, and vv has degree at most

k′+ki⌈ℓ^(k+1)i(k′+1)⌉−1=d′.k'+k^i\left\lceil\frac{\hat{\ell}}{(k+1)^i(k'+1)}\right\rceil-1=d'.
  • For every vertex v∈V(F)∖BFv\in V(F)\setminus B_{\mathcal{F}}, vv is a copy of a vertex of G⊕BG(i)\mathcal{G}^{\oplus B_{\mathcal{G}}(i)}. If vv is a copy of a vertex uu not in BiB_i, then hG⊕BG(i)(u)≥ℓ^h_{\mathcal{G}^{\oplus B_{\mathcal{G}}(i)}}(u)\geq\hat{\ell} so hF(v)≥ℓ^h_{\mathcal{F}}(v)\geq\hat{\ell}. In this case, no neighbor of vv is in BFB_{\mathcal{F}}. Otherwise, vv is a copy of a vertex uu in BiB_i and therefore hG⊕BG(i)(u)=(k+1)ih_{\mathcal{G}^{\oplus B_{\mathcal{G}}(i)}}(u)=(k+1)^i in which case hF(v)=(k+1)i⌈ℓ^(k+1)i⌉≥ℓ^h_{\mathcal{F}}(v)=(k+1)^i\left\lceil\frac{\hat{\ell}}{(k+1)^i}\right\rceil\geq\hat{\ell}.

Every neighbor of BFB_{\mathcal{F}} is in this second case, and vv has degree at most

ki+i(d−k)+i−1+k′+ki(⌈ℓ^(k+1)i(k′+1)⌉−1)≤k′+ki⌊ℓ^(k+1)i(k′+1)⌋−1+i⋅d=d~′,\begin{aligned} k^{i}+i(d-k)+i-1+k^{\prime}+k^{i}\left(\left\lceil\frac{\hat{\ell}}{(k+1)^{i}(k^{\prime}+1)}\right\rceil-1\right) \\ &\le k^{\prime}+k^{i}\left\lfloor\frac{\hat{\ell}}{(k+1)^{i}(k^{\prime}+1)}\right\rfloor-1+i\cdot d \\ &=\tilde{d}^{\prime}, \end{aligned}

as needed.

  • FF has maximum degree at most

max⁡{max⁡{D,ki+i(d−k)+i−1,d~+ki−k},d′,d~′,d~+ki−k}=max⁡{D,d~′,d~+ki−k}\begin{aligned} \max\{\max\{D,k^{i}+i(d-k)+i-1,\tilde{d}+k^{i}-k\},d^{\prime},\tilde{d}^{\prime},\tilde{d}+k^{i}-k\} \\ &=\max\{D,\tilde{d}^{\prime},\tilde{d}+k^{i}-k\} \end{aligned}

using the fact that by definition d~′≥k′+ki−1+id≥ki+i(d−k)+i−1\tilde{d}^{\prime}\ge k^{\prime}+k^{i}-1+id\ge k^{i}+i(d-k)+i-1 and d~′≥d′\tilde{d}^{\prime}\ge d^{\prime}.

We have verified that F=(F,hF)\mathcal{F}=(F,h_{\mathcal{F}}) has property

(ℓ^,k′+1,k′,d′,d~′,max⁡{D,d~′,d~+ki−k})\left(\hat{\ell},k^{\prime}+1,k^{\prime},d^{\prime},\tilde{d}^{\prime},\max\{D,\tilde{d}^{\prime},\tilde{d}+k^{i}-k\}\right)

with the distinguished set BFB_{\mathcal{F}}, as desired.

Lemma 16. For every nonnegative integer ii and all positive integers ℓ>k\ell>k, there exists a hat game (G,h)(G,h) with property

(ℓ^,k+1,k,d,d~,D)(\hat{\ell},k+1,k,d,\tilde{d},D)

with

d=f(k,i),d=f(k,i),
d~=f(k,i)+i⋅f(k,i−1),\tilde{d}=f(k,i)+i\cdot f(k,i-1),

and

D=max⁡j=0…i{f(k,j)+j⋅f(k,j−1)+kj+1},D=\max_{j=0\ldots i}\{f(k,j)+j\cdot f(k,j-1)+k^{j+1}\},

where

f(k,j)={kj⌈ℓ^(k+1)j+1⌉+k−1when j≥00otherwise.f(k,j)= \begin{cases} k^{j}\left\lceil\frac{\hat{\ell}}{(k+1)^{j+1}}\right\rceil+k-1 & \text{when }j\ge0\\ 0 & \text{otherwise.} \end{cases}

Proof. Let G0G_{0} be the clique of size ⌈ℓ^k+1⌉+k\left\lceil\frac{\hat{\ell}}{k+1}\right\rceil+k, let SS be a subset of V(G)V(G) of size kk, and let h0h_{0} be the function such that h0(v)=k+1h_{0}(v)=k+1 for all v∈Sv\in S and h0(v)=ℓ^h_{0}(v)=\hat{\ell} for all v∈V(G)∖Sv\in V(G)\setminus S. By Lemma 9, the hat game (G0,h0)(G_{0},h_{0}) is winning since

∑v∈V(G)1h(v)=kk+1+⌈ℓ^k+1⌉1ℓ^≥kk+1+1k+1=1.\sum_{v\in V(G)}\frac{1}{h(v)} =\frac{k}{k+1}+\left\lceil\frac{\hat{\ell}}{k+1}\right\rceil\frac{1}{\hat{\ell}} \ge\frac{k}{k+1}+\frac{1}{k+1}=1.

Hence, the hat game (G0,h0)(G_{0},h_{0}) has property (ℓ^,k+1,k,δ,δ,δ)(\hat{\ell},k+1,k,\delta,\delta,\delta) with δ=⌈ℓ^k+1⌉+k−1=f(k,0)≤f(k,0)+k\delta=\left\lceil\frac{\hat{\ell}}{k+1}\right\rceil+k-1=f(k,0)\le f(k,0)+k. We now proceed by induction on ii. Suppose there exists a hat game Gi=(Gi,hi)\mathcal{G}_i=(G_i,h_i) with property

(ℓ^,k+1,k,di,d~i,Di)\left(\hat{\ell},k+1,k,d_i,\tilde{d}_i,D_i\right)

where

di=f(k,i),d_i=f(k,i),
d~i=f(k,i)+i⋅f(k,i−1),\tilde{d}_i=f(k,i)+i\cdot f(k,i-1),

and

Di≤max⁡0≤j≤i{f(k,j)+j⋅f(k,j−1)+kj+1}.D_i\leq\max_{0\leq j\leq i}\left\{f(k,j)+j\cdot f(k,j-1)+k^{j+1}\right\}.

Applying Lemma 15 to Gi\mathcal{G}_i with k′=kk'=k and exponent i+1i+1, we obtain a hat game Gi+1=(Gi+1,hi+1)\mathcal{G}_{i+1}=(G_{i+1},h_{i+1}) with property

(ℓ^,k+1,k,di+1,d~i+1,max⁡{Di,d~i+1,d~i+ki+1−k})\left(\hat{\ell},k+1,k,d_{i+1},\tilde{d}_{i+1},\max\{D_i,\tilde{d}_{i+1},\tilde{d}_i+k^{i+1}-k\}\right)

with

di+1=k+ki+1⌊ℓ^(k+1)i+2⌋−1=f(k,i+1),d_{i+1}=k+k^{i+1}\left\lfloor\frac{\hat{\ell}}{(k+1)^{i+2}}\right\rfloor-1=f(k,i+1),

and

d~i+1=di+1+(i+1)⋅di=f(k,i+1)+(i+1)⋅f(k,i).\begin{aligned} \tilde{d}_{i+1}&=d_{i+1}+(i+1)\cdot d_i\\ &=f(k,i+1)+(i+1)\cdot f(k,i). \end{aligned}

Now let

Di+1=max⁡0≤j≤i+1{f(k,j)+jf(k,j−1)+kj+1}D_{i+1}=\max_{0\leq j\leq i+1}\left\{f(k,j)+jf(k,j-1)+k^{j+1}\right\}
=max⁡{max⁡0≤j≤i{f(k,j)+jf(k,j−1)+kj+1},f(k,i+1)+(i+1)f(k,i)+ki+2,f(k,i)+if(k,i−1)+ki+1}\begin{aligned} &=\max\left\{ \begin{array}{l} \max_{0\leq j\leq i}\{f(k,j)+jf(k,j-1)+k^{j+1}\},\\ f(k,i+1)+(i+1)f(k,i)+k^{i+2},\\ f(k,i)+if(k,i-1)+k^{i+1} \end{array} \right\} \end{aligned}
≥max⁡{max⁡0≤j≤i{f(k,j)+jf(k,j−1)+kj+1},f(k,i+1)+(i+1)f(k,i),f(k,i)+if(k,i−1)+ki+1−k}≥max⁡{Di,d~i+1,d~i+ki+1−k}.\begin{aligned} &\geq\max\left\{ \begin{array}{l} \max_{0\leq j\leq i}\{f(k,j)+jf(k,j-1)+k^{j+1}\},\\ f(k,i+1)+(i+1)f(k,i),\\ f(k,i)+if(k,i-1)+k^{i+1}-k \end{array} \right\} \\ &\geq\max\{D_i,\tilde{d}_{i+1},\tilde{d}_i+k^{i+1}-k\}. \end{aligned}

So in particular Gi+1G_{i+1} has maximum degree at most Di+1D_{i+1}, and Gi+1\mathcal{G}_{i+1} has property

(ℓ^,k+1,k,di+1,d~i+1,Di+1)\left(\hat{\ell},k+1,k,d_{i+1},\tilde{d}_{i+1},D_{i+1}\right)

as desired. □\square

To interpret Lemma 16 asymptotically, suppose k→∞k\to\infty, i=Θ(k)i=\Theta(k), and (k+1)i+1=o(ℓ^)(k+1)^{i+1}=o(\hat{\ell}). Since kk+1=exp⁡(−1/k+O(k−2))\frac{k}{k+1}=\exp(-1/k+O(k^{-2})) and the rounding error in f(k,i)f(k,i) is O(ki+k)O(k^i+k), we obtain f(k,i)∼ℓ^ke−i/kf(k,i)\sim\frac{\hat{\ell}}{k}e^{-i/k}. The graph in Lemma 16 has kk distinguished vertices, all of hatness k+1k+1. The degree bounds for these vertices and their neighbors are respectively of order ℓ^ke−i/k\frac{\hat{\ell}}{k}e^{-i/k} and iℓ^ke−i/k\frac{i\hat{\ell}}{k}e^{-i/k}; the global maximum-degree bound is tracked separately.

We now provide the last step of the construction.

Lemma 17. For all positive integers i1,i2,k,ℓ^i_1,i_2,k,\hat{\ell} with ℓ^>k\hat{\ell}>k, there exists a hat game H=(H,hH)\mathcal{H}=(H,h_{\mathcal{H}}) with property

(ℓ^,1,0,dH,d~H,DH)(\hat{\ell},1,0,d_{\mathcal{H}},\widetilde{d}_{\mathcal{H}},D_{\mathcal{H}})

such that

dH=ki2⌊ℓ^(k+1)i2⌋−1d_{\mathcal{H}}=k^{i_2}\left\lfloor\frac{\hat{\ell}}{(k+1)^{i_2}}\right\rfloor-1

and

d~H=dH+i2⋅f(k,i1),\widetilde{d}_{\mathcal{H}}=d_{\mathcal{H}}+i_2\cdot f(k,i_1),

and

DH=max⁡{d~H,f(k,i1)+i1⋅f(k,i1−1)+ki2−k,max⁡j=0…i1{f(k,j)+j⋅f(k,j−1)+kj+1}},D_{\mathcal{H}}=\max\left\{\widetilde{d}_{\mathcal{H}},f(k,i_1)+i_1\cdot f(k,i_1-1)+k^{i_2}-k,\max_{j=0\ldots i_1}\left\{f(k,j)+j\cdot f(k,j-1)+k^{j+1}\right\}\right\},

where

f(k,i)={ki⌊ℓ^(k+1)i+1⌋+k−1when i≥00otherwise.f(k,i)= \begin{cases} k^i\left\lfloor\frac{\hat{\ell}}{(k+1)^{i+1}}\right\rfloor+k-1 & \text{when }i\ge0\\ 0 & \text{otherwise.} \end{cases}

Proof. Let G=(G,hG)\mathcal{G}=(G,h_{\mathcal{G}}) be the hat game with property

(ℓ^,k+1,k,dG,d~G,DG)(\hat{\ell},k+1,k,d_{\mathcal{G}},\widetilde{d}_{\mathcal{G}},D_{\mathcal{G}})

constructed by Lemma 16 using i=i1i=i_1, kk and ℓ^\hat{\ell}. In particular,

dG=f(k,i1),d_{\mathcal{G}}=f(k,i_1),
d~G=f(k,i1)+i1⋅f(k,i1−1),\widetilde{d}_{\mathcal{G}}=f(k,i_1)+i_1\cdot f(k,i_1-1),

and

DG=max⁡j=0…i1{f(k,j)+j⋅f(k,j−1)+kj+1}.D_{\mathcal{G}}=\max_{j=0\ldots i_1}\left\{f(k,j)+j\cdot f(k,j-1)+k^{j+1}\right\}.

We can thus apply Lemma 15 with the hat game G=(G,hG)\mathcal{G}=(G,h_{\mathcal{G}}) and parameters i=i2i=i_2 and k′=0k'=0 in order to construct a hat game H=(H,hH)\mathcal{H}=(H,h_{\mathcal{H}}) with property

(ℓ^,1,0,dH,d~H,max⁡{DG,d~H,d~G+ki2−k})(\hat{\ell},1,0,d_{\mathcal{H}},\widetilde{d}_{\mathcal{H}},\max\{D_{\mathcal{G}},\widetilde{d}_{\mathcal{H}},\widetilde{d}_{\mathcal{G}}+k^{i_2}-k\})

where

dH=ki2⌊ℓ^(k+1)i2⌋−1d_{\mathcal{H}}=k^{i_2}\left\lfloor\frac{\hat{\ell}}{(k+1)^{i_2}}\right\rfloor-1

and

d~H=dH+i2⋅dG,\widetilde{d}_{\mathcal{H}}=d_{\mathcal{H}}+i_2\cdot d_{\mathcal{G}},

as desired.

The game from Lemma 17 has no vertex of hatness less than ℓ^\hat{\ell}, so it remains to verify that for any ϵ>0\epsilon>0 there is a choice of parameters such that the maximum degree of the graph is at most (1e+ϵ)ℓ^\left(\frac{1}{e}+\epsilon\right)\hat{\ell}

Theorem 18. For every ε∈(0,2/e)\varepsilon\in(0,2/e) and for every sufficiently large integer ℓ^\hat{\ell} (depending only on ε\varepsilon), there exists a winning hat game H=(H,hH)\mathcal{H}=(H,h_H) such that, for every vertex v∈V(H)v\in V(H), hH(v)≥ℓ^h_H(v)\ge\hat{\ell} and Δ(H)≤(1/e+ε)ℓ^\Delta(H)\le(1/e+\varepsilon)\hat{\ell}.

Proof. Fix ε∈(0,2/e)\varepsilon\in(0,2/e) and let

k=⌈8eε⌉,i1=⌈(k+1)log⁡(2ε)⌉,i2=k+1.k=\left\lceil\frac{8}{e\varepsilon}\right\rceil,\qquad i_1=\left\lceil(k+1)\log\left(\frac{2}{\varepsilon}\right)\right\rceil,\qquad i_2=k+1.

For ℓ^>k\hat{\ell}>k, we apply Lemma 17 with parameters k,i1,i2k,i_1,i_2, and ℓ^\hat{\ell}. It produces a winning hat game H=(H,hH)\mathcal{H}=(H,h_H) in which every vertex has hatness at least ℓ^\hat{\ell}, and such that

Δ(H)≤max⁡{b1,b2,b3}.\Delta(H)\le\max\{b_1,b_2,b_3\}.

where

b1=kk+1⌈ℓ^(k+1)k+1⌉−1+(k+1)f(k,i1),b2=f(k,i1)+i1f(k,i1−1)+kk+1−k,b3=max⁡0≤j≤i1{f(k,j)+jf(k,j−1)+kj+1}.\begin{aligned} b_1&=k^{k+1}\left\lceil\frac{\hat{\ell}}{(k+1)^{k+1}}\right\rceil-1+(k+1)f(k,i_1),\\ b_2&=f(k,i_1)+i_1f(k,i_1-1)+k^{k+1}-k,\\ b_3&=\max_{0\le j\le i_1}\{f(k,j)+jf(k,j-1)+k^{j+1}\}. \end{aligned}

with

f(k,i)={ki⌈ℓ^(k+1)i+1⌉+k−1,i≥0,0,i<0.f(k,i)= \begin{cases} k^i\left\lceil\frac{\hat{\ell}}{(k+1)^{i+1}}\right\rceil+k-1,&i\ge0,\\ 0,&i<0. \end{cases}

We show that each of these bounds is at most (1/e+ε)ℓ^(1/e+\varepsilon)\hat{\ell} when ℓ^\hat{\ell} is sufficiently large.

By hypothesis, ε<2e\varepsilon<\frac{2}{e}, that is, ln⁡(2ε)>1\ln\left(\frac{2}{\varepsilon}\right)>1 so i1>k+1i_1>k+1 and kk+1<ki1+1k^{k+1}<k^{i_1+1}. By comparing b2b_2 with the last term of the maximum in b3b_3 we get b2≤b3b_2\le b_3. So it is enough to bound b1b_1 and b3b_3.

Using the classical inequality 1−x<e−x1-x<e^{-x} for every x>0x>0, we have

kk+1<e−1/(k+1).(1)\frac{k}{k+1}<e^{-1/(k+1)}. \tag*{(1)}

This implies for all i≥0i\ge0,

f(k,i)≤ℓ^k+1e−i/(k+1)+ki+k−1,(2)f(k,i)\le\frac{\hat{\ell}}{k+1}e^{-i/(k+1)}+k^i+k-1, \tag*{(2)}

where the case i=0i=0 is trivial. Applying (1) to the first term of b1b_1, followed by (2), we get

b1≤ℓ^e+kk+1+(k+1)f(k,i1)≤ℓ^(1e+1ei1/(k+1))+kk+1+(k+1)ki1+(k+1)k≤ℓ^(1e+ε2)+3(k+1)ki1.\begin{aligned} b_1&\le\frac{\hat{\ell}}{e}+k^{k+1}+(k+1)f(k,i_1)\\ &\le\hat{\ell}\left(\frac{1}{e}+\frac{1}{e^{i_1/(k+1)}}\right)+k^{k+1}+(k+1)k^{i_1}+(k+1)k\\ &\le\hat{\ell}\left(\frac{1}{e}+\frac{\varepsilon}{2}\right)+3(k+1)k^{i_1}. \end{aligned}

where the last inequality follows from the choice of i1≥(k+1)log⁡2ε>k+1i_1 \ge(k+1)\log\frac{2}{\varepsilon} > k+1. This implies the desired b1≤(1/e+ε)ℓ^b_1 \le(1/e+\varepsilon)\hat{\ell} as soon as ℓ^≥ℓ^1:=8(k+1)ki1/ε\hat{\ell} \ge\hat{\ell}_1 := 8(k+1)k^{i_1}/\varepsilon.

To bound b3b_3, set g(j)=1k+1+jk+1e(1−j)/(k+1)g(j) = \frac{1}{k+1} + \frac{j}{k+1}e^{(1-j)/(k+1)}. By (2), for every integer 0≤j≤i10 \le j \le i_1 (with j=0j=0 checked directly),

f(k,j)+jf(k,j−1)+kj+1≤ℓ^g(j)+(j+2)(kj+1+kk+1)≤ℓ^g(j)+2(i1+2)ki1+1.\begin{aligned} f(k,j)+jf(k,j-1)+k^{j+1} \le\hat{\ell}g(j)+(j+2)(k^{j+1}+k^{k+1}) \\ &\le\hat{\ell}g(j)+2(i_1+2)k^{i_1+1}. \end{aligned}

Viewing gg as a function of a nonnegative real variable, differentiation shows that it is maximized at j=k+1j=k+1. Thus,

max⁡j≥0g(j)=g(k+1)=1k+1+e−k/(k+1)=1k+1+e1/(k+1)e≤1e+1k+1+1ek≤1e+ε2.\max_{j\ge0}g(j)=g(k+1) = \frac{1}{k+1}+e^{-k/(k+1)} = \frac{1}{k+1}+\frac{e^{1/(k+1)}}{e} \le\frac{1}{e}+\frac{1}{k+1}+\frac{1}{ek} \le\frac{1}{e}+\frac{\varepsilon}{2}.

The penultimate inequality follows from (1). For the last one, the choice of kk gives 1k+1+1ek≤1+1/ek≤e+18ε<ε/2\frac{1}{k+1}+\frac{1}{ek}\le\frac{1+1/e}{k}\le\frac{e+1}{8}\varepsilon<\varepsilon/2. Finally, we get

b3≤ℓ^(1e+ε2)+2(i1+2)ki1+1b_3\le\hat{\ell}\left(\frac{1}{e}+\frac{\varepsilon}{2}\right)+2(i_1+2)k^{i_1+1}

which implies the desired b3≤(1/e+ε)ℓ^b_3\le(1/e+\varepsilon)\hat{\ell} as soon as ℓ^≥ℓ^3:=4(i1+2)ki1+1/ε\hat{\ell}\ge\hat{\ell}_3:=4(i_1+2)k^{i_1+1}/\varepsilon.

Combining the thresholds, it suffices to require

ℓ^≥ℓ^0:=max⁡{ℓ^1,ℓ^3}=4(i1+2)ki1+1ε.\hat{\ell}\ge\hat{\ell}_0:=\max\{\hat{\ell}_1,\hat{\ell}_3\}=\frac{4(i_1+2)k^{i_1+1}}{\varepsilon}.

Since kk and i1i_1 depend only on ε\varepsilon, so does this threshold which concludes the proof.

To deduce Theorem 1, assume 0<ε<e0<\varepsilon<e, put η=ε/(2e2)\eta=\varepsilon/(2e^2), and let ℓ^=⌊Δ/(1/e+η)⌋\hat{\ell}=\lfloor\Delta/(1/e+\eta)\rfloor. For sufficiently large Δ\Delta, Theorem 18 with parameter η\eta gives a winning game of maximum degree at most (1/e+η)ℓ^≤Δ(1/e+\eta)\hat{\ell}\le\Delta and hatness at least ℓ^\hat{\ell} at every vertex. Reducing all hatnesses to ℓ^\hat{\ell} preserves winnability. Since 1/(1/e+η)≥e−ε/21/(1/e+\eta)\ge e-\varepsilon/2, we obtain HG⁡(G)≥ℓ^≥(e−ε/2)Δ−1≥(e−ε)Δ\operatorname{HG}(G)\ge\hat{\ell}\ge(e-\varepsilon/2)\Delta-1\ge(e-\varepsilon)\Delta for sufficiently large Δ\Delta.

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 4/34/3. More precisely, we sought to iterate a construction in which most vertices have the desired hatness ℓ^\hat{\ell}, the graph has maximum degree Δ\Delta, and a small distinguished clique has lower hatness. It was not clear that the constant ee 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 4/34/3 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 ℓ^\hat{\ell} and kk as input. Ignoring integer rounding, it represented the starting clique game by a tuple of parameters: kk vertices had hatness k+1k+1, and ℓ^/(k+1)\hat{\ell}/(k+1) vertices had hatness ℓ^\hat{\ell} (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 ℓ^\hat{\ell} 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 HG⁡(G)≥2Δ(G)\operatorname{HG}(G) \ge2\Delta(G). The observation that e=lim⁡k→∞(k+1k)ke = \lim_{k\to\infty}\left(\frac{k+1}{k}\right)^k 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 HG⁡(G)<eΔ(G)\operatorname{HG}(G) < e\Delta(G) 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 (1/e+o(1))ℓ^=(1−o(1))Δ(G)(1/e+o(1))\hat{\ell}=(1-o(1))\Delta(G). Since the treewidth of a chordal graph equals its maximum clique size minus one, our construction also satisfies tw⁡(G)=(1−o(1))Δ(G)\operatorname{tw}(G)=(1-o(1))\Delta(G). 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 ff such that every graph GG of treewidth tt satisfies HG⁡(G)≤f(t)\operatorname{HG}(G) \le f(t)?

He and Li [10] constructed graphs of pathwidth dd with hat guessing number sd−1s_d-1, where (sd)(s_d) is Sylvester’s sequence, defined by s0=2s_0=2 and sd+1=sd2−sd+1s_{d+1}=s_d^2-s_d+1. 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 GG itself is a valid dependency graph for the events used in the LLL upper bound on HG⁡(G)\operatorname{HG}(G), 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. [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. [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. [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. [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. [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. [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. [7]Michal Farnik. A hat guessing game. PhD thesis, Jagiellonian University, 2015.
  8. [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. [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. [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. [11]Konstantin Kokhas and Aleksei Latyshev. Cliques and constructors in “hats” game. I. Journal of Mathematical Sciences, 255(1):39–57, 2021.DOI
  12. [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. [13]Aleksei Latyshev and Konstantin Kokhas. The Hats game. On maximum degree and diameter. Discrete Mathematics, 345(7):112868, 2022.DOI
  14. [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. [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. [16]James B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241–245, 1985.DOI
  17. [17]Mason Shurman and Scott Albert Sibley. An upper bound on the hat guessing number of graphs, 2026.arxiv.org/abs/2607.07994

Paper details

vlnc:W_q9cedxus
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 16

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT, GPT-6, Claude, Claude Opus 5.5

View statement
Looking for related papers…
Contents