1 Introduction↩︎

1.1 Background and main results↩︎

The fractional chromatic number of a graph \(G\), denoted \(\chi_f (G)\), is the minimum integer \(k \geq 1\) such that there exists a probability distribution \(\mathcal{D}\) over the independent sets of \(G\) such that \(\Pr_{I \sim \mathcal{D}}[v\in I] \geq 1/k\) for each vertex \(v \in V(G)\). It is well known through greedy arguments that \[\chi_f(G) \leq \chi(G) \leq d(G) + 1 \leq \Delta(G) + 1,\] where \(\Delta(G)\) denotes the maximum degree of \(G\) and \(d(G)\) denotes the degeneracy of \(G\). Brooks’s Theorem [1] implies that equality holds throughout if and only if some connected component of \(G\) is isomorphic to the complete graph \(K_{\Delta(G) + 1}\).

A natural question is the following: under what structural constraints can we obtain improved bounds on \(\chi_f(\cdot)\)? A seminal result of Johansson [2] states that every \(K_3\)-free graph \(G\) of maximum degree \(\Delta\) has chromatic number \(O(\Delta/\log\Delta)\) (see [3]–[5] for more recent proofs with improvements in terms of the leading constant factor). Shortly thereafter, Alon, Krivelevich, and Sudakov [6] generalized the result to locally sparse graphs, i.e., graphs where \(e(G[N(v)]) \ll \Delta^2\) for each vertex \(v \in V(G)\). They conjectured the bound holds for all \(F\)-free graphs, which has spurred a large research effort over the past \(\sim\)​30 years; see, e.g., [5], [7]–[14].

Each of these results immediately imply bounds on the fractional chromatic number in terms of the maximum degree. There has been a lot of work on bounds for the fractional chromatic number in terms of other parameters; e.g., the average degree or local versions (see [5], [9], [15]–[17]). In this paper, we are interested in the degeneracy of a graph. A graph \(G\) is \(d\)-degenerate if every subgraph of \(G\) contains a vertex of degree at most \(d\). The starting point of our investigation is the following recent result of Martinsson and Steiner [16], which resolves a conjecture of Harris [18]:

It should be noted that there exist \(d\)-degenerate \(K_3\)-free graphs \(G\) satisfying \(\chi(G) = d+1\) [19], [20] and so the above cannot hold for the chromatic number in general. Although, if \(n\) is not too large, Bradač, Fox, Steiner, Sudakov, and Zhang [21] recently showed that \(\chi(G) = O\left(\frac{d}{\log (d/\log n)}\right)\) for \(n\)-vertex \(d\)-degenerate \(K_3\)-free graphs \(G\). In their proof of Theorem 1, Martinsson and Steiner develop a novel procedure to sample an independent set from \(G\). They assign each vertex an initial weight, traverse the graph according to an ordering determined by the degeneracy, and include each vertex in the independent set with probability determined by its current weight while updating the weights of unexplored vertices along the way. To ascertain the probability a vertex is included in the independent set, they analyze an auxiliary process with a modified weight update procedure.

We develop a new approach toward fractional coloring \(d\)-degenerate graphs rooted in an entropy-based argument inspired by Johansson’s seminal work on coloring \(K_3\)-free graphs. This approach allows us to forgo designing an auxiliary procedure, which makes the analysis somewhat more straightforward; see §1.3 for an informal overview of the argument.

In our first main result, we consider locally \(r\)-colorable graphs. A graph \(G\) is locally \(r\)-colorable if the subgraph induced by \(N(v)\) is \(r\)-colorable for each vertex \(v \in V(G)\) (note that \(K_3\)-free graphs are locally \(1\)-colorable). Alon [22] first considered the independence number \(\alpha(\cdot)\) of such graphs. He showed that an \(n\)-vertex locally \(r\)-colorable graph \(G\) of maximum degree \(\Delta\) satisfies \(\alpha(G) = \Omega\left(\frac{n}{\Delta}\frac{\log \Delta}{\log (r + 1)}\right)\). The analogous chromatic number bound was proved by Bonamy, Kelly, Nelson, and Postle [13] (see also [5] for an improvement in terms of the leading constant factor). We prove that this bound holds for fractional coloring in terms of the degeneracy as opposed to the maximum degree, which immediately yields a strengthening of Alon’s result; namely, it holds with \(\Delta\) replaced by the degeneracy \(d\).

Next, we turn our attention to \(r\)-uniform hypergraphs. Here, each edge contains exactly \(r\) vertices, the degree of a vertex is the number of edges containing it, and degeneracy is defined analogously (i.e., \(H\) is \(d\)-degenerate if every subgraph of \(H\) contains a vertex of degree at most \(d\)). We are interested in hypergraphs that have girth at least \(4\), i.e., no \(2\)- or \(3\)-cycles. Ajtai, Komlós, Pintz, Spencer, and Szemerédi [23] first considered the problem of finding large independent sets in high-girth hypergraphs. They showed that if an \(n\)-vertex \(r\)-uniform hypergraph has girth at least \(5\) (we say such a hypergraph is uncrowded), then it has an independent set of size at least \(c_rn\left(\frac{\log \Delta}{\Delta}\right)^{\frac{1}{r-1}}\), where \(\Delta\) is the maximum degree and \(c_r > 0\) is a constant depending only on the uniformity. Frieze and Mubayi [24] adapted Johansson’s entropy-based argument to prove that \(r\)-uniform hypergraphs of maximum degree \(\Delta\) having girth at least \(4\) have chromatic number at most \(c_r'\left(\frac{\Delta}{\log \Delta}\right)^{\frac{1}{r-1}}\). We prove that this bound holds for fractional coloring in terms of the degeneracy as opposed to the maximum degree, providing a strict generalization of the aforementioned result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi, and a strengthening of the bound on \(\chi_f(\cdot)\) implied by the result of Frieze and Mubayi.

Note that setting \(r = 2\) above recovers the bound in Theorem 1, providing an alternate proof of the result and yielding a substantial strengthening of it. Our proof of Theorem 3 is inspired by the approach of Frieze and Mubayi, who employ an entropy-based argument in conjunction with the Rödl nibble method. However, in our algorithm we process vertices one at a time as opposed to in batches as is the case in the nibble. This distinction requires several modifications representing the key technical novelty of our approach. We discuss this further in §1.3.

In [16], Martinsson and Steiner showed that a random sampling technique of Alon, Krivelevich, and Sudakov [6] allows one to extend Theorem 1 to locally sparse graphs. In a similar flavor, via random sampling as in Duke, Lefmann, and Rödl [25], one can extend Theorem 3 to the setting of linear hypergraphs, i.e., hypergraphs of girth at least \(3\); see also the discussion in [26].¹

We remark that Theorem 3 and Corollary 1 immediately imply lower bounds on the independence number of the hypergraph classes considered in terms of the degeneracy. In forthcoming work [28], building on the techniques introduced in this paper and those in recent work of Janzer, Methuku, and the author of this manuscript [14], we improve Iliopoulos’s bound on the independence number of uncrowded hypergraphs [29]² in the weaker setting of triangle-freeness, which in turn improves upon the seminal result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi [23] as well as a more recent result of Li and Postle [30].

1.2 Notation and terminology↩︎

Throughout the rest of the paper we use the following basic notation. For \(n \in \N\), we let \([n] \defeq \set{1, \ldots, n}\). For a hypergraph \(H\), its vertex and edge sets are denoted \(V(H)\) and \(E(H)\), respectively. For a vertex \(v \in V(H)\), \(\deg_H(v) \mathrel{\vcenter{:}}= |\set{e \in E(H)\,:\, v \in e}|\) denotes the degree of \(v\); we drop the subscript \(H\) when the context is clear. We say \(u \neq v\) is a neighbor of \(v\) if \(\set{u , v} \subseteq e\) for some edge \(e\in E(H)\). For a subset \(U \subseteq V(H)\), the subhypergraph induced by \(U\) is denoted by \(H[U]\).

We say an \(n\)-vertex hypergraph \(H\) is for \(d\in \N\) if there exists an ordering \((v_1, \ldots, v_n)\) of \(V(H)\) such that for each \(i\in [n]\), we have \(\deg_{H_i}(v_i) \leq d\), where \(H_i \mathrel{\vcenter{:}}= H[\set{v_1, \ldots, v_i}]\). Given a degeneracy ordering of \(H\), we let \(N_L(v_i)\) be the set of neighbors of \(v_i\) in the hypergraph \(H_i\); we call such vertices left-neighbors of \(v_i\). Similarly, we let \(N_R(v_i)\) be the vertices \(v_k\) such that \(v_i \in N_L(v_k)\), i.e., the right-neighbors of \(v_i\). Finally, given an edge \(e\) and a vertex \(u \in e\), we say that \(u\) is an internal vertex of \(e\) if \(u\in N_L(v)\) for some \(v \in e\), i.e., \(u\) is not the right-most vertex in \(e\) under the given degeneracy ordering.

Given a hypergraph \(H\) and parameters \(\alpha \in [0, 1]\) and \(q \in \N\), an of \(H\) is an assignment of sets \(S(v) \subseteq [q]\) to each vertex \(v \in V(H)\) such that

• \(|S(v)| \geq \alpha q\) for each vertex \(v\in V(H)\), and

• \(\cap_{u\in e}S(u) = \emptyset\) for each edge \(e \in E(G)\).

For a given \(q \in \N\), we let \[\alpha(H, q) \mathrel{\vcenter{:}}= \max\set{\alpha \in [0, 1]\,:\, H \text{ admits an (\alpha, q)-coloring}}.\] (The maximum is attained, as only values of the form \(\ell/q\) for integer \(\ell\) are relevant.) The fractional chromatic number can be formulated as follows: \[\chi_f(H) \mathrel{\vcenter{:}}= \inf\set{\alpha(H, q)^{-1}\,:\, q \in \N}.\] It is a simple exercise to show that this formulation is equivalent to the one mentioned at the beginning of this introduction.

Note the following observation in light of the above definition:

In our proofs, we will be using this alternate definition of fractional coloring in conjunction with the above observation.

1.3 Proof Overview↩︎

In this section, we provide an informal overview of our proof techniques. We first discuss the overarching algorithmic template and then provide details on the adaptation to each of our main results.

The algorithm takes as input a \(d\)-degenerate (hyper)graph \(H\) and a parameter \(q \in \N\) and outputs a collection of subsets \(\set{S(v) \subseteq [q]}_{v\in V(H)}\) such that \(\cap_{u \in e}S(u) = \emptyset\) for each edge \(e \in E(H)\). We initially assign each vertex-color pair \((v, c)\) a weight \(p_0(v, c) = \alpha\) for a well-chosen \(\alpha \in [0, 1]\) (our eventual bound on \(\chi_f(H)\) is \(\Theta(\alpha^{-1})\)). Iterating through the vertices in a degeneracy ordering of \(H\), we determine the set \(S(v_i)\) by selecting \(c\in [q]\) with a probability determined by \(p_{i-1}(v_i, c)\) (we are being intentionally vague at this point as there is a distinction in how we do so for each of our results). We update the weights \(p_i(v_k, c)\) for each \(k > i\) and \(c \in [q]\) according to the outcome of the event \(\set{c\in S(v_i)}\). In particular, the weight \(p_i(v_k, c)\) must be set to \(0\) if some edge \(e\ni v_k\) satisfies \(c\in \cap_{u \in e\setminus\{v_k\}}S(u)\). Additionally, we increase the weight for \(v_k \in N_R(v_i)\) if \(c \notin S(v_i)\) as we would like to make it more likely that \(c \in S(v_k)\) in this case. Our choice of parameters ensures that \(\E[p_i(v_k, c)\mid p_{i-1}(\cdot, \cdot)] = p_{i-1}(v_k, c)\). It then follows that \(\E[|S(v_k)|] = q\alpha\).

There is, however, a technical fiddle: what if \(p_i(v, c)\) becomes too large (e.g., \(p_i(v, c) > 1\))? As the weights represent a probability, we cannot allow this to occur. For a well-chosen \(\hat{p}\), we artificially set \(p_i(v, c) = \hat{p}\) for colors \(c\) satisfying \(p_i(v, c) > \hat{p}\) and label them as bad at \(v\). We store the bad colors in a set \(B_i(v)\) and these colors are never considered when determining \(S(v)\). As a result, we no longer have the nice property \(\E[p_i(v_k, c)\mid p_{i-1}(\cdot, \cdot)] = p_{i-1}(v_k, c)\). A standard trick, often referred to as an equalizing coin flip, allows us to achieve this property in the case that \(p_i(v, c) > \hat{p}\). See [31] for a more in-depth discussion of the necessity of thresholding \(p_i(v, c)\) in the context of coloring \(K_3\)-free graphs.

At this point, we can show the following: \[\E[|S(v_k)|] = \Theta\left(q\alpha - \hat{p} \E[|B_{k-1}(v_k)|]\right).\] To show \(\E[|S(v_k)|]\) is “large”, we must show that \(\E[|B_{k-1}(v_k)|]\) is “small.” This is where our entropy argument appears. In general, given a probability distribution \(\mathcal{D}\) over some finite set \(T\), the entropy of \(\mathcal{D}\) is the quantity \[Q(\mathcal{D}) = -\sum_{t\in T}\Pr_{X \sim\mathcal{D}}[X = t]\log \Pr_{X \sim\mathcal{D}}[X = t].\] Roughly speaking, \(Q(\mathcal{D})\) measures how widely the assignment probabilities vary—the more they vary, the smaller their entropy will be; the above is maximized when \(\mathcal{D}\) is the uniform distribution. We define the entropy at \(v\) after processing \(i\) vertices to be \[Q_i(v) = -\sum_{c = 1}^qp_i(v, c)\log p_i(v, c).\] Using the intuition from probability theory, if \(\E[Q_{k-1}(v_k)]\) is not too small, then the values of \(p_{k-1}(v_k, c)\) do not vary too much in expectation. As we have \(\sum_{c = 1}^q\E[p_i(v, c)] = q\alpha\), it would then follow that not very many of these values are as high as \(\hat{p}\) in expectation. We show that \(\E[Q_{k-1}(v_k)]\) is indeed not too small and so \(\E[|B_{k-1}(v_k)|]\) is “small,” as desired.

Once we show that \(\E[|S(v_k)|]\) is sufficiently large, we argue that \(|S(v_k)| = \Omega(\alpha q)\) with probability \(1 - \exp\paren{-\Omega(q/(nd^3))}\). The tool that we use is the following classical result, which is a consequence of Azuma’s inequality for Doob martingales (see [32]):

With this template in hand, for \(q = \poly(n, d)\), the above procedure yields a \(\poly(n, d)\)-time randomized algorithm \(\mathcal{A}\) to construct an \((\eta, q)\)-coloring \(S(\cdot)\) with probability \(1 - \exp\paren{-\Omega(n)}\) for some \(\eta = \Theta(\alpha)\). Consider the following polynomial time procedure: run \(\mathcal{A}\) to determine an \((\eta, q)\)-coloring \(S(\cdot)\); if the algorithm succeeds, sample \(\ell \in [q]\) uniformly at random and let \(I \mathrel{\vcenter{:}}= \{v \in V(H)\,:\, \ell \in S(v)\}\). It is not difficult to see that \(I\) is independent. Furthermore, we have \[\begin{align} \Pr[v\in I] &= \Pr[\mathcal{A} \text{ succeeds}]\Pr[\ell \in S(v) \mid \mathcal{A} \text{ succeeds}] \\ &\geq \paren{1 - \exp\paren{-\Omega(n)}}\eta, \end{align}\] for each vertex \(v \in V(H)\). By using this sampling approach, we satisfy the efficiency requirements and performance guarantees outlined in Theorems 2 and 3.³

In the remainder of this overview, we provide more details on how we select colors in \(S(v_i)\) and how we update the weights of vertex-color pairs for each of our main results.

Locally \(r\)-colorable graphs \(G\)↩︎

We select a color \(c\) to be in \(S(v_i)\) in two steps: first, we activate \(c\) with probability \(p_{i-1}(v_i, c)\); then, we select an activated color \(c\) with probability \(1/2\). We update the weights \(p_i(v_k, c)\) for each \(v_k\in V(G)\) according to the outcome of the event \(\set{c\in S(v_i)}\). In particular, if \(c \in S(v_i)\), then we set \(p_i(v_k, c) = 0\) for each \(v_k \in N_R(v_i)\); this ensures that \(S(u) \cap S(v) = \emptyset\) whenever \(uv \in E(G)\). If \(c\) is not activated, we do not change any weights. If \(c\) is activated but not selected, we sample a color class \(J \subseteq N_R(v_i)\) from a proper \(r\)-coloring of \(G[N_R(v_i)]\) uniformly at random, increase the weights of the the vertex-color pairs \((v_k, c)\) for \(v_k \in J\) by a factor of \(2r\) (this makes it more likely that \(c\) is selected when considering \(v_k\)), and set the weights of all other pairs \((v_k, c)\) to \(0\) for \(v_k \in N_R(v_i) \setminus J\).

Let us briefly motivate the update step above. One can view activating \(c\) as considering \(c\) to be a “good” addition to \(S(v_i)\). In the event that \(c\) is activated but not selected, we would like a large subset of \(N_R(v_i)\) to select \(c\), i.e., a large “certificate” for the outcome \(c \notin S(v_i)\). Such a subset must be independent and so we increase the weight for \(c\) at vertices contained in a “large” independent set in \(N_R(v_i)\).⁴

For the proof of Theorem 2, we use the threshold \(\hat{p} = 1\) and define equalizing coin flips accordingly. See Algorithm [algorithm:32fcp] for a formal description of the procedure.

High-girth hypergraphs \(H\)↩︎

Here, we determine the set \(S(v_i)\) by selecting \(c\in [q]\) with probability \(p_{i-1}(v_i, c)\). We update the weights \(p_i(v_k, c)\) for each \(k > i\) and \(c \in [q]\) according to the outcome of the event \(\set{c\in S(v_i)}\). More formally, let \(e\) be an edge containing \(\set{v_i, v_k}\) such that \(v_k\) is the right-most vertex in \(e\). (Note that \(e\) is unique since \(H\) is linear. Furthermore, edges containing \(v_k\) as the right-most vertex are the only ones that can “kill” the color \(c\) at \(v_k\), i.e., cause the outcome \(p_{k-1}(v_k, c) = 0\).) Additionally, let \(f \subseteq e\) consist of the vertices of \(e\) that appear before \(v_i\) in the degeneracy ordering; see Fig. 1 for an example. We update \(p_i(v_k, c)\) as follows: \[\begin{align} \label{eq:32update32intro} p_i(v_k, c) = \left\{\begin{array}{cc} p_{i-1}(v_k, c) & \text{if } c \notin S(u) \text{ for some } u \in f; \\[2em] \dfrac{p_{i-1}(v_k, c)}{1 - \prod_{u \in e \setminus (f \cup \{v_k\})}p_{i-1}(u)} & \text{if } c \notin S(v_i); \\[2em] p_{i-1}(v_k, c)\left(\dfrac{1 - \prod_{u \in e \setminus (f \cup \{v_i, v_k\})}p_{i-1}(u)}{1 - \prod_{u \in e \setminus (f \cup \{v_k\})}p_{i-1}(u)}\right) & \text{otherwise}. \end{array}\right. \end{align}\tag{1}\] Note that the last case implies that if \(c\in S(u)\) for every \(u \in e \setminus \{v_k\}\), then \(p_{k-1}(v_k, c) = 0\); i.e., \(c\) is not selected in \(S(v_k)\).

Let us motivate this update rule. We begin with a brief description of the approach of Frieze and Mubayi [27] where they prove a bound on the chromatic number of hypergraphs of girth at least \(4\). In their paper, they employ a variant of the Rödl nibble method (see [33] for a survey of applications of this method to hypergraph coloring). Roughly speaking, the method proceeds in stages: during stage \(i\), each uncolored vertex \(v\) selects a subset of colors \(S_i(v) \subseteq [q]\) by including each color independently with probability \(\eps\,p_{i-1}(v, c)\), and we update weights of vertex-color pairs accordingly (i.e., if \(c\) is selected at every \(u \in e \setminus \{v\}\) for some \(v\in e\), then we must set \(p_{i}(v, c) = 0\)); a vertex is colored if it selects a nonempty subset.⁵ Note that the probability that \(c\) is not killed at \(v\) due to an edge \(e\ni v\) during stage \(i\) is \(q_{e, i}(v, c) \mathrel{\vcenter{:}}= 1 - \prod_{u \in e\setminus \set{v}}(\eps\,p_{i-1}(u, c))\). The hope is that \(p_{i}(v, c)\) remains unchanged in expectation motivating the update rule \(p_i(v, c) = p_{i-1}(v, c)/\prod_{e \ni v}q_{e, i}(v, c)\), which is precisely the rule used by Frieze and Mubayi. Unfortunately, this rule does not work in our setting as we are processing vertices one at a time as opposed to in batches. More precisely, during the \(i\)-th stage of the nibble, every uncolored vertex makes some random choices, whereas during the \(i\)-th iteration of our algorithm, exactly one vertex makes random choices. Furthermore, a vertex is processed exactly once in our algorithm, whereas in the nibble method, it is repeatedly processed until it selects a nonempty subset of colors during some stage. These distinctions necessitate a different update procedure.

Let us now return our attention to the setting of our update rule. I.e., we are processing a vertex \(v_i\), and \(v_k\in N_R(v_i)\) is such that \(e \ni \set{v_i, v_k}\). Additionally, let \(f \subseteq e\) consist of the vertices of \(e\) that appear before \(v_i\) in the degeneracy ordering. The probability that \(c\) is not killed at \(v_k\) due to \(e\) in the algorithm is roughly \(q_{e}(v_k, c) \mathrel{\vcenter{:}}= 1 - \prod_{v_j \in e\setminus \set{v_k}}p_{j-1}(v_j, c)\). As we cannot determine \(q_{e}(v_k, c)\) a-priori, our update rule enables a semblance of a “running computation” of \(q_{e}(v_k, c)\). Indeed, one can view the rule as related to the conditional probability that \(e\) kills \(c\) at \(v_k\) given the outcomes of vertices in \(e\) processed thus far; i.e., we have \[\Pr[e \text{ does not kill c at } v_k \mid \forall u \in f,\, c\in S(u)] \approx 1 - \prod_{u \in e \setminus (f \cup \{v_k\})}p_{i-1}(u,c),\] and \[\Pr[e \text{ does not kill c at } v_k \mid \forall u \in f\cup \{v_i\},\, c\in S(u)] \approx 1 - \prod_{u \in e \setminus (f \cup \{v_i,v_k\})}p_{i-1}(u,c).\] Additionally, we have \[\Pr[e \text{ does not kill c at } v_k \mid \exists u \in f,\, c\notin S(u)] = 1,\] covering all possible cases.

For the proof of Theorem 3, we use the threshold \(\hat{p} = 1/2\). A key step in the proof of Theorem 2 relies on the fact that a weight either increases, remains the same, or is set to \(0\) during each iteration (see Lemma 4). We no longer have this property as a result of the final case in the update process 1 . Therefore, we need an additional threshold step that ensures a weight does not drop too much.⁶ We ensure all non-zero weights are at least \(\alpha^{1+o(1)}\), and define additional equalizing coin flips accordingly. See Algorithm [algorithm:32fcp32hypergraph] for a formal description of the procedure.

1.4 Open problems↩︎

We conclude this introduction with a few potential avenues for future work. In this paper, we introduce a new entropy-based approach toward fractional colorings of \(d\)-degenerate (hyper)graphs. The key technical novelty lies in the design and analysis of the coloring algorithm. At its core, the algorithm works as follows: iteratively process vertices in an order determined by the degeneracy; when processing \(v_i\), determine a sufficiently large subset of colors \(S(v_i) \subseteq [q]\) such that \(\cap_{u\in e}S(u) = \emptyset\) for each edge \(e \in E(H[\set{v_1, \ldots, v_i}])\), and update the parameters associated with the right-neighbors \(v_k\) of \(v_i\), while carefully tracking the impact of these updates on the eventual set \(S(v_k)\). This procedure provides a framework to tackle other problems regarding \(d\)-degenerate hypergraphs, so it is of independent interest.

In follow-up work to [2], Johansson showed that \(K_r\)-free graphs \(G\) of maximum degree \(\Delta\) have chromatic number \(O_r\left(\frac{\Delta \log\log \Delta}{\log \Delta}\right)\) [34], extending a result of Shearer [35] on the independence number of such graphs (see [3], [4], [9] for more recent proofs with improvements in terms of the leading constant factor; see also [5], [13] for an asymptotic improvement in the regime \(r = \omega\left(\frac{\log \Delta}{\log \log \Delta}\right)\)). He employs an entropy-based argument to prove the result (see [36] for a simplified exposition of the argument). Unfortunately, the same bound does not hold in general for \(\chi_f(\cdot)\) with \(\Delta\) replaced by the degeneracy \(d\). Indeed, Bradač, Fox, Steiner, Sudakov, and Zhang recently showed the following:

\(\chi_f(G) \geq c_r\frac{d}{\log^{(r-2)}d}\) for some constant \(c_r > 0\) [21] Here, \(\log^{(b)}(\cdot)\) denotes the \(b\)-fold iterated logarithm function defined as \(\log^{(b)}(x) \mathrel{\vcenter{:}}= \log(\log^{(b-1)}(x))\) and \(\log^{(1)}(x) = \log x\). They ask whether \(d\)-degenerate \(K_r\)-free graphs \(G\) satisfy \(\chi_f(G) = o_r(d)\) for \(r\geq 4\) in general [21]. It is possible that the techniques described in this paper could yield an affirmative answer to this question.

Subsequent to [27], Cooper and Mubayi studied the chromatic number of \(3\)-uniform triangle-free hypergraphs [37]; a triangle in a hypergraph is a collection of three edges \(e, f, g\) and three vertices \(u, v, w\) such that \(u \in e\cap f, v \in f\cap g, w \in e\cap g,\) and \(\{u, v, w\}\cap e \cap f \cap g = \emptyset\). They showed that \(3\)-uniform triangle-free hypergraphs \(H\) of maximum degree \(\Delta\) satisfy \(\chi(H) = O\left(\sqrt{\frac{\Delta}{\log \Delta}}\right)\). Li and Postle [30] recently extended this result to all uniformities, showing that \(r\)-uniform triangle-free hypergraphs \(H\) of maximum degree \(\Delta\) satisfy \(\chi(H) \leq c_r\left(\frac{\Delta}{\log \Delta}\right)^{\frac{1}{r-1}}\) for some constant \(c_r > 0\).⁷ We conjecture the same result holds for fractional coloring with \(\Delta\) replaced by the degeneracy \(d\).

The update procedure in our proof of Theorem 3 heavily relies on the fact that there is a unique edge containing \(v_i\) and \(v_k\). Indeed, so do a number of other arguments in our proof. As triangle-free hypergraphs need not be linear, proving Conjecture [conj:32hypergraph] would require substantial new ideas.

Structure of the paper↩︎

The remainder of the paper is structured as follows: in §2, we prove Theorem 2; and in §3, we prove Theorem 3.

2 Graphs with bounded local chromatic number: proof of Theorem 2↩︎

In this section, we will prove the following result, which bounds the fractional chromatic number of \(d\)-degenerate locally \(r\)-colorable graphs.

We focus on the bound on \(\chi_f(\cdot)\) as the algorithmic implication is fairly straightforward (see p.  for an outline of the proof). We further split this section into three subsections. In the first, we describe our coloring procedure formally and state two key results associated with the procedure, which we prove in the subsequent subsections.

2.1 Algorithm description↩︎

In this section, we will describe our coloring procedure (see Algorithm [algorithm:32fcp]). The algorithm takes as input an \(n\)-vertex \(d\)-degenerate locally \(r\)-colorable graph \(G\) and parameters \(q\in \N, \eps > 0\), and outputs a collection of subsets \(\set{S(v) \subseteq [q]}_{v\in V(G)}\) such that \(S(u) \cap S(v) = \emptyset\) whenever \(uv \in E(G)\). We refer the reader to §1.3 for an informal overview of the procedure. Let us now provide a formal description of the algorithm.

A few remarks are in order. First, note that Algorithm [algorithm:32fcp] can be implemented in \(O(ndq)\) time. Additionally, it is easy to see that our update steps ensure \(S(v_i) \cap S(v_j) = \emptyset\) whenever \(v_iv_j \in E(G)\). Furthermore, as a result of Step [step:32not32activated], once a color is bad at a vertex \(v_j\), it remains bad at \(v_j\). Finally, we note that the probabilities \(\mu_{i, k, c}\) are well-defined. Indeed, \(\mu_{i, k, c} \in [0, 1]\) as long as \(p_{i-1}(v_k, c) \in [1/(2r),\, 1]\) (which is the case when we are in Step [step:32ub32violated32r]).

It suffices to show that with high probability, \(|S(v_k)|\) is large for all \(k\). We will do so through two key lemmas.

We defer the proofs of these lemmas to §2.2 and §2.3, respectively. With these results in hand, we have the following: \[\Pr\left[\exists k \text{ s.t. }|S(v_k)| \leq \frac{q\,\log d}{(8+\eps)\,d\,\log(2r)}\right] \leq \Pr\left[\exists k \text{ s.t. }|S(v_k)| \leq \frac{(1-\eps/20)q\alpha}{4}\right] \leq n\exp\left(-\Omega\left(\frac{\eps^2\,q\,\alpha^2}{nd}\right)\right).\] The above tends to \(0\) as \(q \to \infty\), completing the proof of Theorem 2 as a result of Observation [obs:32fractional32coloring].

2.2 Expectation of \(|S(v_k)|\): proof of Lemma 1↩︎

Note the following: \[\begin{align} \label{eq:32exp32size32S40vk41} \E[|S(v_k)|] = \frac{1}{2}\E\left[\sum_{c \in [q] \setminus B_{k-1}(v_k)}p_{k-1}(v_k, c)\right] = \frac{1}{2}\left(\E\left[\sum_{c= 1}^qp_{k-1}(v_k, c)\right] - \E[|B_{k-1}(v_k)|]\right). \end{align}\tag{2}\] In the remainder of this section, we will provide bounds on each of the terms on the right. To this end, we define the following quantities: \[\begin{align} P_i(v_k) &= \sum_{c = 1}^qp_i(v_k, c), & &\text{for } 0 \leq i < k \leq n; \\ H_i(v_j, v_k) &= \mathbf{1}\{v_jv_k \in E(G)\}\sum_{c \notin B_i(v_j)}p_i(v_j, c)p_i(v_k, c), & &\text{for } 0 \leq i < j < k \leq n; \\ Q_i(v_k) &= -\sum_{c = 1}^qp_i(v_k, c)\log p_i(v_k, c) & &\text{for } 0 \leq i < k \leq n. \end{align}\] We refer to \(P_i(v_k)\) as the potential of \(v_k\), \(H_i(v_j, v_k)\) as the energy of the pair \((v_j, v_k)\), and \(Q_i(v_k)\) as the entropy of \(v_k\). We begin by computing the expected values of each of the above random variables.

With the above in hand, let us show that \(|B_{k-1}(v_k)|\) is small in expectation.

Combining 2 with Lemmas 3 and 4, we have \[\E[|S(v_k)|] = \frac{1}{2}(\E[P_{k-1}(v_k)] - \E[|B_{k-1}(v_k)|]) \geq \frac{1}{2}\left(q\alpha - \frac{q\alpha}{2}\right) = \frac{q\alpha}{4},\] completing the proof of Lemma 1.

2.3 Concentration of \(|S(v_k)|\): proof of Lemma 2↩︎

In this section, we will prove Lemma 2, i.e., we show that the sizes of the sets \(S(v_k)\) are highly concentrated around their expected values. For the reader’s convenience, we restate the lemma.

As mentioned in §1.3, we aim to apply Theorem 4 to concentrate \(|S(v_k)|\). To this end, we define a few auxiliary random variables. For each \(v_i \in V(G)\), \(c \in [q]\), and \(v_j\in N_R(v_i)\), let \(a_{i, c}', s_{i, c}', \mu_{i, j, c}'\) be independent uniform random variables on the interval \([0, 1]\) and let \(j_{i, c} \in [r]\) be chosen uniformly at random. We modify Algorithm [algorithm:32fcp] as follows: \(a_{i, c} = \mathbf{1}\set{a_{i, c}' \leq p_{i-1}(v_i, c)}\), \(s_{i, c} = \mathbf{1}\set{s_{i, c}' \leq1/2}\), and let the equalizing coin flip outcomes be defined in the same way in terms of \(\mu_{i, j, c}'\); additionally, let \(J_{i, c} = \phi_{v_i}^{-1}(j_{i, c}) \cap N_R(v_i)\). It is easy to see that the analysis of §2.2 remains unchanged. Furthermore, we claim that we may apply Theorem 4 to concentrate \(|S(v_k)|\) with the at most \(2ndq\) trials \(\set{a_{i, c}', s_{i, c}', j_{i, c}, \mu_{i, j, c}'}_{v_i \in V(G),\, v_j\in N_R(v_i),\, c\in [q]}\) and \(\zeta = 1\). Indeed, changing the outcome of \(a_{i, c}'\), \(s_{i, c}'\), \(\mu_{i, j, c}'\), or \(j_{i, c}\) for \(i < j \leq k\) can only possibly affect the value of \(p_{k-1}(v_k, c)\). In particular, it may change the inclusion (or non-inclusion) of \(c\) in \(S(v_k)\). Similarly, changing the outcome of \(a_{k, c}'\), \(\eta_{k, c}'\), or \(j_{k, c}\) can affect \(|S(v_k)|\) by at most \(1\). Finally, changing the outcome of \(a_{i, c}'\), \(s_{i, c}'\), or \(j_{i, c}\) for \(i > k\) has no effect on the random variable \(|S(v_k)|\).

Applying Theorem 4 with \(s = 2ndq\), \(t = \frac{\eps\,q\,\alpha}{80}\), and \(\zeta = 1\), we obtain the following as a result of Lemma 1: \[\begin{align} \Pr\left[|S(v_k)| \leq (1-\eps/20)q\alpha/4\right] &\leq \Pr\left[|S(v_k)| \leq \E[|S(v_k)|] - \frac{\eps\,q\,\alpha}{80}\right] \\ &\leq \Pr\left[||S(v_k)| - \E[|S(v_k)|]| \geq \frac{\eps\,q\,\alpha}{80}\right] \\ &\leq \exp\left(-\frac{\eps^2\,q\,\alpha^2}{25600nd}\right), \end{align}\] completing the proof of Lemma 2.

3 High-girth hypergraphs: proof of Theorem 3↩︎

In this section, we will prove Theorem 3, which bounds the fractional chromatic number of \(d\)-degenerate \(r\)-uniform hypergraphs of girth at least \(4\). The special case \(r = 2\) yields an alternate proof of Martinsson and Steiner’s result (Theorem 1) for \(K_3\)-free graphs. We restate the result for the reader’s convenience.

Once again, we focus on the bound on \(\chi_f(\cdot)\) as the algorithmic implication is fairly straightforward (see p.  for an outline of the proof). While we prove our result for arbitrary \(r \geq 2\), we remark that the argument is considerably simpler for \(r=2\) (we will specify which key technical condition can be avoided in this case). We further split this section into three subsections. In the first, we describe our coloring procedure formally and state two key results associated with the procedure, which we prove in the subsequent subsections.

3.1 Algorithm description↩︎

In this section, we will describe our coloring procedure (see Algorithm [algorithm:32fcp32hypergraph]). The algorithm takes as input an \(n\)-vertex \(r\)-uniform \(d\)-degenerate hypergraph \(H\) having girth at least \(4\) and parameters \(q \in \N, \eps > 0\), and outputs a collection of subsets \(\set{S(v) \subseteq [q]}_{v\in V(H)}\) such that \(\cap_{u \in e}S(u) = \emptyset\) for each \(e \in E(H)\). Before we state the algorithm rigorously, we provide an informal overview. We initially assign each vertex-color pair \((v, c)\) a weight \(p_0(v, c) = \alpha\). Iterating through the vertices in a degeneracy ordering of \(H\), we determine the set \(S(v_i)\) by selecting \(c\in [q]\) with probability \(p_{i-1}(v_i, c)\). We update the weights \(p_i(v_k, c)\) for each \(k > i\) and \(c \in [q]\) according to the outcome of the event \(\set{c\in S(v_i)}\). More formally, let \(v_k\) be a right-neighbor of \(v_i\), and let \(e\) be the unique edge containing \(\set{v_i, v_k}\). Additionally, let \(f \subseteq e\) consist of the vertices of \(e\) that appear before \(v_i\) in the degeneracy ordering. We update \(p_i(v_k, c)\) as follows: \[\begin{align} \label{eq:32hypergraph32update} p_i(v_k, c) = \left\{\begin{array}{cc} p_{i-1}(v_k, c) & \text{if } c \notin S(u) \text{ for some } u \in f; \\[1.5em] \dfrac{p_{i-1}(v_k, c)}{1 - \prod_{u \in e \setminus (f \cup \{v_k\})}p_{i-1}(u)} & \text{if } c \notin S(v_i); \\[2em] p_{i-1}(v_k, c)\left(\dfrac{1 - \prod_{u \in e \setminus (f \cup \{v_i, v_k\})}p_{i-1}(u)}{1 - \prod_{u \in e \setminus (f \cup \{v_k\})}p_{i-1}(u)}\right) & \text{otherwise}; \end{array}\right. \end{align}\tag{4}\] We refer the reader to §1.3 for a motivation to the above update rule. Finally, we ensure all non-zero weights are at most \(1/2\) and at least \(\alpha^{1+\kappa}\) for \(\kappa = \eps/(1000r)\), and define equalizing coin flips accordingly.⁸

Let us now provide a formal description of the algorithm.

A few remarks are in order. First, note that Algorithm [algorithm:32fcp32hypergraph] can be implemented in \(O(rndq)\) time. Additionally, given an edge \(e = \set{v_{i_1}, \ldots, v_{i_r}}\) such that \(i_1 < i_2 < \cdots < i_r\), one can verify that \(X_{i_{r-1}, i_r, c}' = 1\). In particular, \(p_{i_r - 1}(v_{i_r}, c) = 0\) if \(c \in \cap_{l < r}S(v_{i_l})\). This ensures \(\cap_{u \in e}S(u) = \emptyset\) for each \(e \in E(H)\). Furthermore, we note that the probabilities \(\mu_{i, k, c}\) and \(\ell_{i, k, c}\) are well-defined. Indeed, \(\mu_{i, k, c} \leq 1\) always, and \(\mu_{i, k, c} > 0\) if and only if \(p_{i-1}(v_k, c) > (1-X_{i, k, c})/2\). Similarly, \(\ell_{i, k, c} \geq 0\) always and \(\ell_{i, k, c} < 1\) if and only if \(p_{i-1}(v_k, c)(1-X_{i, k, c}') < (1-X_{i, k, c})\alpha^{1+\kappa}\). Finally, we note that by our choice of lower and upper bounds on \(p_i(\cdot, \cdot)\), we can never have both \[0 < p_{i-1}(v_k, c)(1-X_{i, k, c}') < (1-X_{i, k, c})\alpha^{1+\kappa}, \qquad \text{and} \qquad p_{i-1}(v_k, c) > (1-X_{i, k, c})/2,\] for \(d\) sufficiently large. In particular, Algorithm [algorithm:32fcp32hypergraph] covers all cases.

It suffices to show that with high probability, \(|S(v_k)|\) is large for all \(k\). We will do so through two key lemmas.

We defer the proofs of these lemmas to §3.2 and §3.3, respectively. With these results in hand, we have the following for sufficiently large \(q\): \[\begin{align} \Pr\left[\exists k \text{ s.t. }|S(v_k)| \leq \frac{q}{(1+\eps)}\left(1 - \frac{1}{r}\right)\left(\dfrac{\log d}{r(r-1)^2d}\right)^{\frac{1}{r-1}}\right] &\leq \Pr\left[\exists k \text{ s.t. }|S(v_k)| \leq (1-\eps/20)\left(1 - \frac{1}{r}\right)q\alpha\right] \\ &\leq n\exp\left(-\Omega\left(\frac{\eps^2\,q\,\alpha^2}{nd}\right)\right). \end{align}\] The above tends to \(0\) as \(q \to \infty\), completing the proof of Theorem 3 as a result of Observation [obs:32fractional32coloring].

3.2 Expectation of \(|S(v_k)|\): proof of Lemma 5↩︎

Note the following: \[\begin{align} \label{eq:32exp32size32S40vk4132hypergraph} \E[|S(v_k)|] = \E\left[\sum_{c\notin B_{k-1}^\mu(v_k) \cup B_{k-1}^\ell(v_k)}p_{k-1}(v_k, c)\right] \geq \E\left[\sum_{c= 1}^qp_{k-1}(v_k, c)\right] - \frac{\E[|B_{k-1}^\mu(v_k)|]}{2} - q\alpha^{1+\kappa}, \end{align}\tag{5}\] where we use the trivial bound \(|B_{k-1}^\ell(v_k)| \leq q\). In the remainder of this section, we will provide bounds on each of the expectation terms on the right.

As in the proof of Theorem 2, we will define certain quantities to assist with our proof. First, the potential and entropy of a vertex are defined identically as in §2: \[\begin{align} P_i(v_k) &= \sum_{c = 1}^qp_i(v_k, c), & &\text{for } 0 \leq i < k \leq n; \\ Q_i(v_k) &= -\sum_{c = 1}^qp_i(v_k, c)\log p_i(v_k, c) & &\text{for } 0 \leq i < k \leq n. \end{align}\] The definition of the energy of a pair of vertices is rather more involved. Let \(0 \leq i < j < k \leq n\) and let \(e\) be an edge containing \(v_j\) and \(v_k\) such that \(v_k\) is the rightmost vertex of \(e\). Let \(f \subseteq e\) be the vertices \(v_\ell \in e\) such that \(\ell \leq i\). We define \[H_i(v_j, v_k) = \sum_{c = 1}^q\mathbf{1}\set{\forall v \in f,\, c \in S(v)\text{ and } c \notin B_{i}^\mu(v_j)\cup B_{i}^\ell(v_j) \cup B_{i}^\mu(v_k)\cup B_{i}^\ell(v_k)}\prod_{u \in e \setminus f}p_i(u, c).\]

We now compute the expected values of each of the above random variables. To assist with the proofs, we let \(\Omega_i\) denote the outcomes of the random choices at \(v_i\), i.e., the activations and (possible) equalizing coin flips that occur when processing \(v_i\). We begin with the potential of a vertex.

Next, let us consider the energy of a pair of vertices.

Finally, we consider the entropy at each vertex.

With the above in hand, let us show that \(|B_{k-1}(v_k)|\) is small in expectation.

Combining 5 with Lemmas 7 and 10, we have \[\begin{align} \E[|S(v_k)|] &\geq \E[P_{k-1}(v_k)] - \frac{1}{2}\E[|B_{k-1}(v_k)|] - q\alpha^{1+\kappa} \\ &\geq (1-\eps /50)\left(1 - \frac{1}{r}\right)q\alpha, \end{align}\] completing the proof of Lemma 5.

3.3 Concentration of \(|S(v_k)|\): proof of Lemma 6↩︎

In this section, we will prove Lemma 6, i.e., we show that the sizes of the sets \(S(v_k)\) are highly concentrated around their expected values. For the reader’s convenience, we restate the lemma.

As in the proof of Theorem 2, we aim to apply Theorem 4 to concentrate \(|S(v_k)|\). To this end, we define a few auxiliary random variables. For each \(v_i \in V(H)\), \(c \in [q]\), and \(v_j \in N_R(v_i)\), let \(a_{i, c}'\), \(\mu_{i, j, c}'\), \(\ell_{i, j, c}'\) be independent uniform random variables on the interval \([0, 1]\). We modify Algorithm [algorithm:32fcp32hypergraph] as follows: let \(a_{i, c} = \mathbf{1}\set{a_{i, c}' \leq p_{i-1}(v_i, c)}\), and let the equalizing coin flip outcomes be defined in the same way in terms of \(\mu_{i, j, c}'\) and \(\ell_{i, j, c}'\). It is easy to see that the analysis of §3.2 remains unchanged. Furthermore, we claim that we may apply Theorem 4 to concentrate \(|S(v_k)|\) with the at most \(3ndq\) trials \(\set{a_{i, c}', \mu_{i, j, c}', \ell_{i, j, c}'}_{v_i \in V(H),\, v_j \in N_R(v_i),\, c\in [q]}\) and \(\zeta = 1\). Indeed, changing the outcome of \(a_{i, c}'\), \(\mu_{i, j, c}'\), or \(\ell_{i, j, c}'\) for \(i < j \leq k\) can only possibly affect the value of \(p_{k-1}(v_k, c)\). In particular, it may change the inclusion (or non-inclusion) of \(c\) in \(S(v_k)\). Similarly, changing the outcome of \(a_{k, c}'\) can affect \(|S(v_k)|\) by at most \(1\). Furthermore, changing the outcome of \(a_{i, c}'\) for \(i > k\) has no effect on the random variable \(|S(v_k)|\).

Applying Theorem 4 with \(s = 3ndq\), \(t = \frac{\eps\,q\,\alpha}{40}\), and \(\zeta = 1\), we obtain the following as a result of Lemma 5: \[\begin{align} \Pr\left[|S(v_k)| \leq (1-\eps /20)\left(1 - \frac{1}{r}\right)q\alpha\right] &\leq \Pr\left[|S(v_k)| \leq \E[|S(v_k)|] - \frac{\eps\,q\,\alpha}{40}\right] \\ &\leq \Pr\left[||S(v_k)| - \E[|S(v_k)|]| \geq \frac{\eps\,q\,\alpha}{40}\right] \\ &\leq \exp\left(-\frac{\eps^2\,q\,\alpha^2}{9600nd}\right), \end{align}\] completing the proof of Lemma 6.

Acknowledgments↩︎

We thank Peter Bradshaw, Minh-Quan Vo, and Jing Yu for helpful discussions. We also thank Ewan Davies and Abhishek Methuku for helpful comments on an earlier version of this manuscript.

References↩︎

---

1. We note that this reduction appears in [27] as well to prove a bound on the chromatic number of linear hypergraphs.↩︎

2. We note that the stated result is in terms of the chromatic number, however, one obtains the independence number bound as a simple corollary.↩︎

3. We omit the formal details of this derivation for brevity, as the arguments are fairly straightforward.↩︎

4. We remark that our argument holds (with minor modifications) if the graph were locally fractionally \(r\)-colorable as opposed to locally \(r\)-colorable.↩︎

5. The actual procedure differs slightly from this description, however, these distinctions are unimportant for our overview.↩︎

6. In the special case \(r = 2\), the desired property still holds; consequently, the analysis circumvents the need for a lower bound threshold, making the arguments considerably simpler.↩︎

7. We note that they prove a more general result for hypergraphs of rank \(r\), i.e., where each edge contains at most \(r\) vertices.↩︎

8. This is the distinction between the case \(r = 2\) and \(r \geq 3\). In the former case, the final update rule in 4 just sets \(p_i(v_k, c) = 0\) and so we do not need a lower bound threshold.↩︎