Proper Conflict-free Coloring of
Graphs with Large Maximum Degree

Daniel W. Cranston Department of Computer Science, Virginia Commonwealth University, Richmond, VA, USA; [email protected]. Chun-Hung Liu Department of Mathematics, Texas A&M University, College Station, TX, USA; [email protected]. Partially supported by NSF under award DMS-1954054 and CAREER award DMS-2144042.

Abstract

A proper coloring of a graph is conflict-free if, for every non-isolated vertex, some color is used exactly once on its neighborhood. Caro, Petruševski, and Škrekovski proved that every graph $G$ has a proper conflict-free coloring with at most $5\Delta(G)/2$ colors and conjectured that $\Delta(G)+1$ colors suffice for every connected graph $G$ with $\Delta(G)\geqslant 3$ . Our first main result is that even for list-coloring, $\left\lceil 1.6550826\Delta(G)+\sqrt{\Delta(G)}\right\rceil$ colors suffice for every graph $G$ with $\Delta(G)\geqslant 10^{8}$ ; we also prove slightly weaker bounds for all graphs with $\Delta(G)\geqslant 750$ . These results follow from our more general framework on proper conflict-free list-coloring of a pair consisting of a graph $G$ and a “conflict” hypergraph $\mathcal{H}$ . As another corollary of our results in this general framework, every graph has a proper $(\sqrt{30}+o(1))\Delta(G)^{1.5}$ -list-coloring such that every bi-chromatic component is a path on at most three vertices, where the number of colors is optimal up to a constant factor. Our proof uses a fairly new type of recursive counting argument called Rosenfeld counting, which is a variant of the Lovász Local Lemma or entropy compression.

We also prove an asymptotically optimal result for a fractional analogue of our general framework for proper conflict-free coloring for pairs of a graph and a conflict hypergraph. A corollary states that every graph $G$ has a fractional $(1+o(1))\Delta(G)$ -coloring such that every fractionally bi-chromatic component has at most two vertices. In particular, it implies that the fractional analogue of the conjecture of Caro et al. holds asymptotically in a strong sense.

1 Introduction

Motivated by a frequency assignment problem in cellular networks, Even, Lotker, Ron, and Smorodinsky [8] introduced conflict-free coloring of hypergraphs. A coloring^†^†margin: coloring of a graph or a hypergraph $G$ is a map $\varphi\colon V(G)\to\mathbb{Z}^{+}$ . A coloring $\varphi$ of a hypergraph $\mathcal{H}$ is conflict-free^†^†margin: conflict-free if for every (non-empty)¹¹1In this paper, we assume that every edge of a hypergraph is non-empty, though the edge set can be empty. $e\in E(\mathcal{H})$ , there exists a color that is used exactly once by $\varphi$ on $e$ . Pach and Tardos [17] studied this notion and proved that every hypergraph with fewer than ${s\choose 2}$ edges (for some integer $s$ ) has a conflict-free coloring with fewer than $s$ colors. Note that being conflict-free on an edge of size 2 is equivalent to the vertices in this edge using distinct colors. Hence, the result of Pach and Tardos is optimal, as witnessed by complete 2-uniform hypergraphs. Kostochka, Kumbhat, and Łuczak [13] further studied conflict-free coloring for uniform hypergraphs.

A coloring $\varphi$ of a graph $G$ is proper^†^†margin: proper if $\varphi(v)\neq\varphi(w)$ for all $vw\in E(G)$ . As we have seen, being conflict-free on every edge of a hypergraph with size 2 is equivalent to being a proper coloring of a graph. So it is more convenient to consider the following notion, so that we can focus on edges with larger size. For a graph $G$ and a hypergraph $\mathcal{H}$ with $V(G)=V(\mathcal{H})$ , a proper conflict-free coloring of $(G,\mathcal{H})$ ^†^†margin: proper conflict-free coloring of $(G,\mathcal{H})$ is a proper coloring of $G$ that is also a conflict-free coloring of $\mathcal{H}$ . This notion is general: given a graph $G$ , by appropriately defining an associated hypergraph $\mathcal{H}$ , every proper conflict-free coloring of $(G,\mathcal{H})$ is an acyclic coloring, a star coloring, and a frugal coloring of $G$ , respectively.²²2Always $V(\mathcal{H})=V(G)$ and for acyclic, star, and $k$ -frugal coloring we add an edge to $\mathcal{H}$ with vertex $S$ , respectively, when $S$ spans a cycle, $S$ spans a $P_{4}$ , or $S$ is a subset of size $k+1$ of the open neighborhood of some vertex in $G$ . (Note that proper conflict-free coloring is not equivalent to these other notions, but is in fact strictly more general.) So an upper bound for the number of colors used in a proper conflict-free coloring for $(G,\mathcal{H})$ provides an upper bound for those extensively studied notions in graph coloring. On the other hand, for acyclic coloring [1], star coloring [10], and $k$ -frugal coloring (for fixed $k$ ) [12], the numbers of required colors are known to be superlinear in the graph’s maximum degree. So an upper bound for proper conflict-free coloring for a general pair $(G,\mathcal{H})$ cannot be linear in the maximum degree of $G$ .

In this paper we study sufficient conditions to have a proper conflict-free coloring for $(G,\mathcal{H})$ with a number of colors that is a linear in the maximum degree of $G$ . One such result is related to conflict-free proper coloring of graphs, which was introduced by Fabrici, Lužar, Rindošová, and Soták [9] and was further studied in [3, 5, 11, 14]. For a graph $G$ , a proper conflict-free coloring of $G$ ^†^†margin: proper conflict-free coloring of $G$ is a proper conflict-free coloring of the pair $(G,\mathcal{H})$ , where $\mathcal{H}$ is the hypergraph with $V(\mathcal{H})=V(G)$ and the edges of $\mathcal{H}$ are the (open) neighborhoods of the non-isolated vertices of $G$ . In other words, a proper conflict-free coloring of a graph $G$ is a proper coloring of $G$ such that for every non-isolated vertex $v$ , some color appears exactly once on the neighbors of $v$ . This notion is a combination of proper coloring and the pointed conflict-free chromatic parameter studied in [4, 17].

For a graph or hypergraph $G$ , the degree^†^†margin: degree of a vertex $v$ in $G$ , denoted by $d_{G}(v)$ ^†^†margin: $d_{G}(v)$ , is the number of edges of $G$ containing $v$ , and we denote by $\Delta(G)$ ^†^†margin: $\Delta(G)$ the maximum degree of $G$ . For a graph $G$ , we denote by $\chi_{\textrm{pcf}}(G)$ ^†^†margin: $\chi_{\textrm{pcf}}(G)$ the minimum $k$ such that $G$ has a proper conflict-free coloring with $k$ colors. Caro, Petruševski, and Škrekovski [3] proposed the following conjecture.

Conjecture 1 ([3]).

$\chi_{\textrm{pcf}}(G)\leqslant\Delta(G)+1$ for every connected graph $G$ with $\Delta(G)\geqslant 3$ .

The condition $\Delta(G)\geqslant 3$ in Conjecture 1 is required since $\chi_{\textrm{pcf}}(C_{5})=5$ , but if the conjecture is true, then the condition for connectivity can be removed when $\Delta(G)\geqslant 4$ . The case $\Delta(G)=3$ of Conjecture 1 follows from an earlier result of the second author and Yu [16, Theorem 2], even for the list-coloring setting.

As a first step toward their conjecture, Caro, Petruševski, and Škrekovski [3] proved that $\chi_{\textrm{pcf}}(G)\leqslant 5\Delta(G)/2$ . In fact, we can prove $\chi_{\textrm{pcf}}(G)\leqslant 2\Delta(G)+1$ by a simple greedy algorithm (see Proposition 3 below). A goal of this paper is to make further progress toward this conjecture.³³3When a version of this paper was under review, the second author and Reed [15] proved that $\chi_{\textrm{pcf}}(G)\leqslant(1+o(1))\Delta(G)$ , so Conjecture 1 holds asymptotically. This bound in [15] is quantitatively stronger than the bounds in this paper. However, all results in this paper work for list-coloring or for proper conflict-free coloring of pairs of graphs and hypergraphs $(G,\mathcal{H})$ . The result and proof in [15] do not work for those more general settings.

Our first result works for list-coloring. A list-assignment^†^†margin: list-assignment $L$ for a graph $G$ assigns to each vertex $v\in V(G)$ a list $L(v)$ of allowable colors. An $a$ -assignment^†^†margin: $a$ -assignment , for some real number $a$ , is a list-assignment $L$ such that $|L(v)|\geqslant a$ for all vertices $v$ . An $L$ -coloring^†^†margin: $L$ -coloring of $G$ is a coloring $\varphi$ such that $\varphi(v)\in L(v)$ for all $v\in V(G)$ . We prove the following.

Theorem 2.

Fix a positive integer $\Delta\geqslant 6.5\cdot 10^{7}$ , fix a real number $\beta$ with $\Delta\geqslant\beta\geqslant 0.6550826\Delta$ , and let $a:=\left\lceil\Delta+\beta+\sqrt{\Delta}\right\rceil$ . If $G$ is a graph with maximum degree at most $\Delta$ and $L$ is an $a$ -assignment for $G$ , then there are at least $\beta^{|V(G)|}$ proper conflict-free $L$ -colorings of $G$ . Analogous statements hold when $\Delta\geqslant 4000$ and $\Delta\geqslant\beta\geqslant 0.\overline{6}\Delta$ and when $\Delta\geqslant 750$ and $\Delta\geqslant\beta\geqslant 0.8\Delta$ .

It is obvious that the term $\sqrt{\Delta}$ in Theorem 2 can be replaced by $10^{-10}\Delta$ when $\Delta$ is sufficiently large. We choose $\sqrt{\Delta}$ as the error term because it is a natural sublinear term and it enables us to only require a reasonably small lower bound on $\Delta$ . We put a small amount of effort into optimizing the lower bound for $\Delta$ for the cases $\beta\geqslant 0.\overline{6}\Delta$ and $\beta\geqslant 0.8\Delta$ . The proofs of the three cases $\beta\geqslant 0.6550826\Delta$ , $\beta\geqslant 0.\overline{6}\Delta$ , and $\beta\geqslant 0.8\Delta$ are essentially the same, and the proof can be simplified if we do not care about keeping the lower bound on $\Delta$ small. In fact, we prove a more general result (Theorem 4, below) about proper conflict-free coloring for pairs of graphs and hypergraphs, and Theorem 2 follows as a special case for $\Delta$ sufficiently large.

Recall that we mentioned a greedy upper bound of $2\Delta(G)+1$ for Conjecture 1. It is obtained by the following simple observation, which is a modification of an observation by Pach and Tardos [17] on conflict-free coloring for hypergraphs, since the hypergraph $\mathcal{H}$ associated with proper conflict-free coloring for $G$ has edge set equal to the set of neighborhoods of non-isolated vertices and hence has $\Delta(\mathcal{H})=\Delta(G)$ .

Proposition 3.

Let $G$ be a graph and $\mathcal{H}$ be a hypergraph with $V(\mathcal{H})=V(G)$ . If $G$ is $d$ -degenerate, then $(G,\mathcal{H})$ has a proper conflict-free coloring with at most $d+\Delta(\mathcal{H})+1$ colors.

Proof.

Since $G$ is $d$ -degenerate, there exists an ordering $v_{1},v_{2},...$ of $V(G)$ such that for every $i$ , there are at most $d$ indices $j$ with $j<i$ such that $v_{i}v_{j}\in E(G)$ . For each edge $f$ of $\mathcal{H}$ , let $v_{f}$ be the vertex in $f$ with the smallest index. We color $v_{1},v_{2},...$ greedily in the order listed. For each $i$ , when we color $v_{i}$ , we avoid the colors used on all colored neighbors $v_{j}$ of $v_{i}$ , and for each edge $f$ of $\mathcal{H}$ containing $v_{i}$ with $v_{i}\neq v_{f}$ , we also avoid the color of $v_{f}$ . Since there are at most $d$ $v_{j}$ ’s and at most $\Delta(\mathcal{H})$ $v_{f}$ ’s, we only have to avoid at most $d+\Delta(\mathcal{H})$ colors, so $d+\Delta(\mathcal{H})+1$ colors suffice. Moreover, this greedy coloring is clearly proper and is conflict-free for $(G,\mathcal{H})$ since the color assigned to $v_{f}$ has a unique occurrence in $f$ for each $f\in E(\mathcal{H})$ . ∎

Proposition 3 shows that $\Delta(\mathcal{H})$ plays a role for upper bounding the number of colors for proper conflict-free colorings for $(G,\mathcal{H})$ . Our more general Theorem 4 shows that the importance of $\Delta(\mathcal{H})$ is somehow secondary to the size of edges of $\mathcal{H}$ . We need some terminology to state Theorem 4. Let $\mathcal{H}$ be a hypergraph. The rank of $\mathcal{H}$ , denoted by ${\rm{rank}}(\mathcal{H})$ ^†^†margin: ${\rm{rank}}(\mathcal{H})$ , is $\max_{f\in E(\mathcal{H})}|f|$ . For every vertex $v$ of $\mathcal{H}$ , we define ${\rm{mr}}_{\mathcal{H}}(v)$ ^†^†margin: ${\rm{mr}}_{\mathcal{H}}(v)$ to be $\min_{f\in E(\mathcal{H}),f\ni v}|f|$ .

Theorem 4.

Let $R$ be a positive integer. Let $G$ be a graph and $\mathcal{H}$ be a hypergraph with $V(G)=V(\mathcal{H})$ and ${\rm{rank}}(\mathcal{H})\leqslant R$ such that $|f|\geqslant 3$ for every $f\in E(\mathcal{H})$ . Let $\beta$ be a real number with $0.6550826R\leqslant\beta\leqslant R$ . Let

a:=\lceil\Delta(G)+\beta+\max_{v\in V(G)}\big{(}d_{\mathcal{H}}(v)\cdot b(v)\big{)}\rceil,

where

b(v):=\max\{2\beta^{1-\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}(\log R)^{2\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil},(1-10^{-8})^{(\log R)^{2}}\}.

If⁴⁴4In the first version of this paper [6], we proved the same result but only required $R\geqslant e^{5\cdot 10^{6}}$ with a more complicated proof. We elect to present a simpler proof suggested by a referee in this version even though the lower bound for $R$ is weaker. $R\geqslant e^{3.1\cdot 10^{8}}$ , then for every $a$ -assignment $L$ of $G$ , there are at least $\beta^{|V(G)|}$ proper conflict-free $L$ -colorings of $(G,\mathcal{H})$ .

The condition $|f|\geqslant 3$ for every $f\in E(\mathcal{H})$ in Theorem 4 is mild, since we may move edges of $\mathcal{H}$ with size 2 to edges of $G$ . However, this operation might increase $\Delta(G)$ . When considering proper conflict-free coloring for a graph $G$ , this condition $|f|\geqslant 3$ is satisfied only when $G$ has minimum degree at least 3. But vertices of degree at most 2 can be handled by a simple argument, so Theorem 2 can be deduced (when $R$ is sufficiently large) from Theorem 4 without moving edges of size 2 from $\mathcal{H}$ to $G$ .

The emphasis of Theorem 4 is on making the lower bound hypothesis on $\beta$ as weak as possible; that is, making the coefficient on $R$ as small as possible. So this result is more effective when ${\rm{rank}}(\mathcal{H})$ is large. When ${\rm{rank}}(\mathcal{H})$ is small, we can obtain the following result (Theorem 5) by slightly modifying the proof of Theorem 4 to drop logarithmic factors. We will show that the number of colors mentioned in Theorem 5 is optimal up to a constant factor.

Theorem 5.

Let $r,\varepsilon,R$ be positive real numbers. Let $G$ be a graph and $\mathcal{H}$ be a hypergraph with $V(G)=V(\mathcal{H})$ and ${\rm{rank}}(\mathcal{H})\leqslant r$ such that $|f|\geqslant 3$ for every $f\in E(\mathcal{H})$ . If either

•

$R\geqslant(1+\frac{1}{\varepsilon})r$ and

a:=\lceil\Delta(G)+R+(1+\varepsilon)\cdot\max_{v\in V(G)}\{d_{\mathcal{H}}(v)\cdot r^{\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}R^{1-\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}\}\rceil,

•

$r\leqslant 4$ and

$a:=\lceil\Delta(G)+R+\Delta(\mathcal{H})\cdot(3R^{-1}+R^{-2})\rceil,$

then for every $a$ -assignment $L$ of $G$ , there are at least $R^{|V(G)|}$ proper conflict-free $L$ -colorings of $(G,\mathcal{H})$ .

Theorem 5 has applications to other coloring parameters studied in the literature. Given a graph $G$ , if we define $\mathcal{H}$ to be the hypergraph with $V(\mathcal{H})=V(G)$ such that $E(\mathcal{H})$ consists of the vertex sets of any 4-vertex path (not necessarily induced) in $G$ and the 3-element subsets of $N(v)$ for each vertex $v$ of $G$ , then it is easy to show that $d_{\mathcal{H}}(v)\leqslant 2.5\Delta(G)^{3}$ , ${\rm{rank}}(\mathcal{H})\leqslant 4$ and ${\rm{mr}}_{\mathcal{H}}(v)\geqslant 3$ for every $v\in V(G)$ . So taking $R=\sqrt{7.5}\Delta(G)^{3/2}$ in Statement 2 in Theorem 5 immediately gives the following corollary.

Corollary 6.

For every graph $G$ and every $\lceil\sqrt{30}\Delta(G)^{3/2}+\Delta(G)+\frac{1}{3}\rceil$ -assignment $L$ of $G$ , there exist at least $(7.5\Delta(G)^{3})^{|V(G)|/2}$ proper $L$ -colorings $\varphi$ such that every 4-vertex path in $G$ has a color used exactly once, and for every vertex $v$ with $d_{G}(v)\geqslant 3$ and for any three neighbors of $v$ , some color is used exactly once on those three neighbors. In particular, every component of the subgraph of $G$ induced by any two arbitrarily chosen color classes of $\varphi$ is a path on at most three vertices.

The coloring satisfying the conclusion of Corollary 6 is both a star coloring^†^†margin: star coloring , which is a proper coloring with no bi-colored 4-vertex path, and also a linear coloring^†^†margin: linear coloring , which is a proper coloring such that any two color classes induce a subgraph whose every component is a path. Yuster [21] proved that there exist infinitely many graphs $G$ having no linear coloring with at most $\Delta(G)^{3/2}/11$ colors. So Corollary 6, and hence Theorem 5, are optimal up to a constant factor. Corollary 6 also improves the currently best known upper bound $\max\{50\Delta(G)^{4/3},10\Delta(G)^{3/2}\}$ for linear coloring [21]. For star coloring, our $(\sqrt{30}+o(1))\Delta(G)^{3/2}$ upper bound is not better than the currently best known upper bounds $2\sqrt{2}\Delta(G)^{3/2}+\Delta(G)$ [7, 20], even though both results are only a $O(\sqrt{\log\Delta(G)})$ factor away from the known lower bound $\Omega(\Delta(G)^{3/2}/\sqrt{\log\Delta(G)})$ [10]. However, the coloring we obtain in Corollary 6 is stronger than a star coloring and than a linear coloring. Every bi-chromatic component of the coloring in Corollary 6 has at most three vertices, while the bi-chromatic components of a star coloring or a linear coloring can have arbitrarily many vertices.

Our next result shows that the fractional version of Conjecture 1 holds asymptotically. It follows from a more general setting for coloring pairs $(G,\mathcal{H})$ .

Let $[k]$ ^†^†margin: $[k]$ denote $\{1,\ldots,k\}$ , for each $k\in\mathbb{Z}^{+}$ . Let $a$ and $b$ be positive integers. An $(a:b)$ -coloring^†^†margin: $(a:b)$ -coloring of a graph or a hypergraph assigns to each vertex a $b$ -element subset of $[a]$ . An $(a:b)$ -coloring $\varphi$ of a graph $G$ is proper^†^†margin: proper if for every $j\in[a]$ , the preimage $\varphi^{-1}(j)$ is a stable set in $G$ . An $(a:b)$ -coloring $\varphi$ of a hypergraph $\mathcal{H}$ is conflict-free^†^†margin: conflict-free if for every edge $e$ of $\mathcal{H}$ , there exist at least $b$ elements $\ell$ of $[a]$ such that $|e\cap\varphi^{-1}(\ell)|=1$ . Let $G$ be a graph and $\mathcal{H}$ be a hypergraph with $V(\mathcal{H})=V(G)$ . An $(a:b)$ -coloring $\varphi$ of $(G,\mathcal{H})$ is fractionally proper conflict-free^†^†margin: fractionally proper conflict-free if it is a proper $(a:b)$ -coloring of $G$ and a conflict-free $(a:b)$ -coloring of $\mathcal{H}$ . For a positive real number $t$ , $(G,\mathcal{H})$ is fractionally properly conflict-free $t$ -colorable^†^†margin: fractionally properly conflict-free $t$ -colorable if there exists a proper conflict-free $(x:y)$ -coloring of $(G,\mathcal{H})$ for some positive integers $x,y$ with $x/y\leqslant t$ .

Fractional proper conflict-free coloring for $(G,\mathcal{H})$ , defined above, is a natural linear programming relaxation of proper conflict-free coloring for $(G,\mathcal{H})$ . We prove that $\Delta(\mathcal{H})$ is no longer required for upper bounding the number of colors, if we consider fractional coloring and ${\rm{rank}}(\mathcal{H})\leqslant\Delta(G)$ .

Theorem 7.

For every $\varepsilon>0$ , there exists $d_{0}$ such that if $\Delta\geqslant d_{0}$ and $G$ is a graph with maximum degree at most $\Delta$ , then $(G,\mathcal{H})$ is fractionally properly conflict-free $(1+\varepsilon)\Delta$ -colorable for every hypergraph $\mathcal{H}$ with $V(\mathcal{H})=V(G)$ and ${\rm{rank}}(\mathcal{H})\leqslant\Delta$ .

Theorem 7 is asymptotically optimal since, for each $\Delta\geqslant 2$ , there are infinitely many connected graphs with maximum degree $\Delta$ that are not properly $(\Delta-1)$ -colorable.

For a graph $G$ , we say that an $(a:b)$ -coloring of $G$ is a fractional proper conflict-free coloring of $G$ ^†^†margin: fractional proper conflict-free coloring of $G$ if it is a proper $(a:b)$ -coloring of $G$ such that for every non-isolated vertex $v$ of $G$ , at least $b$ colors appear exactly once on $N(v)$ . If we take $\mathcal{H}$ so that $E(\mathcal{H})$ contains all nonempty subsets of $V(G)$ with size at most $\Delta$ , then Theorem 7 leads to the following corollary.

Corollary 8.

For every $\varepsilon>0$ , there exists $d_{0}$ such that if $\Delta\geqslant d_{0}$ and $G$ is a graph with maximum degree at most $\Delta$ , then there exists a proper $(a:b)$ -coloring $\varphi$ of $G$ for some positive integers $a$ and $b$ with $a\leqslant(1+\varepsilon)\Delta b$ such that

1.

$\varphi$ is a fractional proper conflict-free $(a:b)$ -coloring of $G$ ,
2.

for any set $C$ of colors with size less than $5b/2$ , every component of the subgraph of $G$ induced by the vertices that use only colors in $C$ has at most two vertices, and
3.

$|\varphi(v)\cap\varphi(w)|\leqslant b/2$ for any distinct vertices $v,w$ of $G$ .

Statement 1 of Corollary 8 implies that the fractional version of Conjecture 1 holds asymptotically. Statement 2 of Corollary 8 gives the asymptotically optimal upper bound for the fractional version of many types of coloring that address properties of bi-chromatic components, such as acyclic coloring, star coloring, frugal coloring, and linear coloring. It is also a fractional analogue of Corollary 6, but now each $2b$ -colored component has at most two vertices, which is clearly optimal.

The paper is organized as follows. To emphasize the key ideas in our proofs of Theorems 2, 4 and 5, for clarity we first present the proofs assuming certain estimates of quantities involving 2-associated Stirling numbers, which count the number of partitions of a set with certain properties. In Section 3 (and the appendix) we prove those estimates via a sequence of lemmas. Finally, we prove Theorem 7 and Corollary 8 in Section 4.

2 Proof of Theorems 2, 4, and 5

In this section, we prove Theorems 2, 4, and 5. The proofs use a clever inductive counting argument introduced by Rosenfeld [18] and extended by Wanless and Wood [20]. This technique works well for many problems amenable to the Lovász Local Lemma or entropy compression, but often gives simpler proofs. Our proof actually works for a slightly more general setting. For an integer $t$ , a graph $G$ , and a hypergraph $\mathcal{H}$ with $V(\mathcal{H})=V(G)$ , we say that $\varphi$ is a proper $t$ -conflict-free coloring of $(G,\mathcal{H})$ ^†^†margin: proper $t$ -conflict-free coloring of $(G,\mathcal{H})$ if it is a proper coloring of $G$ such that for every $f\in E(\mathcal{H})$ ,⁵⁵5For clarity, we always use $e$ to denote the base of the natural logarithm, which is the constant $2.71828\cdots$ . For an edge of a hypergraph, we typically use $f$ . there exists a color that is used $k$ times by $\varphi$ on $f$ for some $k\in[t]$ . Note that conflict-free colorings of $(G,\mathcal{H})$ are exactly $1$ -conflict-free colorings of $(G,\mathcal{H})$ .

When applying the aforementioned inductive counting argument to proper $t$ -conflict-free coloring, the computation involves $t$ -associated Stirling numbers of the second kind, denoted by $S_{t}(d,i)$ ; for positive integers $t$ , $i$ , and $d$ , the quantity $S_{t}(d,i)$ ^†^†margin: $S_{t}(d,i)$ is defined as the number of partitions of the set $[d]$ into $i$ parts, each of size at least $t$ . Now we can state and prove our first key lemma.

Lemma 9.

Let $G$ be a graph and $\mathcal{H}$ be a hypergraph with $V(G)=V(\mathcal{H})$ . Let $t$ be a positive integer. Let $\beta$ be a real number. If $a$ is a real number such that

\displaystyle a\geqslant\Delta(G)+\beta+\sum_{f\in E(\mathcal{H}),f\ni v}\sum_{i=1}^{\lfloor|f|/(t+1)\rfloor}S_{t+1}(|f|,i)\cdot\beta^{i-|f|+1}

(1)

for every $v\in V(G)$ , then for every $a$ -assignment $L$ of $G$ , there are at least $\beta^{|V(G)|}$ proper $t$ -conflict-free $L$ -colorings of $(G,\mathcal{H})$ .

Proof.

For a subset $Z$ of $V(G)$ , an $L$ -coloring $\varphi$ of $G[Z]$ is a proper $t$ -conflict-free partial coloring on $Z$ if

(a)

$\varphi$ is a proper coloring of $G[Z]$ , and
(b)

for each $f\in E(\mathcal{H})$ , if $f\subseteq Z$ , then $\varphi$ uses some color exactly $k$ times on $f$ for some $k\in[t]$ .

For each subset $Z$ of $V(G)$ , denote by $R(Z)$ ^†^†margin: $R(Z)$ the number of proper $t$ -conflict-free partial $L$ -colorings on $Z$ . For every nonempty subset $Z$ of $V(G)$ , and every $v\in Z$ , we will prove by induction on $|Z|$ :

\displaystyle R(Z)

\displaystyle\geqslant\beta\cdot R(Z\setminus\{v\}).

(2)

For each $v\in V(G)$ , we have $R(\{v\})=a\geqslant\beta$ . So the desired base case holds. Thus, induction on $|Z|$ will give $R(Z)\geqslant\beta^{|Z|}$ for all $Z$ . In particular, $R(V(G))\geqslant\beta^{|V(G)|}$ .

Fix some $Z\subseteq V(G)$ and $v\in Z$ . If we extend a proper $t$ -conflict-free partial coloring on $Z\setminus\{v\}$ by further coloring $v$ with a color that is not used on its colored neighbors, then we form a proper $L$ -coloring of $G[Z]$ . Note that there are at least $a-\Delta(G)$ ways to extend a proper $t$ -conflict-free partial coloring on $Z\setminus\{v\}$ to a proper coloring of $G[Z]$ . Hence there are at least $(a-\Delta(G))\cdot R(Z\setminus\{v\})$ $L$ -colorings of $G[Z]$ satisfying (a). We show that at least $\beta\cdot R(Z\setminus\{v\})$ of these also satisfy (b).

A proper $L$ -coloring $\varphi$ of $G[Z]$ is bad^†^†margin: bad if it is not a proper $t$ -conflict-free partial coloring on $Z$ but its restriction to $Z\setminus\{v\}$ is a proper $t$ -conflict-free partial coloring on $Z\setminus\{v\}$ . Let $B$ ^†^†margin: $B$ be the set of bad $L$ -colorings. For every $f\in E(H)$ with $v\in f$ and $f\subseteq Z$ , let $B_{f}$ ^†^†margin: $B_{f}$ := $\{\varphi\in B:\varphi$ does not use any color exactly $k$ times on $f$ for every $k\in[t]\}$ ; these are the colorings that are bad for $f$ . So $B=\bigcup_{f\in E(\mathcal{H}),f\ni v}B_{f}$ . To prove (2), it suffices to show $(a-\Delta(G))\cdot R(Z\setminus\{v\})-|B|\geqslant\beta\cdot R(Z\setminus\{v\})$ .

We claim that for every edge $f$ of $\mathcal{H}$ containing $v$ ,

\displaystyle|B_{f}|\leqslant\sum_{i=1}^{\lfloor|f|/(t+1)\rfloor}S_{t+1}(|f|,i)\cdot R(Z\setminus\{v\})\beta^{i-|f|+1}.

(3)

This claim implies this lemma since the number of proper $t$ -conflict-free partial colorings of $G[Z]$ is at least

		$\displaystyle R(Z\setminus\{v\})(a-\Delta(G))-\sum_{f\in E(\mathcal{H}),f\ni v}\|B_{f}\|$
	$\displaystyle\geqslant~{}$	$\displaystyle R(Z\setminus\{v\})\left[a-\Delta(G)-\sum_{f\in E(\mathcal{H}),f\ni v}\sum_{i=1}^{\lfloor\|f\|/(t+1)\rfloor}S_{t+1}(\|f\|,i)\cdot\beta^{i-\|f\|+1}\right]$
	$\displaystyle\geqslant~{}$	$\displaystyle\beta R(Z\setminus\{v\}).$

Here the final inequality follows from (1).

Now we prove (3). Fix an edge $f$ of $\mathcal{H}$ containing $v$ . For every $\varphi\in B_{f}$ , let $\mathcal{P}_{\varphi}$ ^†^†margin: $\mathcal{P}_{\varphi}$ be the partition $\{\varphi^{-1}(j)\cap f:j\in{\mathbb{Z}}^{+}\}$ of $f$ . These are the color classes of $\varphi|_{f}$ , which is the coloring obtained by restricting $\varphi$ to $f$ . Since $\varphi\in B_{f}$ , every part in $\mathcal{P}_{\varphi}$ has size at least $t+1$ . Hence the number of possibilities for $\mathcal{P}_{\varphi}$ is at most $S_{t+1}(|f|,i_{\varphi})$ , where $i_{\varphi}$ is the number of colors used in $\varphi|_{f}$ . Note that for every partition $\mathcal{P}$ of $f$ into $i$ parts each having size at least $t+1\geqslant 2$ , there exists a subset $T_{\mathcal{P}}$ ^†^†margin: $T_{\mathcal{P}}$ of $f$ consisting of a vertex in each part of $\mathcal{P}$ such that $v\not\in T_{\mathcal{P}}$ . We define $T_{\varphi}$ ^†^†margin: $T_{\varphi}$ to be $T_{\mathcal{P}_{\varphi}}\cup(Z-f)$ . Note that $\varphi$ is uniquely determined by $\mathcal{P}_{\varphi}$ and $\varphi|_{T_{\varphi}}$ . Moreover, since $T_{\varphi}\subseteq Z\setminus\{v\}$ , the partial coloring $\varphi|_{T_{\varphi}}$ is a proper $t$ -conflict-free partial $L$ -coloring on $T_{\varphi}=Z\setminus(f\setminus T_{\mathcal{P}_{\varphi}})$ . Hence, for every partition $\mathcal{P}$ of $f$ into parts each having size at least $t+1$ , the number of possibilities for $\varphi|_{T_{\varphi}}$ , among all colorings $\varphi$ in $B_{f}$ with $\mathcal{P}_{\varphi}=\mathcal{P}$ , is at most $R(Z\setminus(f\setminus T_{\mathcal{P}}))$ . By applying the inductive hypothesis $|f|-|\mathcal{P}|-1$ times, we see that

\displaystyle R(Z\setminus\{v\})\geqslant R(Z\setminus(f\setminus T_{\mathcal{P}}))\beta^{|f|-|\mathcal{P}|-1}.

Equivalently, $R(Z\setminus(f\setminus T_{\mathcal{P}}))\leqslant R(Z\setminus\{v\})\beta^{|\mathcal{P}|-|f|+1}.$ Therefore, for any fixed integer $i$ , the number of colorings $\varphi$ in $B_{f}$ with $|\mathcal{P}_{\varphi}|=i$ is at most $S_{t+1}(|f|,i)\cdot R(Z\setminus\{v\})\beta^{i-|f|+1}$ . Since every color is used at least $t+1$ times or zero times on $f$ , we have $1\leqslant i\leqslant\lfloor|f|/(t+1)\rfloor$ .

This proves the lemma. ∎

As we have seen in Lemma 9, estimates for $t$ -associated Stirling numbers of the second kind are crucial. In this paper, we will only need sophisticated estimates for the case $t=2$ . These $S_{2}(d,i)$ have been widely studied in the literature (see [2, 19] and the references therein), but the known formulas are unhelpful for our purposes here.

Instead, we will prove the following two estimates for $S_{2}(d,i)$ . We prove the second in Section 3. But the proof of the first essentially consists of straightforward but tedious calculation, so we defer it to the appendix.

Lemma 10.

Let $d$ and $R$ be positive integers and $\beta$ be a real number with $\beta\geqslant 0.6R\geqslant 14$ . If $3\leqslant{d}\leqslant\beta^{19/20}$ and $\beta\geqslant 600$ and $R\geqslant 750$ , then

\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}S_{2}(d,i)\beta^{i-d+1}\leqslant R^{-1/2}.

Lemma 11.

Let $d$ and $R$ be positive integers with $110\leqslant d\leqslant R$ . If $\varepsilon$ , $c$ , and $\beta$ are real numbers such that $0.6251\leqslant\varepsilon<1$ , $0.3\leqslant c<\frac{\varepsilon}{2}$ and $\varepsilon R\leqslant\beta\leqslant R$ , then

\sum_{i=1}^{\lfloor d/2\rfloor}S_{2}(d,i)\beta^{i-d+1}\leqslant\frac{d\beta}{2}\left(\frac{2c}{\varepsilon}\right)^{(1-c)d}+2R^{3}\left(\frac{\varepsilon}{0.6251}\right)^{-d/2}.

Moreover, if $d\geqslant\max\{\frac{7.6\log R}{\log(\varepsilon/0.6251)},\frac{2.5\log R}{(1-c)\log(\varepsilon/(2c))}\}$ , then

\sum_{i=1}^{\lfloor d/2\rfloor}S_{2}(d,i)\beta^{i-d+1}\leqslant R^{-1/2}.

Now we can prove a special case of Theorem 2 for graphs with minimum degree at least three.

Lemma 12.

Fix a positive integer $\Delta\geqslant 6.5\cdot 10^{7}$ , fix a real number $\beta$ with $\Delta\geqslant\beta\geqslant 0.6550826\Delta$ , and let $a:=\left\lceil\Delta+\beta+\sqrt{\Delta}\right\rceil$ . If $G$ is a graph with minimum degree at least 3 and maximum degree at most $\Delta$ , and $L$ is an $a$ -assignment for $G$ , then there are at least $\beta^{|V(G)|}$ proper conflict-free $L$ -colorings of $G$ . Analogous statements hold when $\Delta\geqslant 4000$ and $\beta\geqslant 0.\overline{6}\Delta$ and when $\Delta\geqslant 750$ and $\beta\geqslant 0.8\Delta$ .

Proof.

Let $\mathcal{H}$ ^†^†margin: $\mathcal{H}$ be the hypergraph with $V(\mathcal{H})=V(G)$ and $E(\mathcal{H})=\{N(v):v\in V(G)\}$ . By Lemma 9, it suffices to show $\sum_{f\in E(\mathcal{H}),f\ni v}\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)\cdot\beta^{i-|f|+1}\leqslant\sqrt{\Delta}$ for every $v\in V(G)$ . Note that $\Delta(\mathcal{H})\leqslant\Delta$ . So it suffices to show, for every $f\in E(\mathcal{H})$ , that

\displaystyle\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)\cdot\beta^{i-|f|+1}\leqslant 1/\sqrt{\Delta}.

(4)

Fix an edge $f$ of $\mathcal{H}$ . Every vertex of $G$ has degree at least 3 and at most $\Delta$ , so $3\leqslant|f|\leqslant\Delta$ . Our assumptions for $\Delta$ and $\beta$ imply $\beta\geqslant 600$ . So (4) holds when $|f|\leqslant\beta^{19/20}$ by Lemma 10. Hence we may assume $|f|>\beta^{19/20}$ . By Lemma 11, it suffices to show $\beta^{19/20}\geqslant\max\{\frac{7.6\log\Delta}{\log(\varepsilon/0.6251)},\frac{2.5\log\Delta}{(1-c)\log(\varepsilon/(2c))}\}$ , for corresponding choices of $\varepsilon$ and $c$ .

Let $\varepsilon=0.6550826$ and $c=0.32754$ . So $\Delta\geqslant\beta\geqslant\varepsilon\Delta$ . We have $\max\{\frac{7.6}{\log(\varepsilon/0.6251)},\frac{2.5}{(1-c)\log(\varepsilon/(2c))}\}\leqslant\max\{164,936689\}=936689$ . By considering the derivative, we know $(\varepsilon\Delta)^{19/20}/\log\Delta$ is increasing when $\Delta>10$ . If $\Delta\geqslant 6.5\cdot 10^{7}$ , then $\frac{\beta^{19/20}}{\log\Delta}\geqslant\frac{(\varepsilon\Delta)^{19/20}}{\log\Delta}\geqslant\frac{(\varepsilon\cdot 6.5\cdot 10^{7})^{19/20}}{\log(6.5\cdot 10^{7})}\geqslant 983377>936689\geqslant\max\{\frac{7.6}{\log(\varepsilon/0.6251)},\frac{2.5}{(1-c)\log(\varepsilon/(2c))}\}$ . So we are done.

Now we assume $\varepsilon=0.\overline{6}$ and $c=0.3272$ . We have $\max\{\frac{7.6}{\log(\varepsilon/0.6251)},\frac{2.5}{(1-c)\log(\varepsilon/(2c))}\}\leqslant\max\{120,\allowbreak 201\}=201$ . If $\Delta\geqslant 4000$ , then $\frac{\beta^{19/20}}{\log\Delta}\geqslant\frac{(\varepsilon\Delta)^{19/20}}{\log\Delta}\geqslant\frac{(\varepsilon\cdot 4000)^{19/20}}{\log 4000}\geqslant 216\geqslant 201$ . So we are done.

Finally, we assume $\varepsilon=0.8$ and $c=0.32$ . We have $\max\{\frac{7.6}{\log(\varepsilon/0.6251)},\frac{2.5}{(1-c)\log(\varepsilon/(2c))}\}\leqslant\max\{32,\allowbreak 22\}=32$ . If $\Delta\geqslant 750$ , then $\frac{\beta^{19/20}}{\log\Delta}\geqslant\frac{(\varepsilon\Delta)^{19/20}}{\log\Delta}\geqslant\frac{(\varepsilon\cdot 750)^{19/20}}{\log 750}\geqslant 65\geqslant 32$ . This proves the lemma. ∎

Now we are ready to prove Theorem 2.

Proof of Theorem 2.

Suppose that $G$ is a counterexample with the minimum number of vertices. Clearly, $G$ is connected and has at least three vertices. Let $v$ be a vertex of $G$ with smallest degree. By Lemma 12, the degree of $v$ is 1 or 2. Let $x$ and $y$ be the neighbors of $v$ , where $x=y$ if $v$ has degree 1. If $x\neq y$ , and $x$ and $y$ are non-adjacent, then let $G^{\prime}:=G-v+xy$ ; otherwise, let $G^{\prime}:=G-v$ . Let $L^{\prime}$ be the restriction of $L$ to $V(G^{\prime})$ . Since $G^{\prime}$ has maximum degree at most $\Delta$ , the minimality of $G$ implies that there exist at least $\beta^{|V(G)|-1}$ proper conflict-free $L^{\prime}$ -colorings of $G^{\prime}$ . Hence, to obtain a contradiction, it suffices to show that for every proper conflict-free $L^{\prime}$ -coloring $\varphi$ of $G^{\prime}$ , there are at least $\beta$ ways to extend $\varphi$ to a proper conflict-free $L$ -coloring of $G$ .

Fix a proper conflict-free $L^{\prime}$ -coloring $\varphi$ of $G^{\prime}$ . Since $G$ is connected and has at least three vertices, $x$ and $y$ each have degree at least one in $G^{\prime}$ , by the choice of $v$ . So there exist colors $c_{x}$ and $c_{y}$ such that $c_{x}$ appears on $N_{G^{\prime}}(x)$ exactly once and $c_{y}$ appears on $N_{G^{\prime}}(y)$ exactly once. If possible, we choose $c_{x}\neq\varphi(y)$ and $c_{y}\neq\varphi(x)$ . If $G^{\prime}=G-v$ , then either $N_{G}(v)=\{x\}$ , or $xy\in E(G^{\prime})$ and $\varphi(x)\neq\varphi(y)$ , so there are at least $a-4\geqslant\beta$ ways to extend $\varphi$ to a proper conflict-free coloring of $G$ by coloring $v$ with a color in $L(v)\setminus\{\varphi(x),\varphi(y),c_{x},c_{y}\}$ , a contradiction. So $G^{\prime}=G-v+xy$ and $x\neq y$ . For each $u\in\{x,y\}$ and $u^{\prime}\in\{x,y\}\setminus\{u\}$ , if $c_{u}=\varphi(u^{\prime})$ , then let $S_{u}:=\{\varphi(z):z\in N_{G}(u)\setminus\{v\}\}$ ; otherwise, let $S_{u}:=\{c_{u}\}$ . For the former, since $c_{u}$ is chosen to be different from $\varphi(u^{\prime})$ if possible, we know that every color appears on $N_{G}(u)\setminus\{v\}$ zero times or at least twice, so $|S_{u}|\leqslant|N_{G}(u)\setminus\{v\}|/2\leqslant(\Delta-1)/2$ ; for the latter, $|S_{u}|=1\leqslant(\Delta-1)/2$ . But there are at least $a-|S_{x}|-|S_{y}|-2\geqslant a-(\Delta-1)-2\geqslant\beta$ ways to extend $\varphi$ to a proper conflict-free coloring of $G$ by coloring $v$ with a color in $L(v)\setminus(S_{x}\cup S_{y}\cup\{\varphi(x),\varphi(y)\})$ , a contradiction. ∎

To prove Theorem 4, we use the following estimate for $S_{2}(d,i)$ , which we will prove in Section 3.

Lemma 13.

If $d$ is a positive integer and $\beta$ is a real number with $d<\beta$ , then

\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}S_{2}(d,i)\beta^{i-d+1}\leqslant\beta\cdot\frac{(d/\beta)^{\lceil d/2\rceil}}{1-\frac{d}{\beta}}.

Now we prove Theorem 4.

Proof of Theorem 4.

By Lemma 9, it suffices to prove that $\sum_{f\in E(\mathcal{H}),f\ni v}\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)\cdot\beta^{i-|f|+1}\leqslant d_{\mathcal{H}}(v)\cdot\max\{2\beta(\frac{(\log R)^{2}}{\beta})^{\lceil{\rm{mr}}_{\mathcal{H}}(v)/2\rceil},(1-10^{-8})^{(\log R)^{2}}\}$ for every $v\in V(G)$ , when $R\geqslant e^{3.1\cdot 10^{8}}$ . And it suffices to prove $\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)\cdot\beta^{i-|f|+1}\leqslant\max\{2\beta(\frac{(\log R)^{2}}{\beta})^{\lceil{\rm{mr}}_{\mathcal{H}}(v)/2\rceil},(1-10^{-8})^{(\log R)^{2}}\}$ for every $v\in V(G)$ and $f\in E(\mathcal{H})$ containing $v$ , when $R\geqslant e^{3.1\cdot 10^{8}}$ .

Fix a vertex $v$ of $G$ and an edge $f$ of $\mathcal{H}$ containing $v$ .

Suppose $|f|\leqslant(\log R)^{2}$ . Since $R\geqslant e^{5\cdot 10^{6}}$ , we get $|f|\leqslant(\log R)^{2}\leqslant 0.5\cdot 0.65R<\beta$ . By Lemma 13,

\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)\beta^{i-|f|+1}\leqslant\beta\frac{(|f|/\beta)^{\lceil|f|/2\rceil}}{1-\frac{|f|}{\beta}}\leqslant\beta\frac{((\log R)^{2}/\beta)^{\lceil{\rm{mr}}_{\mathcal{H}}(v)/2\rceil}}{1-\frac{(\log R)^{2}}{0.65R}}\leqslant 2\beta^{1-\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}(\log R)^{2\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}.

Assume instead that $|f|>(\log R)^{2}$ . Let $\varepsilon=0.6550826$ and $c=0.32754125$ . Now $0.6251\leqslant\varepsilon<1$ , $0.3\leqslant c<\varepsilon/2$ , and $\varepsilon R\leqslant\beta\leqslant R$ . Since $|f|\leqslant{\rm{rank}}(\mathcal{H})\leqslant R$ and $R\geqslant|f|\geqslant 110$ , by Lemma 11,

	$\displaystyle\sum_{i=1}^{\lfloor\|f\|/2\rfloor}S_{2}(\|f\|,i)\beta^{i-\|f\|+1}$	$\displaystyle\leqslant\frac{\|f\|R}{2}\left(\frac{2\cdot 0.32754125}{0.6550826}\right)^{(1-0.32754125)\|f\|}+2R^{3}\left(\frac{0.6550826}{0.6251}\right)^{-\|f\|/2}$
		$\displaystyle\leqslant 2.5R^{3}\cdot(1-10^{-7})^{\|f\|}.$

Because $|f|\geqslant(\log R)^{2}$ ,

	$\displaystyle 2.5R^{3}\cdot(1-10^{-7})^{\|f\|}$	$\displaystyle\leqslant 2R^{2}\cdot(1-10^{-7})^{(\log R)^{2}}$
		$\displaystyle=2.5R^{3}\cdot(\frac{1-10^{-7}}{1-10^{-8}})^{(\log R)^{2}}\cdot(1-10^{-8})^{(\log R)^{2}}$
		$\displaystyle\leqslant 2.5R^{3}\cdot(\frac{1}{1+10^{-8}})^{(\log R)^{2}}\cdot(1-10^{-8})^{(\log R)^{2}}.$

Note that $\log(1+10^{-8})\geqslant 9.99999995\cdot 10^{-9}$ . Since $R\geqslant e^{3.1\cdot 10^{8}}$ , we have $2.5R^{3}\leqslant R^{3.01}$ and $\log R\geqslant 3.1\cdot 10^{8}$ , so $3.01\log R\leqslant(\log R)^{2}\cdot 9.99999995\cdot 10^{-9}\leqslant(\log R)^{2}\cdot\log(1+10^{-8})$ . Hence $2.5R^{3}\cdot(\frac{1}{1+10^{-8}})^{(\log R)^{2}}\cdot(1-10^{-8})^{(\log R)^{2}}\leqslant(1-10^{-8})^{(\log R)^{2}}$ . This proves the theorem. ∎

Finally, we prove Theorem 5.

Proof of Theorem 5.

Let $v\in V(G)$ and $f\in E(\mathcal{H})$ with $v\in f$ . Since ${\rm{rank}}(\mathcal{H})\leqslant r$ , $|f|\leqslant r$ . If $R\geqslant(1+\frac{1}{\varepsilon})r$ , then $1-\frac{r}{R}\geqslant\frac{1}{1+\varepsilon}$ , so by Lemma 13,

\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)R^{i-|f|+1}\leqslant R\frac{(|f|/R)^{\lceil|f|/2\rceil}}{1-\frac{|f|}{R}}\leqslant R\frac{(r/R)^{\lceil{\rm{mr}}_{\mathcal{H}}(v)/2\rceil}}{1-\frac{r}{R}}\leqslant(1+\varepsilon)R^{1-\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}r^{\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}.

Hence $\sum_{f\in E(\mathcal{H}),f\ni v}\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)\cdot R^{i-|f|+1}\leqslant d_{\mathcal{H}}(v)\cdot(1+\varepsilon)R^{1-\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}r^{\lceil\frac{{\rm{mr}}_{\mathcal{H}}(v)}{2}\rceil}$ . Therefore, Statement 1 of this theorem follows from Lemma 9 (with taking $\beta=R$ ).

Now we assume $r\leqslant 4$ . Then $3\leqslant|f|\leqslant 4$ . If $|f|=3$ , then

\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)R^{i-|f|+1}=S_{2}(3,1)R^{-1}=R^{-1}.

If $|f|=4$ , then

\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)R^{i-|f|+1}=S_{2}(4,1)R^{-2}+S_{2}(4,2)R^{-1}=R^{-2}+\frac{1}{2}{4\choose 2}R^{-1}=R^{-2}+3R^{-1}.

Hence $\sum_{f\in E(\mathcal{H}),f\ni v}\sum_{i=1}^{\lfloor|f|/2\rfloor}S_{2}(|f|,i)\cdot R^{i-|f|+1}\leqslant d_{\mathcal{H}}(v)\cdot(3R^{-1}+R^{-2})$ . Therefore, Statement 2 of this theorem follows from Lemma 9 (with taking $\beta=R$ ). ∎

3 Estimates for 2-Associated Stirling Numbers

Recall that, to prove our results in the previous section, we assumed the correctness of estimates about summations involving $S_{2}(d,i)$ (Lemmas 10, 11, and 13). In this section, we prove the second and third of these; the proof of Lemma 10 consists of calculation that is tedious but straightforward, so we defer it to the appendix. For simplicity, we denote $S_{2}(d,i)$ by $E_{i}(d)$ ^†^†margin: $E_{i}(d)$ for any positive integers $d$ and $i$ . We will extensively use two simple upper bounds for $E_{i}(d)$ , combined via $\min\{\cdot,\cdot\}$ in the following lemma.

Lemma 14.

For positive integers $i$ and $d$ ,

	$\displaystyle E_{i}(d)\leqslant$	$\displaystyle\min\Big{\{}{{d}\choose i}i^{{d}-i}2^{-i},$
		$\displaystyle\frac{d!}{\lfloor d/2\rfloor!2^{d/2}}\cdot{\bf 1}_{d/2\in{\mathbb{Z}}}+\sum_{j=\max\{3i-d,0\}}^{i-1}\binom{d}{2j}\frac{(2j)!}{j!2^{j}}\binom{d-2j}{3(i-j)}\frac{(3(i-j))!}{(i-j)!(3!)^{i-j}}(i-j)^{d-2j-3(i-j)}\Big{\}},$

where ${\bf 1}_{d/2\in{\mathbb{Z}}}=1$ if $d/2\in{\mathbb{Z}}$ , and ${\bf 1}_{d/2\in{\mathbb{Z}}}=0$ otherwise.

Proof.

To form a partition of $[d]$ into $i$ parts, each of size at least 2, we can choose $i$ elements to be “leaders” and then assign each other element to the part of a leader. (This also forms partitions with parts of size 1 but, since we seek an upper bound, this is not a problem.) Since each part has at least two elements, this process overcounts by a factor of at least $2^{i}$ . Thus,

\displaystyle E_{i}(d)\leqslant{{d}\choose i}i^{{d}-i}2^{-i}.

Now we prove the other upper bound. To form a partition of $[d]$ into $i$ parts each of size at least 2, we first consider the parts of size exactly 2; denote the number of them by $j$ . To form these $j$ parts of size 2, we choose $2j$ elements and pair them up. The number of ways to pair $2j$ elements is precisely $\frac{(2j)!}{j!2^{j}}$ . If $i=j$ , then $d=2i$ ; if $j<i$ , then each of the remaining $i-j$ parts has size at least 3, and to form these, we choose $3(i-j)$ of the remaining elements, group them into triples, then assign each element still remaining to one of these triples. The number of ways to group $3(i-j)$ elements into triples is $\frac{(3(i-j))!}{(i-j)!(3!)^{i-j}}$ . This gives

\displaystyle E_{i}(d)\leqslant\frac{d!}{\lfloor d/2\rfloor!2^{d/2}}\cdot{\bf 1}_{d/2\in{\mathbb{Z}}}+\sum_{j=\max\{3i-d,0\}}^{i-1}\binom{d}{2j}\frac{(2j)!}{j!2^{j}}\binom{d-2j}{3(i-j)}\frac{(3(i-j))!}{(i-j)!(3!)^{i-j}}(i-j)^{d-2j-3(i-j)}.

(For the lower bound on the index $j$ , note that $2j+3(i-j)\leqslant d$ , which implies that $j\geqslant 3i-d$ .) ∎

3.1 Proof of Lemma 13

We begin by proving Lemma 13. For easy reference, we restate it. This result will also be used when proving Lemma 10.

Lemma 13.

If $d$ is a positive integer and $\beta$ is a real number with $d<\beta$ , then

\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant\beta\cdot\frac{(d/\beta)^{\lceil d/2\rceil}}{1-\frac{d}{\beta}}.

Proof.

By the first bound in Lemma 14,

\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant\sum_{i=1}^{\lfloor d/2\rfloor}{{d}\choose i}i^{{d}-i}2^{-i}\beta^{i-d+1}=\beta\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}{{d}\choose i}2^{-{d}}\left(\frac{2i}{\beta}\right)^{{d}-i}.

Since ${d\choose i}\leqslant 2^{d}$ and $d<\beta$ ,

\beta\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}{{d}\choose i}2^{-{d}}\left(\frac{2i}{\beta}\right)^{{d}-i}\leqslant\beta\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}\left(\frac{d}{\beta}\right)^{{d}-i}\leqslant\beta\sum_{j=\left\lceil{d}/2\right\rceil}^{\infty}\left(\frac{d}{\beta}\right)^{j}=\beta\frac{({d}/\beta)^{\left\lceil{d}/2\right\rceil}}{1-\frac{d}{\beta}}.

∎

3.2 Proof of Lemma 11

In the rest of this section, we prove Lemma 11. To upper bound binomial coefficients when proving Lemma 20, we need the following two upper bounds; for completeness we include their short proofs.

Proposition 15.

If $k$ and $n$ are integers with $0<k<n$ , then

\binom{n}{k}\leqslant\frac{n^{n}}{k^{k}(n-k)^{n-k}}.

Proof.

By the Binomial Theorem, we have

n^{n}=(k+(n-k))^{n}=\sum_{i=0}^{n}\binom{n}{i}k^{i}(n-k)^{n-i}>\binom{n}{k}k^{k}(n-k)^{n-k}.

∎

Proposition 16.

If $i$ is a positive integer, then

\frac{(2i)!}{i!2^{i}}\leqslant 2i\left(\frac{2i}{e}\right)^{i}.

Proof.

It is well-known that $\frac{n^{n}}{e^{n-1}}\leqslant n!\leqslant\frac{n^{n+1}}{e^{n-1}}$ ; for example, see [6] for a complete proof. Direct computation gives

\frac{(2i)!}{i!2^{i}}\leqslant\left(\frac{(2i)^{2i+1}}{e^{2i-1}}\right)/\left(\frac{i^{i}}{e^{i-1}}\cdot 2^{i}\right)=\frac{(2i)^{i+1}}{e^{i}}.

∎

To prove Lemma 11, we estimate separately the summations of lower indexed terms and of higher indexed terms. (We remark that whenever we write $\sum_{i=a}^{b}$ , we mean that we sum over all terms with index $i$ satisfying $i\in{\mathbb{Z}}$ and $a\leqslant i\leqslant b$ , so $a$ and $b$ are not necessarily integers.)

Lemma 17.

Let $d$ and $R$ ^†^†margin: $d$ , $R$ be positive integers with $d\leqslant R$ . Let $\varepsilon$ , $c$ , and $\beta$ ^†^†margin: $\varepsilon$ , $c$ , $\beta$ be real numbers such that $0<\varepsilon<1$ and $0<c<\frac{\varepsilon}{2}$ and $\varepsilon R\leqslant\beta\leqslant R$ . Then

\sum_{i=1}^{cd}E_{i}(d)\beta^{i-d+1}\leqslant\frac{d\beta}{2}\cdot\left(\frac{2c}{\varepsilon}\right)^{(1-c)d}.

Moreover, if $d\geqslant\frac{\log(R^{2.5})}{(1-c)\log\frac{\varepsilon}{2c}}$ , then

\sum_{i=1}^{cd}E_{i}(d)\beta^{i-d+1}\leqslant\frac{1}{2}R^{-0.5}.

Proof.

By Lemma 14, and the fact that ${d\choose i}\leqslant 2^{d}$ ,

	$\displaystyle\sum_{i=1}^{cd}E_{i}(d)\beta^{i-d+1}$	$\displaystyle\leqslant\sum_{i=1}^{cd}{d\choose i}i^{d-i}2^{-i}\beta^{i-d+1}\leqslant\beta\sum_{i=1}^{cd}\left(\frac{2i}{\beta}\right)^{d-i}$
		$\displaystyle\leqslant\beta\sum_{i=1}^{cd}\left(\frac{2cd}{\beta}\right)^{d-i}\leqslant\beta\sum_{i=1}^{cd}\left(\frac{2cR}{\varepsilon R}\right)^{d-i}\leqslant\frac{d\beta}{2}\left(\frac{2c}{\varepsilon}\right)^{(1-c)d}.$

If also $d\geqslant\frac{\log(R^{2.5)}}{(1-c)\log\frac{\varepsilon}{2c}}$ , then we have

\displaystyle\sum_{i=1}^{cd}E_{i}(d)\beta^{i-d+1}\leqslant\frac{d\beta}{2}\left(\frac{2c}{\varepsilon}\right)^{(1-c)d}\leqslant\frac{d\beta}{2}\left(\frac{2c}{\varepsilon}\right)^{(\log(R^{2.5}))/\log(\varepsilon/(2c))}=\frac{d\beta}{2}R^{-2.5}\leqslant\frac{1}{2}R^{-0.5}.

∎

Our next lemma allows us to focus on partitions counted by $E_{i}(d)$ that have many parts of size at least 3, since it shows that these are at least $1/4$ of all partitions counted by $E_{i}(d)$ .

Lemma 18.

Let $n,k,j$ be positive integers with $j\leqslant k$ . Perform $k$ independent draws from $\{1,2,...,n\}$ with uniform probability. Let $p(j,k,n)$ be the probability that at most $j$ distinct elements are collected. If $2j\leqslant k$ and $2j\leqslant n$ and $n\geqslant 110$ , then $p(j,k,n)\leqslant 3/4$ .

Proof.

Clearly $p(j,k+1,n)\leqslant p(j,k,n)$ since drawing fewer times increases the likelihood of at most $j$ distinct draws. By the union bound and 15 above, letting $\varepsilon:=j/n$ , we get

	$\displaystyle p(j,k,n)$	$\displaystyle\leqslant p(j,2j,n)\leqslant\binom{n}{j}\left(\frac{j}{n}\right)^{2j}\leqslant\frac{n^{n}}{j^{j}(n-j)^{n-j}}\left(\frac{j}{n}\right)^{2j}$
		$\displaystyle=\frac{n^{n-2j}j^{j}}{(n-j)^{n-j}}=\frac{n^{n(1-2\varepsilon)}(\varepsilon n)^{\varepsilon n}}{(n(1-\varepsilon))^{n(1-\varepsilon)}}=\frac{\varepsilon^{\varepsilon n}}{(1-\varepsilon)^{n(1-\varepsilon)}}=\left[\frac{\varepsilon^{\varepsilon}}{(1-\varepsilon)^{(1-\varepsilon)}}\right]^{n}.$		(5)

Note that $\frac{1}{n}\leqslant\varepsilon\leqslant\frac{1}{2}$ . Let $f$ be the function $f(x)=x\log x-(1-x)\log(1-x)$ . So $p(j,k,n)\leqslant e^{n\cdot f(\varepsilon)}$ . Since $f^{\prime\prime}(x)=\frac{1-2x}{x(1-x)}>0$ for $\frac{1}{n}\leqslant x<\frac{1}{2}$ , we have that if $2j<n$ , then $\frac{1}{n}\leqslant\varepsilon\leqslant\frac{(n-1)}{2n}$ and

p(j,k,n)\leqslant e^{n\cdot f(\varepsilon)}\leqslant\max\{e^{n\cdot f(\frac{1}{n})},e^{n\cdot f(\frac{n-1}{2n})}\}.

Note that by Taylor’s approximation, $1-x\leqslant e^{-x}$ for every real number $x$ with $0<x<1$ . When $\varepsilon=1/n$ , we know $j=1$ , so by (5),

e^{n\cdot f(\frac{1}{n})}=\frac{n^{n-2}\cdot 1}{(n-1)^{n-1}}\leqslant\left(\frac{n}{n-1}\right)^{n-1}\cdot\frac{1}{n}=\left(1+\frac{1}{n-1}\right)^{n-1}\cdot\frac{1}{n}\leqslant\frac{e}{n}<\frac{3}{4}.

When $\varepsilon=\frac{n-1}{2n}$ , we know $j=\frac{n-1}{2}$ , so by (5),

e^{n\cdot f(\frac{n-1}{2n})}=\frac{n^{1}\left(\frac{n-1}{2}\right)^{(n-1)/2}}{\left(\frac{n+1}{2}\right)^{(n+1)/2}}=\frac{2n}{n+1}\left(\frac{n-1}{n+1}\right)^{\frac{n-1}{2}}\leqslant 2\left(1-\frac{2}{n+1}\right)^{\frac{n-1}{2}}\leqslant 2e^{-\frac{n-1}{n+1}}\leqslant 2e^{-\frac{109}{111}}<\frac{3}{4}.

This shows that if $2j<n$ , then $p(j,k,n)<\frac{3}{4}$ .

So it remains to consider the case $2j=n$ . Let $X$ be a random variable denoting the number of elements of $\{1,2,...,n\}$ that are not drawn. Since $2j=n$ , $p(j,k,n)\leqslant p(j,2j,2j)=\Pr[X\geqslant j]=\Pr[X\geqslant n/2]$ . By linearity of expectation, we have $E[X]=n(1-1/n)^{n}$ . By Markov’s inequality,

p(j,k,n)\leqslant\Pr[X\geqslant n/2]\leqslant\frac{E[X]}{n/2}=2(1-1/n)^{n}\leqslant\frac{2}{e}<\frac{3}{4}.

∎

Lemma 19.

Let $i$ and $d$ be positive integers with $i\leqslant d/2$ . Then for every integer $t$ with $1\leqslant t\leqslant\min\{\frac{d}{2}-i,\frac{i}{2}\}$ , the number of partitions of $[d]$ into $i$ parts each having size at least 2 for which there are at most $t$ parts of size at least 3 is at most $p(t,d-2i,i)\cdot E_{i}(d)$ , where the function $p$ is defined in Lemma 18.

Proof.

For every partition $\mathcal{P}$ of $[d]$ into $i$ parts each having size at least 2, let $Z_{\mathcal{P}}=\{\{m_{P},m^{\prime}_{P}\}:P\in\mathcal{P}\}$ , where $m_{P}$ and $m_{P}^{\prime}$ are the minimum and the second minimum of the part $P$ of $\mathcal{P}$ , respectively. Note that each $Z_{\mathcal{P}}$ is a pairing of $2i$ elements of $[d]$ . For every pairing $Z$ of $2i$ elements of $[d]$ , let $A_{Z}$ be the set consisting of the partitions $\mathcal{P}$ of $[d]$ into $i$ parts each having size at least 2 with $Z_{\mathcal{P}}=Z$ . Hence $\{A_{Z}:Z$ is a pairing of $2i$ elements of $[d]\}$ is a partition of the set of partitions of $[d]$ into $i$ parts each having size at least 2. Note that for every such a pairing $Z$ , there exists a bijection $\iota_{Z}$ from $A_{Z}$ to $[i]^{d-2i}$ defined by for every $P\in A_{Z}$ and $j\in[d-2i]$ , the $j$ -th entry of $\iota_{Z}(P)$ equals $k$ , where $k$ is the integer such that the $j$ -th smallest element in $[d]$ not used in $Z$ is contained in the part $P$ of $\mathcal{P}$ for which $m_{P}$ is the $k$ -th smallest element in $\{m_{P^{\prime}}:P^{\prime}\in\mathcal{P}\}$ . Hence for every integer $t$ with $1\leqslant t\leqslant\min\{\frac{d}{2}-i,\frac{i}{2}\}$ , the number of partitions in $A_{Z}$ having at most $t$ parts of size at least 3 equals $p(t,d-2i,i)\cdot|A_{Z}|$ . ∎

Our next lemma provides the key step in proving our upper bound on the sum of the higher indexed terms.

Lemma 20.

Let $i$ and $d$ be integers with $d\geqslant 110$ . If $0.3d\leqslant i\leqslant d/2$ , then $E_{i}(d)\leqslant 8i(0.6251d)^{d-i}$ .

Proof.

Among the partitions counted by $E_{i}(d)$ , the fraction of partitions contain at most $\min\{\frac{d}{2}-i,\frac{i}{2}\}$ parts of size at least 3 is $p(\min\{\frac{d}{2}-i,\frac{i}{2}\},d-2i,i)$ by Lemma 19; by Lemma 18, this fraction is at most $3/4$ . So it suffices to show that the number of partitions of $[d]$ into $i$ parts each having size at least 2 with more than $\min\{\frac{d}{2}-i,\frac{i}{2}\}$ parts of size at least 3 is at most $2i(0.6251d)^{d-i}$ . (Hence we may assume $i<\frac{d}{2}$ , since $i=\frac{d}{2}$ implies that $\min\{\frac{d}{2}-i,\frac{i}{2}\}=\frac{d}{2}-i=0$ and it is impossible to have a partition of $[d]$ with $i=\frac{d}{2}$ parts of size at least 2 and more than 0 part of size at least 3.)

To count these partitions, we first draw $2i$ elements that we pair together. Then, for each of the $d-2i$ remaining elements, we assign it to one of the $i$ parts formed by the pairing. For each part of size at least 3, there are at least 3 choices for the initial pair of elements. Thus, there are at least $3^{j}$ ways to construct a partition with $j$ parts of size at least 3 by this process. Since we only count those with $j>\min\{\frac{d}{2}-i,\frac{i}{2}\}$ , we get the inequality

\frac{1}{4}E_{i}(d)\leqslant\binom{d}{2i}\cdot\frac{(2i)!}{i!2^{i}}\cdot\frac{i^{d-2i}}{3^{\min\{\frac{d}{2}-i,\frac{i}{2}\}}}.

We first assume $\min\{\frac{d}{2}-i,\frac{i}{2}\}=\frac{d}{2}-i$ . Then

	$\displaystyle\frac{1}{4}E_{i}(d)$	$\displaystyle\leqslant\binom{d}{2i}\cdot\frac{(2i)!}{i!2^{i}}\cdot\frac{i^{d-2i}}{3^{d/2-i}}$
		$\displaystyle\leqslant\frac{d^{d}}{(2i)^{2i}(d-2i)^{d-2i}}\cdot 2i\left(\frac{2i}{e}\right)^{i}\cdot\left(\frac{i}{\sqrt{3}}\right)^{d-2i}$
		$\displaystyle=2i\frac{d^{d}}{(2ei)^{i}}\left(\frac{i}{\sqrt{3}(d-2i)}\right)^{d-2i},$

where the second inequality follows from 15 and 16. Letting $\varepsilon:=i/d$ ,

	$\displaystyle E_{i}(d)$	$\displaystyle\leqslant 4\cdot 2i\cdot d^{d-i}\left[\frac{d^{i}i^{d-2i}}{(2ei)^{i}(\sqrt{3}(d-2i))^{d-2i}}\right]$
		$\displaystyle=4\cdot 2i\cdot d^{d-i}\left[\frac{d^{\varepsilon d}{(\varepsilon d)}^{d-2\varepsilon d}}{(2e\varepsilon d)^{\varepsilon d}(\sqrt{3}d(1-2\varepsilon))^{d-2\varepsilon d}}\right]$
		$\displaystyle=4\cdot 2i\cdot d^{d-i}\left[\frac{{\varepsilon}^{d(1-2\varepsilon)}}{(2e\varepsilon)^{\varepsilon d}(\sqrt{3}(1-2\varepsilon))^{d-2\varepsilon d}}\right]$
		$\displaystyle=4\cdot 2i\cdot d^{d-i}\left[\frac{{\varepsilon}^{(1-2\varepsilon)}}{(2e\varepsilon)^{\varepsilon}(\sqrt{3}(1-2\varepsilon))^{1-2\varepsilon}}\right]^{d}$
		$\displaystyle=4\cdot 2i\cdot\left[d\left[\frac{{\varepsilon}^{(1-2\varepsilon)}}{(2e\varepsilon)^{\varepsilon}(\sqrt{3}(1-2\varepsilon))^{1-2\varepsilon}}\right]^{\frac{1}{1-\varepsilon}}\right]^{d-i}.$

Let

\displaystyle f(\varepsilon)

\displaystyle:=\left[\frac{{\varepsilon}^{(1-2\varepsilon)}}{(2e\varepsilon)^{\varepsilon}(\sqrt{3}(1-2\varepsilon))^{1-2\varepsilon}}\right]^{\frac{1}{1-\varepsilon}}.

Since $\min\{\frac{d}{2}-i,\frac{i}{2}\}=\frac{d}{2}-i$ , we have $\frac{d}{3}\leqslant i<\frac{d}{2}$ , so $\frac{1}{3}\leqslant\varepsilon<\frac{1}{2}$ . With Mathematica we know that $\max_{1/3\leqslant\varepsilon\leqslant 1/2}f(\varepsilon)\leqslant 0.6251$ . Thus, we conclude that $E_{i}(d)\leqslant 4\cdot 2i\cdot(0.6251d)^{d-i}$ , as claimed.

Now we assume $\min\{\frac{d}{2}-i,\frac{i}{2}\}=\frac{i}{2}$ . That is, $0.3d\leqslant i\leqslant\frac{d}{3}$ . Then

	$\displaystyle\frac{1}{4}E_{i}(d)$	$\displaystyle\leqslant\binom{d}{2i}\cdot\frac{(2i)!}{i!2^{i}}\cdot\frac{i^{d-2i}}{3^{i/2}}$
		$\displaystyle\leqslant\frac{d^{d}}{(2i)^{2i}(d-2i)^{d-2i}}\cdot 2i\left(\frac{2i}{e\sqrt{3}}\right)^{i}\cdot i^{d-2i}$
		$\displaystyle=2i\frac{d^{d}}{(2\sqrt{3}ei)^{i}}\left(\frac{i}{d-2i}\right)^{d-2i},$

where the second inequality follows from 15 and 16. Letting $\varepsilon:=i/d$ ,

	$\displaystyle E_{i}(d)$	$\displaystyle\leqslant 4\cdot 2i\cdot d^{d-i}\left[\frac{d^{i}i^{d-2i}}{(2\sqrt{3}ei)^{i}(d-2i)^{d-2i}}\right]$
		$\displaystyle=4\cdot 2i\cdot d^{d-i}\left[\frac{d^{\varepsilon d}{(\varepsilon d)}^{d-2\varepsilon d}}{(2\sqrt{3}e\varepsilon d)^{\varepsilon d}(d(1-2\varepsilon))^{d-2\varepsilon d}}\right]$
		$\displaystyle=4\cdot 2i\cdot d^{d-i}\left[\frac{{\varepsilon}^{d(1-2\varepsilon)}}{(2\sqrt{3}e\varepsilon)^{\varepsilon d}(1-2\varepsilon)^{d-2\varepsilon d}}\right]$
		$\displaystyle=4\cdot 2i\cdot d^{d-i}\left[\frac{{\varepsilon}^{(1-2\varepsilon)}}{(2\sqrt{3}e\varepsilon)^{\varepsilon}(1-2\varepsilon)^{1-2\varepsilon}}\right]^{d}$
		$\displaystyle=4\cdot 2i\cdot\left[d\left[\frac{{\varepsilon}^{(1-2\varepsilon)}}{(2\sqrt{3}e\varepsilon)^{\varepsilon}(1-2\varepsilon)^{1-2\varepsilon}}\right]^{\frac{1}{1-\varepsilon}}\right]^{d-i}.$

Let

\displaystyle g(\varepsilon)

\displaystyle:=\left[\frac{{\varepsilon}^{(1-2\varepsilon)}}{(2\sqrt{3}e\varepsilon)^{\varepsilon}(1-2\varepsilon)^{1-2\varepsilon}}\right]^{\frac{1}{1-\varepsilon}}.

Since $0.3d\leqslant i\leqslant\frac{d}{3}$ , so $0.3\leqslant\varepsilon\leqslant\frac{1}{3}$ . With Mathematica we know that $\max_{0.3\leqslant\varepsilon\leqslant 1/3}g(\varepsilon)\leqslant 0.57<0.6251$ . Thus, we conclude that $E_{i}(d)\leqslant 4\cdot 2i\cdot(0.6251d)^{d-i}$ , as claimed. ∎

Now we can finally use the previous three lemmas to bound the sum of higher indexed terms.

Lemma 21.

Let $d$ and $R$ ^†^†margin: $d$ , $R$ be positive integers with $110\leqslant d\leqslant R$ . If $\varepsilon$ , $c$ , and $\beta$ ^†^†margin: $\varepsilon$ , $c$ , $\beta$ are real numbers such that $0.6251\leqslant\varepsilon<1$ and $0.3\leqslant c<\frac{\varepsilon}{2}$ and $\varepsilon R\leqslant\beta\leqslant R$ , then

\sum_{i=cd}^{\lfloor d/2\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant 2R^{3}\left(\frac{\varepsilon}{0.6251}\right)^{-d/2}.

Moreover, if $d\geqslant\frac{7.6\log R}{\log(\varepsilon/0.6251)}$ , then

\sum_{i=cd}^{\lfloor d/2\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant\frac{1}{2}R^{-0.5}.

Proof.

By Lemma 20, we have

	$\displaystyle\sum_{i=cd}^{d/2}E_{i}(d)\beta^{i-d+1}$	$\displaystyle\leqslant\sum_{i=cd}^{d/2}8i(0.6251d)^{d-i}\beta^{i-d+1}$
		$\displaystyle=8\beta\sum_{i=cd}^{d/2}i\left(\frac{\beta}{0.6251d}\right)^{i-d}$
		$\displaystyle=8\beta\sum_{i=cd}^{d/2}i\left(\frac{\varepsilon R}{0.6251R}\right)^{i-d}$
		$\displaystyle\leqslant 2R^{3}\left(\frac{\varepsilon}{0.6251}\right)^{-d/2}.$

If also $d\geqslant(7.6\log R)/(\log(\varepsilon/0.6251))$ , then

\sum_{i=cd}^{d/2}E_{i}(d)\beta^{i-d+1}\leqslant 2R^{3}\left(\frac{\varepsilon}{0.6251}\right)^{(-3.8\log R)/(\log(\varepsilon/0.6251))}=2R^{3}(R^{-3.8})=2R^{-0.8}\leqslant\frac{1}{2}R^{-0.5}.

∎

Corollary 22.

Lemma 11 is true.

Proof.

This follows immediately from Lemmas 17 and 21. ∎

4 Fractional Coloring

The goal of this section is to prove Theorem 7, which is an asymptotically optimal theorem for fractional proper conflict-free coloring. The following is a restatement.

Theorem 23.

For every $\varepsilon>0$ , there exists $d_{0}$ such that if $\Delta$ is a real number with $\Delta\geqslant d_{0}$ and $G$ is a graph with maximum degree at most $\Delta$ , then $(G,\mathcal{H})$ is fractionally properly conflict-free $(1+\varepsilon)\Delta$ -colorable for any hypergraph $\mathcal{H}$ with $V(\mathcal{H})=V(G)$ and ${\rm{rank}}(\mathcal{H})\leqslant\Delta$ .

To prove the theorem, we consider the dual problem of fractional coloring that transforms the problem to finding maximum weighted stable sets with specific properties and is easier to work with. We state the dual problem and prove the duality in Lemma 24. The remaining task, Lemma 25, is to construct a desired stable set randomly. We first randomly construct an induced subgraph with small maximum degree (and hence with small chromatic number) with a very large fraction of the weight by using concentration inequalities, and then choose a stable set from it that hits a large fraction of the weight.

Lemma 24.

If $G$ is a graph and $\mathcal{H}$ is a hypergraph with $V(\mathcal{H})=V(G)$ , then for every positive real number $t$ , the following two statements are equivalent.

(1)

$(G,\mathcal{H})$ is fractionally properly conflict-free $t$ -colorable.
(2)

For any functions $f:V(G)\rightarrow{\mathbb{R}}_{\geqslant 0}$ and $g:E(\mathcal{H})\rightarrow{\mathbb{R}}_{\geqslant 0}$ with $\sum_{v\in V(G)}f(v)+\sum_{z\in E(\mathcal{H})}g(z)=1$ , there exists a stable set $S$ in $G$ such that $\sum_{v\in S}f(v)+\sum_{z\in E(\mathcal{H}),|z\cap S|=1}g(z)\geqslant\frac{1}{t}$ .

Lemma 25.

For every $\varepsilon>0$ , there exists an integer $d_{0}$ such that if $\Delta\geqslant d_{0}$ , $G$ is a graph with maximum degree at most $\Delta$ , $\mathcal{H}$ a hypergraph with $V(\mathcal{H})=V(G)$ and ${\rm{rank}}(\mathcal{H})\leqslant\Delta$ , and $f:V(G)\rightarrow{\mathbb{R}}_{\geqslant 0}$ and $g:E(\mathcal{H})\rightarrow{\mathbb{R}}_{\geqslant 0}$ are functions with $\sum_{v\in V(G)}f(v)+\sum_{z\in E(\mathcal{H})}g(z)=1$ , then there exists a stable set $S$ of $G$ such that $\sum_{v\in S}f(v)+\sum_{z\in E(\mathcal{H}),|z\cap S|=1}g(z)\geqslant\frac{(1-\varepsilon)^{2}}{(1+2\varepsilon)\Delta}$ .

Before proving Lemmas 24 and 25, we prove Theorem 23 assuming the lemmas.

Proof of Theorem 23.

To show $(G,\mathcal{H})$ is fractionally properly conflict-free $(1+\varepsilon)\Delta$ -colorable, by Lemma 24, it suffices, given functions $f:V(G)\rightarrow{\mathbb{R}}_{\geqslant 0}$ and $g:E(\mathcal{H})\rightarrow{\mathbb{R}}_{\geqslant 0}$ with $\sum_{v\in V(G)}f(v)+\sum_{z\in E(\mathcal{H})}g(z)=1$ , to show there is a stable set $S$ of $G$ with $\sum_{v\in S}f(v)+\sum_{z\in E(\mathcal{H}),|z\cap S|=1}g(z)\geqslant\frac{1}{(1+\varepsilon)\Delta}$ .

By Lemma 25, for every $\varepsilon_{0}>0$ , there exists an integer $d_{0}$ such that if $\Delta\geqslant d_{0}$ , then there exists a stable set $S$ in $G$ with $\sum_{v\in S}f(v)+\sum_{z\in E(\mathcal{H}),|z\cap S|=1}g(z)\geqslant\frac{(1-\varepsilon_{0})^{2}}{(1+2\varepsilon_{0})\Delta}$ . Since $\lim_{x\to 0}\frac{1+2x}{(1-x)^{2}}=1$ , there exists $\varepsilon_{0}>0$ such that $\frac{1+2\varepsilon_{0}}{(1-\varepsilon_{0})^{2}}\leqslant 1+\varepsilon$ . Let $d_{0}$ be the constant mentioned in Lemma 25 for $\varepsilon_{0}$ . Now we are done by Lemma 25. ∎

Proof of Lemma 24.

We begin by formulating fractional proper conflict-free coloring as a linear program. Let $A_{1}$ ^†^†margin: $A_{1}$ be a matrix with rows indexed by $V(G)$ and columns indexed by the set of all stable sets in $G$ , such that for each $v\in V(G)$ and stable set $S$ in $G$ , the entry of $A_{1}$ in the $v$ -th row and $S$ -th column equals 1 if $v\in S$ and equals 0 otherwise. Let $A_{2}$ ^†^†margin: $A_{2}$ be a matrix with rows indexed by $E(\mathcal{H})$ , and columns indexed by the set of all stable sets in $G$ , in the same order as in $A_{1}$ , and for each $z\in E(\mathcal{H})$ and stable set $S$ in $G$ , the entry of $A_{2}$ in the $z$ -th row and $S$ -th column equals 1 if $|z\cap S|=1$ and equals 0 otherwise. Let $A$ ^†^†margin: $A$ be the matrix with $|V(G)|+|E(\mathcal{H})|$ rows such that its first $|V(G)|$ rows form $A_{1}$ and its last $|E(\mathcal{H})|$ rows form $A_{2}$ . In the rest of proof, we will frequently denote by 1 a vector all of whose entries are 1.

It is easy to see that $(G,\mathcal{H})$ is fractionally properly conflict-free $t$ -colorable if and only if there exists a nonnegative rational vector $x$ with $1^{T}x\leqslant t$ and $Ax\geqslant 1$ , where $x\in[0,1]^{|\mathcal{I}(G)|}$ , where $\mathcal{I}(G)$ is the set of all independent sets of $G$ . Since $A$ is an integral matrix, the fractional proper conflict-free chromatic number of $(G,\mathcal{H})$ equals $\min_{x}1^{T}x$ over nonnegative real vectors $x$ with $Ax\geqslant 1$ ; moreover, this minimum is attained by a nonnegative rational vector $x$ .

Now we prove that (1) implies (2). Assume that the fractional proper conflict-free chromatic number of $(G,\mathcal{H})$ is at most $t$ . So there exist positive integers $a,b$ with $a/b\leqslant t$ and a proper^†^†margin: $t$ , $a$ , $b$ conflict-free $(a:b)$ -coloring $\varphi$ of $(G,\mathcal{H})$ . Let $f,g$ be functions as given in (2). Since $\varphi$ is a proper conflict-free^†^†margin: $f$ , $g$ , $\varphi$ $(a:b)$ -coloring of $(G,\mathcal{H})$ , by the definition of $(a:b)$ -coloring,

	$\displaystyle\sum_{i=1}^{a}\left(\sum_{v\in\varphi^{-1}(i)}f(v)+\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ \|z\cap\varphi^{-1}(i)\|=1\end{subarray}}g(z)\right)$	$\displaystyle\geqslant b\sum_{v\in V(G)}f(v)+\sum_{i=1}^{a}\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ \|z\cap\varphi^{-1}(i)\|=1\end{subarray}}g(z)$
		$\displaystyle\geqslant b\sum_{v\in V(G)}f(v)+b\sum_{z\in E(\mathcal{H})}g(z)=b.$

By the pigeonhole principle, there exists $i\in[a]$ with $\sum_{v\in\varphi^{-1}(i)}f(v)+\sum_{z\in E(\mathcal{H}),|z\cap\varphi^{-1}(i)|=1}g(z)\geqslant\frac{b}{a}\geqslant\frac{1}{t}$ . So (2) holds, since $\varphi^{-1}(i)$ is a stable set.

Now we prove that (2) implies (1). Assume that (2) holds. Suppose to the contrary that the fractional proper conflict-free chromatic number of $(G,\mathcal{H})$ is greater than $t$ ^†^†margin: $t$ . By the duality theorem of linear programming, there exist nonnegative functions $f_{1}:V(G)\rightarrow{\mathbb{R}}_{\geqslant 0}$ and $g_{1}:E(\mathcal{H})\rightarrow{\mathbb{R}}_{\geqslant 0}$ ^†^†margin: $f_{1}$ , $g_{1}$ such that $\sum_{v\in V(G)}f_{1}(v)+\sum_{z\in E(\mathcal{H})}g_{1}(z)>t$ , and for every stable set $S$ in $G$ , we have $\sum_{v\in S}f_{1}(v)+\sum_{z\in E(\mathcal{H}),|z\cap S|=1}g_{1}(z)\leqslant 1$ . Let $s:=\sum_{v\in V(G)}f_{1}(v)+\sum_{z\in E(\mathcal{H})}g_{1}(z)$ .^†^†margin: $s$ Note that $s>t$ . Let $f$ and $g$ be the functions such that $f:=\frac{1}{s}\cdot f_{1}$ and $g:=\frac{1}{s}\cdot g_{1}$ .^†^†margin: $f$ , $g$ Hence $\sum_{v\in V(G)}f(v)+\sum_{z\in E(\mathcal{H})}g(z)=\frac{1}{s}\cdot(\sum_{v\in V(G)}f_{1}(v)+\sum_{z\in E(\mathcal{H})}g_{1}(z))=1$ , and for every stable set $S$ in $G$ , we have $\sum_{v\in S}f(v)+\sum_{z\in E(\mathcal{H}),|z\cap S|=1}g(z)=\frac{1}{s}\cdot(\sum_{v\in S}f_{1}(v)+\sum_{z\in E(\mathcal{H}),|z\cap S|=1}g_{1}(z))\leqslant\frac{1}{s}<\frac{1}{t}$ , contradicting (2). ∎

To prove Lemma 25, the second main step in our plan, we need the following three lemmas to bound various probabilities. The first is the Chernoff Bound, which is well-known (proofs are available in most probability textbooks). The second and third are straightforward applications of elementary calculus, so we defer their proofs to the appendix.

Lemma 26 (Chernoff bound).

Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables such that for every $i\in[n]$ , we have $X_{i}=1$ with probability $p$ and $X_{i}=0$ with probability $1-p$ . Let $X:=\sum_{i=1}^{n}X_{i}$ . For every $\delta$ with $0<\delta<1$ , we have $P(|X-{\mathbb{E}}[X]|\geqslant\delta{\mathbb{E}}[X])\leqslant 2e^{-\delta^{2}{\mathbb{E}}[X]/3}$ .

Lemma 27.

Let $p$ be a real number with $0<p<1$ . Let $a,b$ be real numbers. If $f(x):=x(1-p)^{x}$ for every real number $x$ , then $f(x)\geqslant\min\{f(a),f(b)\}$ for every $x$ with $a\leqslant x\leqslant b$ .

Lemma 28.

$\lim_{x\to\infty}x(1-\frac{\log x}{x})^{x}=1$ .

Now we prove Lemma 25, completing the proof of Theorem 23. For convenience, we restate it.

Lemma 25. For every $\varepsilon>0$ , there exists an integer $d_{0}$ such that if $\Delta\geqslant d_{0}$ , $G$ is a graph with maximum degree at most $\Delta$ , $\mathcal{H}$ a hypergraph with $V(\mathcal{H})=V(G)$ and ${\rm{rank}}(\mathcal{H})\leqslant\Delta$ , and $f:V(G)\rightarrow{\mathbb{R}}_{\geqslant 0}$ and $g:E(\mathcal{H})\rightarrow{\mathbb{R}}_{\geqslant 0}$ are functions with $\sum_{v\in V(G)}f(v)+\sum_{z\in E(\mathcal{H})}g(z)=1$ , then there exists a stable set $S$ of $G$ such that $\sum_{v\in S}f(v)+\sum_{z\in E(\mathcal{H}),|z\cap S|=1}g(z)\geqslant\frac{(1-\varepsilon)^{2}}{(1+2\varepsilon)\Delta}$ .

Proof.

Fix $\varepsilon>0$ .^†^†margin: $\varepsilon$ Note that $\lim_{x\to\infty}x^{-\varepsilon^{2}/3}=0=\lim_{x\to\infty}\frac{\log x}{x}$ and recall (from Lemma 28), that $\lim_{x\to\infty}x(1-\frac{\log x}{x})^{x}=1$ . So there exists an integer $d_{0}$ ^†^†margin: $d_{0}$ such that for every real number $d$ , if $d\geqslant d_{0}$ , then $\varepsilon\geqslant\max\{2d^{-\varepsilon^{2}/3},\frac{\log d}{d},1-d(1-\frac{\log d}{d})^{d},1/\log d\}$ . Let $\Delta$ , $G$ , $\mathcal{H}$ , and functions $f,g$ ^†^†margin: $\Delta$ , $G$ , $\mathcal{H}$ , $f$ , $g$ be as prescribed in the lemma. Let $p:=\frac{\log\Delta}{\Delta}$ .^†^†margin: $p$

Let $A$ ^†^†margin: $A$ be the subset of $V(G)$ obtained by, for each vertex $v$ of $G$ , independently putting $v$ into $A$ with probability $p$ . For each $v\in V(G)$ , let $X_{v}$ ^†^†margin: $X_{v}$ be the random variable with $X_{v}=1$ if $v\in A$ , and $X_{v}=0$ otherwise. For each $v\in V(G)$ , let $Y_{v}$ ^†^†margin: $Y_{v}$ be the random variable such that $Y_{v}=1$ if $X_{v}=1$ and there are more than $(1+\varepsilon)p\Delta$ neighbors $w$ of $v$ with $X_{w}=1$ ; otherwise, $Y_{v}=0$ . Let $B:=\{v\in V(G):X_{v}=1,Y_{v}=0\}$ .^†^†margin: $B$ Hence

{\mathbb{E}}[\sum_{v\in B}f(v)+\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ |z\cap B|=1\end{subarray}}g(z)]=\sum_{v\in V(G)}f(v)\cdot P(v\in B)+\sum_{z\in E(\mathcal{H})}g(z)\cdot P(|z\cap B|=1).

For every $v\in V(G)$ , by the Chernoff bound (Lemma 26),

	$\displaystyle P(Y_{v}=1)$	$\displaystyle=P(X_{v}=1\mbox{ and }\sum_{w\in N(v)}X_{w}>(1+\varepsilon)p\Delta)$
		$\displaystyle=P(X_{v}=1)\cdot P\left(\sum_{w\in N(v)}X_{w}>(1+\varepsilon)\frac{\Delta}{d(v)}\cdot{\mathbb{E}}[\sum_{w\in N(v)}X_{w}]\right)$
		$\displaystyle\leqslant p\cdot 2e^{-\frac{1}{3}((1+\varepsilon)\frac{\Delta}{d(v)}-1)^{2}{\mathbb{E}}[\sum_{w\in N(v)}X_{w}]}$
		$\displaystyle=2p\cdot e^{-\frac{1}{3}((1+\varepsilon)\frac{\Delta}{d(v)}-1)^{2}\cdot p\cdot d(v)}$
		$\displaystyle=2p\cdot e^{-\frac{1}{3}((1+\varepsilon)\frac{\Delta}{\sqrt{d(v)}}-\sqrt{d(v)})^{2}\cdot p}$
		$\displaystyle\leqslant 2p\cdot e^{-\frac{1}{3}(\varepsilon\frac{\Delta}{\sqrt{d(v)}})^{2}\cdot p}$
		$\displaystyle\leqslant 2p\cdot e^{-\frac{1}{3}\varepsilon^{2}\Delta p}=2pe^{-\frac{1}{3}\varepsilon^{2}\log\Delta}=2p\cdot\Delta^{-\varepsilon^{2}/3}.$

Since $\Delta\geqslant d_{0}$ , by our choice of $d_{0}$ , we know $2\Delta^{-\varepsilon^{2}/3}\leqslant\varepsilon$ . So $P(Y_{v}=1)\leqslant p\varepsilon$ . Hence, for every $v\in V(G)$ , we know $P(v\in B)=P(X_{v}=1,Y_{v}=0)=P(X_{v}=1)-P(X_{v}=1,Y_{v}=1)=P(X_{v}=1)-P(Y_{v}=1)\geqslant p-p\varepsilon=p\cdot(1-\varepsilon)$ .

For each $z\in E(\mathcal{H})$ , note that $P(|z\cap B|=1)\geqslant\sum_{u\in z}P(X_{u}=1,Y_{u}=0,X_{w}=0$ for every $w\in z\setminus\{u\})$ . For each vertex $z\in E(\mathcal{H})$ and $u\in z$ , by the Chernoff bound,

	$\displaystyle~{}~{}~{}~{}P(Y_{u}=1\|X_{u}=1\mbox{ and }X_{w}=0{\rm\ for\ every\ }w\in z-\{u\})$
	$\displaystyle=P(\sum_{w\in N(u)\setminus z}X_{w}>(1+\varepsilon)p\Delta)$
	$\displaystyle=P(\sum_{w\in N(u)\setminus z}X_{w}>(1+\varepsilon)\frac{\Delta}{\|N(u)\setminus z\|}{\mathbb{E}}[\sum_{w\in N(u)\setminus z}X_{w}])$
	$\displaystyle\leqslant 2e^{-\frac{((1+\varepsilon)\frac{\Delta}{\|N(u)\setminus z\|}-1)^{2}}{3}{\mathbb{E}}[\sum_{w\in N(u)\setminus z}X_{w}]}$
	$\displaystyle=2e^{-\frac{((1+\varepsilon)\frac{\Delta}{\|N(u)\setminus z\|}-1)^{2}}{3}p\|N(u)\setminus z\|}$
	$\displaystyle=2e^{-((1+\varepsilon)\frac{\Delta}{\sqrt{\|N(u)\setminus z\|}}-\sqrt{\|N(u)\setminus z\|})^{2}\cdot\frac{p}{3}}$
	$\displaystyle\leqslant 2e^{-(\varepsilon\frac{\Delta}{\sqrt{\|N(u)\setminus z\|}})^{2}\cdot\frac{p}{3}}$
	$\displaystyle\leqslant 2e^{-\varepsilon^{2}\Delta p/3}=2e^{-\varepsilon^{2}\log\Delta/3}=2\Delta^{-\varepsilon^{2}/3}\leqslant\varepsilon.$

So $P(Y_{u}=0|X_{u}=1,X_{w}=0$ for every $w\in z-\{u\})\geqslant 1-\varepsilon$ . For each $z\in E(\mathcal{H})$ and $u\in z$ , we have $P(X_{u}=1,X_{w}=0$ for every $w\in z-\{u\})=p(1-p)^{|z|-1}\geqslant p(1-p)^{|z|}$ . Hence, for each $z\in E(\mathcal{H})$ and $u\in z$ ,

	$\displaystyle~{}~{}~{}~{}P(X_{u}=1\mbox{ and }Y_{u}=0\mbox{ and }X_{w}=0{\rm\ for\ all\ }w\in z\setminus\{u\})$
	$\displaystyle=P(X_{u}=1\mbox{ and }X_{w}=0{\rm\ for\ all\ }w\in z\setminus\{u\})\cdot P(Y_{u}=0\|X_{u}=1\mbox{ and }X_{w}=0{\rm\ for\ all\ }w\in z\setminus\{u\})$
	$\displaystyle\geqslant p(1-p)^{\|z\|}\cdot(1-\varepsilon).$

All $z\in E(\mathcal{H})$ satisfy $1\leqslant|z|\leqslant\Delta$ , so Lemma 27 gives $|z|(1-p)^{|z|}\geqslant\min\{1-p,\Delta(1-p)^{\Delta}\}$ . Since $\Delta\geqslant d_{0}$ , we get $1-p=1-\frac{\log\Delta}{\Delta}\geqslant 1-\varepsilon$ and $\Delta(1-p)^{\Delta}=\Delta(1-\frac{\log\Delta}{\Delta})^{\Delta}\geqslant 1-\varepsilon$ . Thus, by summing the probabilities of some disjoint events, we have

	$\displaystyle P(\|z\cap B\|=1)$	$\displaystyle\geqslant\sum_{u\in z}P(X_{u}=1,Y_{u}=0,X_{w}=0{\rm\ for\ every}\ w\in z\backslash\{u\})$
		$\displaystyle\geqslant\|z\|\cdot p(1-p)^{\|z\|}\cdot(1-\varepsilon)$
		$\displaystyle=(1-\varepsilon)p\cdot\|z\|(1-p)^{\|z\|}$
		$\displaystyle\geqslant(1-\varepsilon)p\cdot\min\{1-p,\Delta(1-p)^{\Delta}\}$
		$\displaystyle\geqslant(1-\varepsilon)p\cdot(1-\varepsilon)=(1-\varepsilon)^{2}p.$

Hence

	$\displaystyle{\mathbb{E}}[\sum_{v\in B}f(v)+\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ \|z\cap B\|=1\end{subarray}}g(z)]$	$\displaystyle=\sum_{v\in V(G)}f(v)\cdot P(v\in B)+\sum_{z\in E(\mathcal{H})}g(z)\cdot P(\|z\cap B\|=1)$
		$\displaystyle\geqslant p(1-\varepsilon)\sum_{v\in V(G)}f(v)+(1-\varepsilon)^{2}p\sum_{z\in E(\mathcal{H})}g(z)$
		$\displaystyle\geqslant p(1-\varepsilon)^{2}(\sum_{v\in V(G)}f(v)+\sum_{z\in E(\mathcal{H})}g(z))=p(1-\varepsilon)^{2}.$

So there exists $B^{*}\subseteq V(G)$ such that $G[B^{*}]$ has maximum degree at most $(1+\varepsilon)p\Delta$ and

\sum_{v\in B^{*}}f(v)+\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ |z\cap B^{*}|=1\end{subarray}}g(z)\geqslant p(1-\varepsilon)^{2}.

Since $G[B^{*}]$ has maximum degree at most $(1+\varepsilon)p\Delta$ , $G[B^{*}]$ is properly $(\lfloor(1+\varepsilon)p\Delta\rfloor+1)$ -colorable. Hence $B^{*}$ is a union of disjoint stable sets $S_{1},S_{2},...,S_{\lfloor(1+\varepsilon)p\Delta\rfloor+1}$ in $G$ . Note that for every $z\in E(\mathcal{H})$ , if $|z\cap B^{*}|=1$ , then $|z\cap S_{j}|=1$ for some $j$ . So

\sum_{j=1}^{\lfloor(1+\varepsilon)p\Delta\rfloor+1}\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ |z\cap S_{j}|=1\end{subarray}}g(z)\geqslant\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ |z\cap B^{*}|=1\end{subarray}}g(z).

Hence

	$\displaystyle\sum_{j=1}^{\lfloor(1+\varepsilon)p\Delta\rfloor+1}(\sum_{v\in S_{j}}f(v)+\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ \|z\cap S_{j}\|=1\end{subarray}}g(z))$	$\displaystyle\geqslant\sum_{v\in B^{}}f(v)+\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ \|z\cap B^{}\|=1\end{subarray}}g(z)$
		$\displaystyle\geqslant p(1-\varepsilon)^{2}.$

Therefore, there exists a subset $S$ of $B^{*}$ such that $S$ is a stable set in $G$ and

	$\displaystyle\sum_{v\in S}f(v)+\sum_{\begin{subarray}{c}z\in E(\mathcal{H})\\ \|z\cap S\|=1\end{subarray}}g(z)\geqslant$	$\displaystyle\frac{1}{\lfloor(1+\varepsilon)p\Delta\rfloor+1}\cdot p(1-\varepsilon)^{2}$
	$\displaystyle\geqslant$	$\displaystyle\frac{1}{(1+2\varepsilon)p\Delta}\cdot p(1-\varepsilon)^{2}=\frac{(1-\varepsilon)^{2}}{(1+2\varepsilon)\Delta}.$

∎

Finally, we prove Corollary 8. We restate it here.

Corollary 8. For every $\varepsilon>0$ , there exists $d_{0}$ such that if $\Delta\geqslant d_{0}$ and $G$ is a graph with maximum degree at most $\Delta$ , then there exists a proper $(a:b)$ -coloring $\varphi$ of $G$ for some positive integers $a$ and $b$ with $a\leqslant(1+\varepsilon)\Delta b$ such that

1.

$\varphi$ is a fractionally proper conflict-free $(a:b)$ -coloring of $G$ ,
2.

for any set $C$ of colors with size less than $5b/2$ , every component of the subgraph of $G$ induced by the vertices that use only colors in $C$ has at most two vertices, and
3.

$|\varphi(v)\cap\varphi(w)|\leqslant b/2$ for any distinct vertices $v,w$ of $G$ .

Proof.

Fix a graph $G$ . Let $\mathcal{H}$ be the hypergraph with $V(\mathcal{H})=V(G)$ and $E(\mathcal{H})$ consists of all nonempty subsets of $V(G)$ with size at most $\Delta$ . By Theorem 23, there exists a proper $(a:b)$ -coloring $\varphi$ of $(G,\mathcal{H})$ for some positive integers $a$ and $b$ with $a\leqslant(1+\varepsilon)\Delta b$ . So for every non-isolated vertex $v$ of $G$ , since $|N_{G}(v)|\leqslant\Delta(G)\leqslant\Delta$ , we have $N_{G}(v)\in E(\mathcal{H})$ , so at least $b$ colors appear exactly once on $N_{G}(v)$ . This proves Statement 1.

For any two distinct vertices $v,w$ of $G$ , since $|\{v,w\}|\leqslant\Delta$ , by the definition of $E(\mathcal{H})$ some edge of $\mathcal{H}$ is precisely $\{v,w\}$ . Since the coloring of $\mathcal{H}$ is conflict-free, by definition at least $b$ colors appear exactly once on $\{v,w\}$ . So $|\varphi(v)\setminus\varphi(w)|+|\varphi(w)\setminus\varphi(v)|\geqslant b$ , and hence $|\varphi(v)\cap\varphi(w)|=(|\varphi(v)|+|\varphi(w)|-(|\varphi(v)\setminus\varphi(w)|+|\varphi(w)\setminus\varphi(v)|))/2\leqslant b/2$ . This proves Statement 3.

Now we prove Statement 2. Suppose to the contrary that there exists a subset $S$ of $V(G)$ with $|S|=3$ such that $\bigcup_{v\in S}\varphi(v)=C$ of size less than $5b/2$ and the subgraph of $G$ induced on $S$ is connected. So some vertex $x$ in $S$ is adjacent to the other two vertices $y$ and $z$ in $S$ . By Statement 3, $|\varphi(y)\cup\varphi(z)|=|\varphi(y)|+|\varphi(z)|-|\varphi(y)\cap\varphi(z)|\geqslant 3b/2$ . Since $\varphi$ is proper, $\varphi(x)\cap(\varphi(y)\cup\varphi(z))=\emptyset$ , so $|\varphi(x)\cup\varphi(y)\cup\varphi(z)|=|\varphi(x)|+|\varphi(y)\cup\varphi(z)|\geqslant 5b/2$ , a contradiction. This proves Statement 2. ∎

Acknowledgments

Thanks to an anonymous referee whose helpful suggestions shortened and simplified Section 3. Thanks also to Louis Esperet for helpful comments on an early draft of this paper.

References

[1] N. Alon, C. McDiarmid, and B. Reed. Acyclic coloring of graphs. Random Structures Algorithms, 2(3):277–288, 1991.
[2] M. Bóna and I. Mező. Real zeros and partitions without singleton blocks. European J. Combin., 51:500–510, 2016.
[3] Y. Caro, M. Petruševski, and R. Škrekovski. Remarks on proper conflict-free colorings of graphs. Discrete Math., 346(2):Paper No. 113221, 14, 2023.
[4] P. Cheilaris. Conflict-free coloring. PhD thesis, City University of New York, 2009.
[5] E.-K. Cho, I. Choi, H. Kwon, and B. Park. Proper conflict-free coloring of sparse graphs. March 2022, arXiv:2203.16390.
[6] D. W. Cranston and C.-H. Liu. Proper conflict-free coloring of graphs with large maximum degree. arXiv:2211.02818v1.
[7] L. Esperet and A. Parreau. Acyclic edge-coloring using entropy compression. European J. Combin., 34(6):1019--1027, 2013.
[8] G. Even, Z. Lotker, D. Ron, and S. Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput., 33(1):94--136, 2003.
[9] I. Fabrici, B. Lužar, S. Rindošová, and R. Soták. Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods. Discrete Appl. Math., 324:80--92, 2023.
[10] G. Fertin, A. Raspaud, and B. Reed. Star coloring of graphs. J. Graph Theory, 47(3):163--182, 2004.
[11] R. Hickingbotham. Odd colourings, conflict-free colourings and strong colouring numbers. March 2022, arXiv:2203.10402.
[12] H. Hind, M. Molloy, and B. Reed. Colouring a graph frugally. Combinatorica, 17(4):469--482, 1997.
[13] A. Kostochka, M. Kumbhat, and T. Ł uczak. Conflict-free colourings of uniform hypergraphs with few edges. Combin. Probab. Comput., 21(4):611--622, 2012.
[14] C.-H. Liu. Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth. Discrete Math., 347(1):113668, 2024.
[15] C.-H. Liu and B. Reed. Asymptotically optimal proper conflict-free colouring. January 2024, arXiv:2401.02155.
[16] C.-H. Liu and G. Yu. Linear colorings of subcubic graphs. European J. Combin., 34(6):1040--1050, 2013, arXiv:1206.5348.
[17] J. Pach and G. Tardos. Conflict-free colourings of graphs and hypergraphs. Combin. Probab. Comput., 18(5):819--834, 2009.
[18] M. Rosenfeld. Another approach to non-repetitive colorings of graphs of bounded degree. Electron. J. Combin., 27(3):Paper No. 3.43, 16, 2020, arXiv:2006.09094.
[19] N. J. A. Sloane and T. O. F. Inc. The on-line encyclopedia of integer sequences, 2022. https://oeis.org/A008299.
[20] I. M. Wanless and D. R. Wood. A general framework for hypergraph coloring. SIAM J. Discrete Math., 36(3):1663--1677, 2022.
[21] R. Yuster. Linear coloring of graphs. Discrete Math., 185(1-3):293--297, 1998.

Appendix: 3 Omitted Proofs

Here we include 3 proofs that we omitted from the body of the text.

4.1 Proof of Lemma 10

We prove Lemma 10 by considering the range of possible values of $d$ .

Lemma 29.

If $3\leqslant{d}\leqslant 9$ and $\beta\geqslant 0.6R$ and $R\geqslant 750$ , then

\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant R^{-1/2}.

Proof.

Since $d\geqslant 3$ and $\beta\geqslant 0.6R$ , $\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)(0.6R)^{i-d+1}$ . Note that $E_{1}(d)=1$ , $E_{i}(2i)=\frac{(2i)!}{i!2^{i}}$ (by the second bound in Lemma 14), and $E_{i}(j)\leqslant E_{i}(k)$ for every $j\leqslant k$ . When $d=3$ , $\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)(0.6R)^{i-d+1}=(0.6R)^{-1}\leqslant R^{-1/2}$ . When $d=4$ ,

\displaystyle\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)(0.6R)^{i-d+1}=(0.6R)^{-2}+E_{2}(4)(0.6R)^{-1}\leqslant(1+\frac{4!}{2!2^{2}})(0.6R)^{-1}=4(0.6R)^{-1}\leqslant R^{-1/2}.

Since $E_{i}(d)$ is the number of partitions of the set $[d]$ into $i$ parts with extra properties, $E_{i}(d)\leqslant i^{d}$ . When $5\leqslant d\leqslant 6$ ,

	$\displaystyle\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)(0.6R)^{i-d+1}$	$\displaystyle\leqslant(0.6R)^{2-d}+E_{2}(d)(0.6R)^{3-d}+(d-5)E_{3}(6)(0.6R)^{4-d}$
		$\displaystyle\leqslant(0.6R)^{2-d}+2^{d}(0.6R)^{3-d}+(d-5)\frac{6!}{3!2^{3}}(0.6R)^{4-d}$
		$\displaystyle\leqslant(1+2^{6})(0.6R)^{-2}+15(d-5)(0.6R)^{4-d}.$

So if $d=5$ , then $\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)(0.6R)^{i-d+1}\leqslant 181/R^{2}\leqslant R^{-1/2}$ , since $R\geqslant 750$ ; if $d=6$ , then $\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)(0.6R)^{i-d+1}\leqslant 181R^{-2}+15(0.6R)^{-2}\leqslant R^{-1/2}$ .

When $7\leqslant d\leqslant 8$ ,

	$\displaystyle\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)(0.6R)^{i-d+1}$	$\displaystyle\leqslant(0.6R)^{2-d}+E_{2}(d)(0.6R)^{3-d}+E_{3}(d)(0.6R)^{4-d}+E_{4}(d)(0.6R)^{5-d}$
		$\displaystyle\leqslant(0.6R)^{-5}+2^{8}(0.6R)^{-4}+3^{8}(0.6R)^{-3}+\frac{8!}{4!2^{4}}(0.6R)^{-2}$
		$\displaystyle\leqslant(1+256+6561)(0.6R)^{-3}+105(0.6R)^{-2}$
		$\displaystyle\leqslant 31565R^{-3}+300R^{-2}=(31565R^{-2.5}+300R^{-1.5})R^{-1/2}$
		$\displaystyle\leqslant(31565\cdot 750^{-2.5}+300\cdot 750^{-1.5})R^{-1/2}\leqslant R^{-1/2}.$

When $d=9$ ,

	$\displaystyle\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)(0.6R)^{i-d+1}$	$\displaystyle=(0.6R)^{-7}+E_{2}(9)(0.6R)^{-6}+E_{3}(9)(0.6R)^{-5}+E_{4}(9)(0.6R)^{-4}$
		$\displaystyle\leqslant 4\cdot 4^{9}(0.6R)^{-4}\leqslant 4^{10}\cdot(5/3)^{4}\cdot 750^{-3.5}\cdot R^{-1/2}\leqslant R^{-1/2}.$

∎

Lemma 30.

If $10\leqslant{d}\leqslant\beta^{2/3}$ and $\beta\geqslant 0.6R\geqslant 14$ , then

\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant R^{-1/2}.

Proof.

Since $10\leqslant d\leqslant\beta^{2/3}$ , we have $d/\beta\leqslant\beta^{-1/3}\leqslant 1/2$ , so

\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant\beta\frac{({d}/\beta)^{\left\lceil{d}/2\right\rceil}}{1-\frac{d}{\beta}}\leqslant 2\beta(\beta^{-\frac{1}{3}})^{\frac{d}{2}}=2\beta^{1-\frac{d}{6}}\leqslant 2\beta^{-2/3}\leqslant\left(\frac{\beta}{0.6}\right)^{-1/2}\leqslant R^{-1/2},

where the first inequality follows from Lemma 13, and the final two inequalities holds because $\beta\geqslant 14$ and because $\beta\geqslant 0.6R$ . ∎

Lemma 31.

If $\beta^{2/3}\leqslant{d}\leqslant\beta^{19/20}$ and $\beta\geqslant\max\{0.6R,600\}$ and $R\geqslant 750$ , then

\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)\beta^{i-d+1}\leqslant R^{-1/2}.

Proof.

Since $\beta\geqslant 600$ , we have $d/\beta\leqslant\beta^{-1/20}\leqslant 600^{-1/20}\leqslant 3/4$ , so by Lemma 13,

\displaystyle\sum_{i=1}^{\left\lfloor{d}/2\right\rfloor}E_{i}(d)\beta^{i-d+1}

\displaystyle\leqslant\beta\frac{({d}/\beta)^{\left\lceil{d}/2\right\rceil}}{1-\frac{d}{\beta}}\leqslant 4\beta(\beta^{-\frac{1}{20}})^{{d}/2}=4\beta^{1-\frac{d}{40}}\leqslant 4\cdot(0.6R)^{1-\frac{d}{40}}.

Since $\beta\geqslant 600$ , we have $d\geqslant\beta^{2/3}\geqslant 71$ , so $4\cdot(0.6R)^{1-d/40}\leqslant 4\cdot(0.6R)^{-31/40}\leqslant 6R^{-31/40}\leqslant 6\cdot 750^{-11/40}\cdot R^{-1/2}\leqslant R^{-1/2}$ , where the penultimate inequality follows from $R\geqslant 750$ . ∎

Corollary 32.

Lemma 10 is true.

Proof.

This follows immediately from Lemmas 29, 30, and 31. ∎

4.2 Proofs of Lemmas 27 and 28

27. Let $p$ be a real number with $0<p<1$ . Let $a,b$ be real numbers. If $f(x):=x(1-p)^{x}$ for every real number $x$ , then $f(x)\geqslant\min\{f(a),f(b)\}$ for every $x$ with $a\leqslant x\leqslant b$ .

Proof.

Let $t:=-1/\log(1-p)$ . Since $\frac{{\rm d}f(x)}{{\rm d}x}=(1-p)^{x}+x(1-p)^{x}\log(1-p)=(1-p)^{x}(1+x\log(1-p))$ , $f(x)$ is increasing when $x\leqslant t$ , and $f(x)$ is decreasing when $x\geqslant t$ . Hence $f(x)\geqslant\min\{f(a),f(b)\}$ for every $x$ with $a\leqslant x\leqslant b$ . ∎

28. $\lim_{x\to\infty}x(1-\frac{\log x}{x})^{x}=1$ .

Proof.

This is a straightforward application of L’Hôspital’s rule. We have

	$\displaystyle~{}~{}~{}~{}\lim_{x\to\infty}\log\left(x\left(1-\frac{\log x}{x}\right)^{x}\right)=\lim_{x\to\infty}\left(\log(x)+x\log\left(1-\frac{\log x}{x}\right)\right)$
	$\displaystyle=\lim_{x\to\infty}\left(\frac{\log(x)}{x}+\log\left(1-\frac{\log x}{x}\right)\right)/x^{-1}$
	$\displaystyle\stackrel{{\scriptstyle\text{H}}}{{=}}\lim_{x\to\infty}\left(\frac{1}{x^{2}}-\frac{\log x}{x^{2}}+\left(1-\frac{\log(x)}{x}\right)^{-1}\left(\frac{-1+\log x}{x^{2}}\right)\right)/(-x^{-2})$
	$\displaystyle=\lim_{x\to\infty}\left(-1+\log x-\frac{x(\log x-1)}{x-\log x}\right)=\lim_{x\to\infty}\frac{\log x-\log^{2}x}{x-\log x}=0.$

\displaystyle~{}~{}~{}~{}\lim_{x\to\infty}x\left(1-\frac{\log x}{x}\right)^{x}=\lim_{x\to\infty}\exp\left(\log\left(x\left(1-\frac{\log x}{x}\right)^{x}\right)\right)=1

∎

	$\displaystyle~{}~{}~{}~{}P(Y_{u}=1\|X_{u}=1\mbox{ and }X_{w}=0{\rm\ for\ every\ }w\in z-\{u\})$
	$\displaystyle=P(\sum_{w\in N(u)\setminus z}X_{w}>(1+\varepsilon)p\Delta)$
	$\displaystyle=P(\sum_{w\in N(u)\setminus z}X_{w}>(1+\varepsilon)\frac{\Delta}{\|N(u)\setminus z\|}{\mathbb{E}}[\sum_{w\in N(u)\setminus z}X_{w}])$
	$\displaystyle\leqslant 2e^{-\frac{((1+\varepsilon)\frac{\Delta}{\|N(u)\setminus z\|}-1)^{2}}{3}{\mathbb{E}}[\sum_{w\in N(u)\setminus z}X_{w}]}$
	$\displaystyle=2e^{-\frac{((1+\varepsilon)\frac{\Delta}{\|N(u)\setminus z\|}-1)^{2}}{3}p\|N(u)\setminus z\|}$
	$\displaystyle=2e^{-((1+\varepsilon)\frac{\Delta}{\sqrt{\|N(u)\setminus z\|}}-\sqrt{\|N(u)\setminus z\|})^{2}\cdot\frac{p}{3}}$
	$\displaystyle\leqslant 2e^{-(\varepsilon\frac{\Delta}{\sqrt{\|N(u)\setminus z\|}})^{2}\cdot\frac{p}{3}}$
	$\displaystyle\leqslant 2e^{-\varepsilon^{2}\Delta p/3}=2e^{-\varepsilon^{2}\log\Delta/3}=2\Delta^{-\varepsilon^{2}/3}\leqslant\varepsilon.$

Proper Conflict-free Coloring of Graphs with Large Maximum Degree

Abstract

1 Introduction

Conjecture 1 ([3]).

Theorem 2.

Proposition 3.

Proof.

Theorem 4.

Theorem 5.

Corollary 6.

Theorem 7.

Corollary 8.

2 Proof of Theorems 2, 4, and 5

Lemma 9.

Proof.

Lemma 10.

Lemma 11.

Lemma 12.

Proof.

Proof of Theorem 2.

Lemma 13.

Proof of Theorem 4.

Proof of Theorem 5.

3 Estimates for 2-Associated Stirling Numbers

Lemma 14.

Proof.

3.1 Proof of Lemma 13

Lemma 13.

Proof.

3.2 Proof of Lemma 11

Proposition 15.

Proof.

Proposition 16.

Proof.

Lemma 17.

Proof.

Lemma 18.

Proof.

Lemma 19.

Proof.

Lemma 20.

Proof.

Lemma 21.

Proof.

Corollary 22.

Proof.

4 Fractional Coloring

Theorem 23.

Lemma 24.

Lemma 25.

Proof of Theorem 23.

Proof of Lemma 24.

Lemma 26 (Chernoff bound).

Lemma 27.

Lemma 28.

Proof.

Proof.

Acknowledgments

References

Appendix: 3 Omitted Proofs

4.1 Proof of Lemma 10

Lemma 29.

Proof.

Lemma 30.

Proof.

Lemma 31.

Proof.

Corollary 32.

Proof.

4.2 Proofs of Lemmas 27 and 28

Proof.

Proof.

Proper Conflict-free Coloring of
Graphs with Large Maximum Degree