DP-Coloring of Graphs from Random Covers

Anton Bernshteyn Department of Mathematics, University of California, Los Angeles, CA, USA. E-mail: [email protected]. Research of this author is partially supported by the NSF grant DMS-2045412 and the NSF CAREER grant DMS-2239187. Daniel Dominik Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL, USA. E-mail: [email protected] Hemanshu Kaul Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL, USA. E-mail: [email protected] Jeffrey A. Mudrock Department of Mathematics and Statistics, University of South Alabama, Mobile, AL, USA. E-mail: [email protected]

Abstract

DP-coloring (also called correspondence coloring) of graphs is a generalization of list coloring that has been widely studied since its introduction by Dvořák and Postle in $2015$ . Intuitively, DP-coloring generalizes list coloring by allowing the colors that are identified as the same to vary from edge to edge. Formally, DP-coloring of a graph $G$ is equivalent to an independent transversal in an auxiliary structure called a DP-cover of $G$ . In this paper, we introduce the notion of random DP-covers and study the behavior of DP-coloring from such random covers. We prove a series of results about the probability that a graph is or is not DP-colorable from a random cover. These results support the following threshold behavior on random $k$ -fold DP-covers as $\rho\to\infty$ where $\rho$ is the maximum density of a graph: graphs are non-DP-colorable with high probability when $k$ is sufficiently smaller than $\rho/\ln\rho$ , and graphs are DP-colorable with high probability when $k$ is sufficiently larger than $\rho/\ln\rho$ . Our results depend on $\rho$ growing fast enough and imply a sharp threshold for dense enough graphs. For sparser graphs, we analyze DP-colorability in terms of degeneracy. We also prove fractional DP-coloring analogs to these results.

Keywords: graph coloring, DP-coloring, fractional DP-coloring, correspondence coloring, random cover, DP-threshold, random lifts.

Mathematics Subject Classification: 05C15, 05C69, 05C80.

1 Introduction

1.1 Basic terminology and notation

All graphs in this paper are finite and simple. Unless otherwise noted we follow terminology from West [Wes20]. We will use $\mathbb{N}$ for the set $\{0,1,2,\ldots\}$ of natural numbers, $2^{A}$ for the power set of a set $A$ , and $[k]$ for $\{1,\,\ldots,\,k\}$ with $[0]=\emptyset$ . Also, for $a$ , $b\in\mathbb{N}$ with $a\leqslant b$ , $[a:b]$ is the set $\{a,\ldots,b\}$ . We use $K_{n}$ for the complete graph on $n$ vertices and $K_{m\times n}$ for the complete $m$ -partite graph with parts of size $n$ . For a graph $G$ and $t\in\mathbb{N}$ , $tG$ is the disjoint union of $t$ copies of $G$ .

Suppose $G=(V(G),E(G))$ is a graph and $v\in V(G)$ is a vertex. The neighborhood of $v$ in $G$ is the set of all vertices adjacent to $v$ , and it is denoted by $N_{G}(v)$ . The degree of $v$ is $|N_{G}(v)|$ , and it is denoted by $\deg(v)$ . For two disjoint sets of vertices $A$ , $B\subseteq V(G)$ , we will use $E_{G}(A,B)$ to denote the set of edges with one endpoint in $A$ and the other in $B$ .

The density of a nonempty graph $G$ , denoted by $d(G)$ , is $|E(G)|/|V(G)|$ . The maximum density of a nonempty graph $G$ , denoted by $\rho(G)$ , is $\max_{G^{\prime}}d(G^{\prime})$ , where the maximum is taken over all nonempty subgraphs $G^{\prime}$ of $G$ .

A graph $G$ is said to be $d$ -degenerate if there exists some ordering of the vertices in $V(G)$ such that each vertex has at most $d$ neighbors among the preceding vertices. The degeneracy of a graph $G$ is the smallest $d\in\mathbb{N}$ such that $G$ is $d$ -degenerate. Note that the degeneracy $d$ of $G$ satisfies the bounds $\rho(G)\leqslant d\leqslant 2\rho(G)$ .

1.2 Graph coloring, list coloring, and DP-coloring

In classical vertex coloring, given a graph $G$ , we assign to each vertex $v\in V(G)$ a color from $\mathbb{N}$ . More precisely, by a coloring of $G$ we mean a function $\varphi\colon V(G)\to\mathbb{N}$ . A $k$ -coloring is a coloring where $\varphi(v)\in[k]$ for all $v\in V(G)$ . We say that a coloring $\varphi\colon V(G)\to\mathbb{N}$ is proper if for every $uv\in E(G)$ , $\varphi(u)\neq\varphi(v)$ . We say that $G$ is $k$ -colorable if it has a proper $k$ -coloring. The chromatic number of $G$ , $\chi(G)$ , is the smallest $k$ such that $G$ is $k$ -colorable.

List coloring is a generalization of vertex coloring that was introduced in the 1970s independently by Vizing [Viz76] and Erdős, Rubin, and Taylor [ERT79]. For a graph $G$ , a list assignment for $G$ is a function $L\colon V(G)\to 2^{\mathbb{N}}$ ; intuitively, $L$ maps each vertex $v\in V(G)$ to a list of allowable colors $L(v)\subseteq\mathbb{N}$ . An $L$ -coloring of $G$ is a coloring $\varphi$ of $G$ such that $\varphi(v)\in L(v)$ for each $v\in V(G)$ . A proper $L$ -coloring of $G$ is an $L$ -coloring of $G$ that is a proper coloring. A $k$ -assignment for $G$ is a list assignment $L$ for $G$ such that $|L(v)|=k$ for all $v\in V(G)$ . We say $G$ is $k$ -choosable if for every $k$ -assignment $L$ for $G$ , $G$ has a proper $L$ -coloring. The list chromatic number of $G$ , denoted by $\chi_{\ell}(G)$ , is the smallest $k$ such that $G$ is $k$ -choosable. Clearly, $\chi(G)\leqslant\chi_{\ell}(G)$ .

The concept of DP-coloring was first put forward in 2015 by Dvořák and Postle [DP18] under the name correspondence coloring. Intuitively, DP-coloring generalizes list coloring by allowing the colors that are identified as the same to vary from edge to edge. Formally, for a graph $G$ , a DP-cover (or simply a cover) of $G$ is an ordered pair $\mathcal{H}=(L,H)$ , where $H$ is a graph and $L\colon V(G)\to 2^{V(H)}$ is a function satisfying the following conditions:

•

$\{L(v):v\in V(G)\}$ is a partition of $V(H)$ into $|V(G)|$ independent sets,
•

for every pair of adjacent vertices $u$ , $v\in V(G)$ , the edges in $E_{H}\left(L(u),L(v)\right)$ form a matching (not necessarily perfect and possibly empty), and
•

$\displaystyle E(H)=\bigcup_{uv\in E(G)}E_{H}(L(u),L(v)).$

Note that some definitions of a DP-cover require each $L(v)$ to be a clique (see, e.g., [BKP17]), but our definition requires each $L(v)$ to be an independent set of vertices in $H$ . We will refer to $L(v)$ as the list of $v$ .

Suppose $\mathcal{H}=(L,H)$ is a cover of a graph $G$ . A transversal of $\mathcal{H}$ is a set of vertices $T\subseteq V(H)$ containing exactly one vertex from each list $L(v)$ . A transversal $T$ is said to be independent if $uv\not\in E(H)$ for all $u$ , $v\in T$ , i.e., if $T$ is an independent set in $H$ . If $\mathcal{H}$ has an independent transversal $T$ , then $T$ is said to be a proper $\mathcal{H}$ -coloring of $G$ , and $G$ is said to be $\mathcal{H}$ -colorable.

A $k$ -fold cover of $G$ is a cover $\mathcal{H}=(L,H)$ such that $|L(v)|=k$ for all $v\in V(G)$ . We will use the term cover size to refer to the value of $k$ in a $k$ -fold cover. The DP-chromatic number of a graph $G$ , $\chi_{DP}(G)$ , is the smallest $k\in\mathbb{N}$ such that $G$ is $\mathcal{H}$ -colorable for every $k$ -fold cover $\mathcal{H}$ of $G$ . Since for any $k$ -assignment $L$ for $G$ , there exists a $k$ -fold cover $\mathcal{H}$ of $G$ such that $G$ is $L$ -colorable if and only if it is $\mathcal{H}$ -colorable [DP18], we know that

\chi(G)\,\leqslant\,\chi_{\ell}(G)\,\leqslant\,\chi_{DP}(G).

Many classical upper bounds on $\chi_{\ell}(G)$ hold for $\chi_{DP}(G)$ as well [DP18, Ber16, Ber19], but there are also some differences [BK18]. For example, the first named author [Ber16] showed that for a graph $G$ with average degree $d$ , $\chi_{DP}(G)=\Omega(d/\ln d)$ . On the other hand, by a celebrated result of Alon [Alo00], such graphs satisfy $\chi_{\ell}(G)=\Omega(\ln d)$ , and this bound is in general best possible.

A full cover of $G$ is a cover $\mathcal{H}=(L,H)$ such that for any $uv\in E(G)$ , the matching between $L(u)$ and $L(v)$ is perfect. It follows that a full cover of a connected graph $G$ must be a $k$ -fold cover for some $k\in\mathbb{N}$ . It is clear that in the definition of the DP-chromatic number, it is enough to only consider full $k$ -fold covers.

1.3 Random DP-covers

The DP-chromatic number, similarly to other variants of the chromatic number, captures the extremal behavior of a graph $G$ with respect to DP-coloring. This extremal perspective looks for the value $k_{0}\in\mathbb{N}$ such that $G$ is $\mathcal{H}$ -colorable for every $k$ -fold cover $\mathcal{H}$ with $k\geqslant k_{0}$ , and $G$ is not $\mathcal{H}$ -colorable for some $k$ -fold cover $\mathcal{H}$ for each $k<k_{0}$ . However, for a given graph $G$ , one can also ask what DP-coloring behavior $G$ exhibits with a high (or low) proportion of DP-covers of a given cover size. This notion of high (or low) proportion of DP-covers can be naturally formalized by considering a probability distribution on the set of all such covers. In this paper, we initiate this study by considering full DP-covers generated uniformly at random, and asking the natural probabilistic questions of the likelihood that the cover does or does not have an independent transversal, and whether a graph shows asymptotically almost sure transition in the behavior of its DP-coloring over these random covers.

Similar probabilistic questions have also been studied for list coloring of graphs. The list assignments of a given graph $G$ are generated uniformly at random from a palette of given colors, and the primary question is whether there is a threshold size of the assignments that shows a transition in the list colorability of the graph (parameterized by either the number of vertices or the chromatic number of the graph). Krivelevich and Nachmias [KN06, KN04] initiated the study of this topic in 2005 and considered it specifically for complete bipartite graphs and powers of cycles. Several follow-up papers were written by Casselgren [Cas11, Cas12, Cas14, Cas18] and Casselgren and Häggkvist [CH16] on various families of graphs including complete graphs, complete multipartite graphs, graphs with bounded degree, etc. The concept of colorings from random list assignments—under the name palette sparsification—has recently found applications in the design of sublinear algorithms in the work of Assadi, Chen, and Khanna [ACK19].

As discussed in the paper by Dvořák and Postle [DP18], a full DP-cover of $G$ is equivalent to the previously studied notion of a lift (or a covering graph) of $G$ (see Godsil and Royle [GR01, §6.8] and discussion with further references in [AL02]). The notion of random $k$ -lifts was introduced by Amit and Linial [AL02]. This work, and the large body of research following it [AL06, ALM02, LR05], studied random $k$ -lifts as a random graph model. Their purpose was the study of the properties of random $k$ -lifts of a fixed graph $G$ as $k\to\infty$ . In this paper, we study the probability that a randomly selected cover has an independent transversal. This focus on finding independent transversals is different from the previous work on random $k$ -lifts.

Let us describe our random model formally. Suppose $G$ is a graph with $V(G)=\{v_{1},\ldots,v_{n}\}$ and $E(G)=\{e_{1},\ldots,e_{m}\}$ . For some $k\in\mathbb{N}$ , let $L(v)=\{(v,i):i\in[k]\}$ for each $v\in V(G)$ . Let $S_{k}$ be the set of all permutations of $[k]$ . For each ${\boldsymbol{\sigma}}=(\sigma_{1},\ldots,\sigma_{m})\in S_{k}^{m}$ , let $\mathcal{H}_{\boldsymbol{\sigma}}=(L,H_{\boldsymbol{\sigma}})$ be the full $k$ -fold cover of $G$ , where $H_{\boldsymbol{\sigma}}$ has the following edges. For each $j\in[m]$ , consider the edge $e_{j}$ . Suppose $e_{j}=v_{q}v_{r}$ with $q<r$ , and define

E_{H_{\boldsymbol{\sigma}}}\left(L(v_{q}),L(v_{r})\right)\,=\,\{(v_{q},i)(v_{r},\sigma_{j}(i))\,:\,i\in[k]\}.

Let $\Omega_{G,k}=\{\mathcal{H}_{\boldsymbol{\sigma}}:{\boldsymbol{\sigma}}\in S_{k}^{m}\}$ . Note that $|\Omega_{G,k}|=(k!)^{m}$ . Let $\mathcal{H}(G,k)$ be an element of $\Omega_{G,k}$ chosen uniformly at random. We will refer to $\mathcal{H}(G,k)$ as a random $k$ -fold cover of $G$ .

Equivalently, a random $k$ -fold cover of a graph $G$ , $\mathcal{H}(G,k)=(L,H)$ , can be constructed in the following way. The mapping $L$ is as described above. For each $v\in V(G)$ , $L(v)$ is an independent set in $H$ . For each edge $e\in E(G)$ , where $e=v_{q}v_{r}$ , the edge set $E_{H}\left(L(v_{q}),L(v_{r})\right)$ takes on one of the $k!$ perfect matchings between $L(v_{q})$ and $L(v_{r})$ uniformly at random.

Here we study the probability that a random cover of a graph has an independent transversal. When $\mathbb{P}(\text{$G$ is $\mathcal{H}(G,k)$-colorable})=p$ , we say that $G$ is $k$ -DP-colorable with probability $p$ .

1.4 Outline of the main results

1.4.1 DP-colorability and density

Table 1 compiles our main results. Given $\varepsilon>0$ and a graph $G$ with a large enough number $n$ of vertices whose maximum density is bounded below by the quantity in the first column, the third column gives the probability that $G$ is $k$ -DP-colorable provided $k$ satisfies the inequality in the second column.

Density lower bound	Cover size	Probability of $k$ -DP-colorability	Reference
$\exp(e/\varepsilon)$	$\displaystyle k\leqslant\frac{\rho(G)}{\ln\rho(G)}$	$\leqslant\varepsilon$	Prop. 1.1

$n^{1-s}$ for $s\in[0,1/3)$	$\displaystyle k\geqslant(1+\varepsilon)\left(1+\frac{s}{1-2s}\right)\frac{\rho(G)}{\ln\rho(G)}$	$\geqslant 1-\varepsilon$	Thm. 1.2

$\displaystyle\ln^{2/\varepsilon}n$	$\displaystyle k\geqslant(1+\varepsilon)\frac{2\rho(G)}{\ln\rho(G)}$	$\geqslant 1-\varepsilon$	Thm. 1.3

No lower bound	$k>2\rho(G)$	$1$	[DP18]

Table 1: Probability of

k

-DP-colorability depending on the maximum density of

G

Our work shows that, for sufficiently dense graphs $G$ , the probability $G$ is $k$ -DP-colorable exhibits a transition when $k$ is close to $\rho(G)/\ln\rho(G)$ . To begin with, we note that if $k\leqslant\rho(G)/\ln\rho(G)$ and $\rho(G)$ is not too small, the probability that $G$ is $k$ -DP-colorable is close to $0$ :

Proposition 1.1.

Let $\varepsilon>0$ and let $G$ be a nonempty graph with $\rho(G)\geqslant\exp(e/\varepsilon)$ . If $1\leqslant k\leqslant\rho(G)/\ln\rho(G)$ , then $G$ is $k$ -DP-colorable with probability at most $\varepsilon$ .

Proposition 1.1 is proved via a simple application of the First Moment Method. It is a straightforward modification of [Ber16, Theorem 1.6], but, for completeness, we include a self-contained proof in §2.1. We remark that the bound $\rho(G)\geqslant\exp(e/\varepsilon)$ in Proposition 1.1 is rather crude and can be sharpened by more careful calculations. However, this bound is sufficient for our purposes. In particular, note that if $(G_{\lambda})_{\lambda\in\mathbb{N}}$ is a sequence of graphs such that $\rho(G_{\lambda})\to\infty$ as $\lambda\to\infty$ , then the bound $\rho(G_{\lambda})\geqslant\exp(e/\varepsilon)$ holds for any fixed $\varepsilon>0$ and all large enough $\lambda$ .

Next we show that if $G$ is fairly dense (of density greater than $n^{2/3}$ ) and $k$ exceeds $\rho(G)/\ln\rho(G)$ by an appropriate constant factor, then $G$ is $k$ -DP-colorable with probability close to $1$ :

Theorem 1.2.

For all $\varepsilon>0$ and $s\in[0,1/3)$ , there is $n_{0}\in\mathbb{N}$ such that the following holds. Suppose $G$ is a graph with $n\geqslant n_{0}$ vertices such that $\rho(G)\geqslant n^{1-s}$ , and

k\,\geqslant\,\left(1+\varepsilon\right)\left(1+\frac{s}{1-2s}\right)\frac{\rho(G)}{\ln\rho(G)}.

(1.1)

Then $G$ is $k$ -DP-colorable with probability at least $1-\varepsilon$ .

Theorem 1.2 is proved in §3 by applying the Second Moment Method to the number of independent transversals in a random cover of $G$ . Notice that when the density of $G$ is at least $n^{1-o(1)}$ , the factor in front of $\rho(G)/\ln\rho(G)$ in (1.1) is very close to $1$ (which matches the bound in Proposition 1.1). On the other hand, when $\rho(G)\geqslant n^{2/3+o(1)}$ , the factor in front of $\rho(G)/\ln\rho(G)$ approaches $2$ . Our next result shows that with the factor fixed at $2$ , the conclusion of Theorem 1.2 remains true all the way down to $\rho(G)\geqslant\ln^{\omega(1)}n$ . More precisely, we establish the following lower bound on the probability that $G$ is $k$ -DP-colorable in terms of the relationship between $k$ and the degeneracy of $G$ :

Theorem 1.3.

For all $\varepsilon\in(0,1/2)$ , there is $n_{0}\in\mathbb{N}$ such that the following holds. Let $G$ be a graph with $n\geqslant n_{0}$ vertices and degeneracy $d$ such that $d\geqslant\ln^{2/\varepsilon}n$ and let $k\geqslant(1+\varepsilon)d/\ln d$ . Then $G$ is $k$ -DP-colorable with probability at least $1-\varepsilon$ .

Theorem 1.3 is proved in §4 by analyzing a greedy algorithm for constructing an independent transversal in a random $k$ -fold cover. The key tool we employ is a form of the Chernoff–Hoeffding bound for negatively correlated Bernoulli random variables due to Panconesi and Srinivasan [PS97]. Since every graph $G$ is $2\rho(G)$ -degenerate, the lower bound on $k$ in Theorem 1.3 is implied by $k\geqslant(1+\varepsilon)2\rho(G)/\ln\rho(G)$ , which is roughly a factor of $2$ away from the bound in Proposition 1.1. We conjecture that the factor of $2$ is not needed:

Conjecture 1.4.

For all $\varepsilon>0$ , there exist $C>0$ and $n_{0}\in\mathbb{N}$ such that the following holds. Suppose $G$ is a graph with $n\geqslant n_{0}$ vertices such that $\rho(G)\geqslant\ln^{C}n$ , and

k\,\geqslant\,\left(1+\varepsilon\right)\frac{\rho(G)}{\ln\rho(G)}.

Then $G$ is $k$ -DP-colorable with probability at least $1-\varepsilon$ .

The polylogarithmic lower bound on $\rho(G)$ in Theorem 1.3 and Conjecture 1.4 is unavoidable, as the following proposition, proved in §2.2, demonstrates:

Proposition 1.5.

For any $\varepsilon>0$ and $n_{0}\in\mathbb{N}$ , there is a graph $G$ with $n\geqslant n_{0}$ vertices such that $\rho(G)\geqslant\left(\ln n/\ln\ln n\right)^{1/3}$ but, for every $k\leqslant 2\rho(G)$ , $G$ is $k$ -DP-colorable with probability less than $\varepsilon$ .

Therefore, we cannot hope to get results similar to Theorems 1.2 and 1.3 for very sparse graphs. Note that the bound $k\leqslant 2\rho(G)$ in Proposition 1.5 is optimal: if $k>2\rho(G)$ , then $k$ must be strictly greater than the degeneracy of $G$ , and thus $G$ is $k$ -DP-colorable (with probability $1$ ) [DP18].

It follows from [Ber19, Theorem 1.3] that for each $\varepsilon>0$ , there is $C_{\varepsilon}>0$ such that every triangle-free regular graph $G$ with $\rho(G)\geqslant C_{\varepsilon}$ satisfies $\chi_{DP}(G)\leqslant(1+\varepsilon)2\rho(G)/\ln\rho(G)$ , and hence it is $k$ -DP-colorable (with probability $1$ ) for all $k\geqslant(1+\varepsilon)2\rho(G)/\ln\rho(G)$ . Together with Proposition 1.5, this shows that for very sparse graphs, it is impossible to determine up to a constant factor where the probability of DP-colorability transitions from approximately $0$ to approximately $1$ based on the maximum density alone.

1.4.2 Threshold functions

We can use the above results to answer questions about the asymptotic behavior of sequences of graphs. Consider a sequence of graphs $\mathcal{G}=(G_{\lambda})_{\lambda\in\mathbb{N}}$ and a sequence of integers $\kappa=(k_{\lambda})_{\lambda\in\mathbb{N}}$ . We say that $\mathcal{G}$ is $\kappa$ -DP-colorable with high probability, or w.h.p., if

\lim_{\lambda\to\infty}\mathbb{P}(\text{$G_{\lambda}$ is $\mathcal{H}(G_{\lambda},k_{\lambda})$-colorable})\,=\,1.

Similarly, we say that $\mathcal{G}$ is non- $\kappa$ -DP-colorable w.h.p. if

\lim_{\lambda\to\infty}\mathbb{P}(\text{$G_{\lambda}$ is $\mathcal{H}(G_{\lambda},k_{\lambda})$-colorable})\,=\,0.

A function $t_{\mathcal{G}}\colon\mathbb{N}\to\mathbb{R}$ is called a DP-threshold function for $\mathcal{G}$ if it satisfies the following two conditions: if $k_{\lambda}=o(t_{\mathcal{G}}(\lambda))$ , then $\mathcal{G}$ is non- $\kappa$ -DP-colorable w.h.p., while if $t_{\mathcal{G}}(\lambda)=o(k_{\lambda})$ , then $\mathcal{G}$ is $\kappa$ -DP-colorable w.h.p. (Here the $o(\cdot)$ notation is used with respect to $\lambda\to\infty$ .) Similarly, a function $t_{\mathcal{G}}$ is said to be a sharp DP-threshold function for $\mathcal{G}$ if it satisfies the following two conditions: for any $\varepsilon>0$ , $\mathcal{G}$ is non- $\kappa$ -DP-colorable w.h.p. when $k_{\lambda}\leqslant(1-\varepsilon)t_{\mathcal{G}}(\lambda)$ for all large enough $\lambda$ , and it is $\kappa$ -DP-colorable w.h.p. when $k_{\lambda}\geqslant(1+\varepsilon)t_{\mathcal{G}}(\lambda)$ for all large enough $\lambda$ .

We can use Theorem 1.2 to show that any sequence of graphs $\mathcal{G}=(G_{\lambda})_{\lambda\in\mathbb{N}}$ whose densities are bounded below by $|V(G_{\lambda})|^{1-o(1)}$ has $t_{\mathcal{G}}(\lambda)=\rho(G_{\lambda})/\ln(\rho(G_{\lambda}))$ as a sharp DP-threshold function, while for graph sequences with $\rho(G_{\lambda})\geqslant\ln^{\omega(1)}n$ , the same $t_{\mathcal{G}}$ is a DP-threshold function (but we do not know whether it is sharp). This result is proved in §5 as Theorem 5.1. The following two corollaries are special cases:

Corollary 1.6.

For $\mathcal{G}=(K_{n})_{n\in\mathbb{N}}$ , the sequence of complete graphs, $t_{\mathcal{G}}(n)=n/(2\ln n)$ is a sharp DP-threshold function.

Corollary 1.7.

For $\mathcal{G}=(K_{m\times n})_{n\in\mathbb{N}}$ with constant $m\geqslant 2$ , the sequence of complete $m$ -partite graphs with $n$ vertices in each part, $t_{\mathcal{G}}(n)=(m-1)n/(2\ln n)$ is a sharp DP-threshold function.

The existence of a (not necessarily sharp) DP-threshold function of order $\Theta(n/\ln n)$ for the sequence of complete graphs was recently proved by Dvořák and Yepremyan using different methods [DY23, Theorem 1.3].

From Theorems 1.2 and 1.3, we know that sequences of graphs with at least polylogarithmic densities have DP-threshold functions, while very dense graph sequences have sharp DP-threshold functions. Proposition 1.5 shows that there is more going on, and leads to the following question.

Question 1.8.

Under what conditions on $\mathcal{G}=(G_{\lambda})_{\lambda\in\mathbb{N}}$ will $t_{\mathcal{G}}(\lambda)=\rho(G_{\lambda})/\ln\rho(G_{\lambda})$ be a DP-threshold function or a sharp DP-threshold function for $\mathcal{G}$ ?

1.4.3 Fractional DP-coloring

We now extend our analysis of DP-colorability with respect to random covers to fractional DP-coloring, which was introduced by Kostochka, Zhu, and the first named author in [BKZ20]. For $a$ , $b\in\mathbb{N}$ , a b-fold transversal of some $a$ -fold cover $\mathcal{H}=(L,H)$ of $G$ is a set $T\subseteq V(H)$ such that for every $v\in V(G)$ , $\left|L(v)\cap T\right|=b$ . An independent $b$ -fold transversal is a $b$ -fold transversal that is an independent set in $H$ (here we rely on our convention that the sets $L(v)$ for $v\in V(G)$ are independent). If $\mathcal{H}$ has an independent $b$ -fold transversal, we say that $G$ is $(\mathcal{H},b)$ -colorable. For $a$ , $b\in\mathbb{N}$ with $a\geqslant b$ , we say that a graph $G$ is $(a,b)$ -DP-colorable if for every $a$ -fold cover $\mathcal{H}$ of $G$ , $G$ is $(\mathcal{H},b)$ -colorable. The fractional DP-chromatic number is

\chi_{{}_{DP}}^{*}(G)\,=\,\inf\{a/b\,:\,G\text{ is $(a,b)$-DP-colorable}\}.

When $\mathbb{P}(\text{$G$ is $(\mathcal{H}(G,a),b)$-colorable})=p$ , we say that $G$ is $(a,b)$ -DP-colorable with probability $p$ . (Here $\mathcal{H}(G,a)$ is the random $a$ -fold cover of $G$ defined in §1.3.) Given $k\geqslant 1$ , we define

p^{\ast}(G,k)\,=\,\sup\{p\,:\,\exists a,\,b\in\mathbb{N}\text{ s.t.~{}$a/b\leqslant k$ and $G$ is $(a,b)$-DP-colorable with probability $p$}\}.

We obtain two results for fractional-DP-coloring. The first is Proposition 1.9, which is a general result that implies Proposition 1.1.

Proposition 1.9.

Let $\varepsilon>0$ and let $G$ be a nonempty graph with $\rho(G)\geqslant\exp(e/\varepsilon)$ . If $1\leqslant k\leqslant\rho(G)/\ln\rho(G)$ , then $p^{\ast}(G,k)\leqslant\varepsilon$ .

Proposition 1.9 is a slight strengthening of [BKZ20, Theorem 1.9] due to Kostochka, Zhu, and the first named author and is proved using the First Moment Method. We present the proof in §2.1.

Our second result is a version of Theorem 1.3 for fractional DP-coloring:

Theorem 1.10.

For all $\varepsilon>0$ , there is $d_{0}\in\mathbb{N}$ such that the following holds. Let $G$ be a graph with degeneracy $d\geqslant d_{0}$ and let $k\geqslant(1+\varepsilon)d/\ln d$ . Then $p^{\ast}(G,k)\geqslant 1-\varepsilon$ .

Theorem 1.10 extends the result of Theorem 1.3 to any graph whose degeneracy is high enough as a function of $\varepsilon$ (regardless of how small it is when compared to the number of vertices in the graph), at the cost of replacing DP-coloring with fractional DP-coloring. In particular, Proposition 1.5 fails in the fractional setting. The proof of Theorem 1.10 is analogous to that of Theorem 1.3 and will be presented in §4.3.

2 DP-colorability with probability close to $0$

2.1 A First Moment argument

In this subsection we prove Proposition 1.9, which clearly implies Proposition 1.1.

Observation 2.1.

If $G^{\prime}$ is a subgraph of a graph $G$ , then $p^{\ast}(G,k)\leqslant p^{\ast}(G^{\prime},k)$ for all $k\geqslant 1$ .

Proof.

Given a cover $\mathcal{H}=(L,H)$ of $G$ , the subcover of $\mathcal{H}$ corresponding to $G^{\prime}$ is $\mathcal{H}^{\prime}=(L^{\prime},H^{\prime})$ where $L^{\prime}$ is the restriction of $L$ to $V(G^{\prime})$ and $H^{\prime}$ is the subgraph of $H$ with vertex set $V(H^{\prime})=\bigcup_{u\in V(G^{\prime})}L(u)$ that retains those and only those edges of $H$ that belong to the matchings corresponding to the edges of $G^{\prime}$ . Clearly, $\mathcal{H}^{\prime}$ is a cover of $G^{\prime}$ .

Now suppose that $a$ , $b\in\mathbb{N}$ satisfy $a/b\leqslant k$ . Note that the subcover $\mathcal{H^{\prime}}$ of $\mathcal{H}(G,a)$ corresponding to $G^{\prime}$ is a random cover of $G^{\prime}$ with the same distribution as $\mathcal{H}(G^{\prime},a)$ . If $\mathcal{H}^{\prime}$ has no independent $b$ -fold transversal, $\mathcal{H}$ also has no independent $b$ -fold transversal. Thus,

		$\displaystyle\mathbb{P}\left(\mathcal{H}(G,a)\text{ has an independent $b$-fold transversal}\right)$
	$\displaystyle\leqslant\,$	$\displaystyle\mathbb{P}\left(\mathcal{H}(G^{\prime},a)\text{ has an independent $b$-fold transversal}\right)\,\leqslant\,p^{\ast}(G^{\prime},k).$

Since this holds for all $a/b\leqslant k$ , we conclude that $p^{\ast}(G,k)\leqslant p^{\ast}(G^{\prime},k)$ , as desired. ∎

We now prove Proposition 1.9, which we restate here for the reader’s convenience.

Proposition 1.9.

Let $\varepsilon>0$ and let $G$ be a nonempty graph with $\rho(G)\geqslant\exp(e/\varepsilon)$ . If $1\leqslant k\leqslant\rho(G)/\ln\rho(G)$ , then $p^{\ast}(G,k)\leqslant\varepsilon$ .

Proof.

Suppose $a$ , $b\in\mathbb{N}$ satisfy $1\leqslant a/b\leqslant k$ . We need to argue that $G$ is $(a,b)$ -DP-colorable with probability at most $\varepsilon$ . By Observation 2.1, we may assume that $\rho(G)$ equals the density of $G$ . For ease of notation, let $n=|V(G)|$ , $m=|E(G)|$ , and $\rho=\rho(G)=m/n$ .

We enumerate all $b$ -fold transversals of $\mathcal{H}(G,a)=(L,H)$ as $\{I_{i}\}_{i=1}^{s}$ where $s={a\choose b}^{n}$ . Let $E_{i}$ be the event that $I_{i}$ is an independent $b$ -fold transversal and let $X_{i}$ be the indicator random variable for the event $E_{i}$ . Define $X=\sum_{i=1}^{s}X_{i}$ . Note that $X$ is the random variable that counts the number of independent $b$ -fold transversals of $\mathcal{H}(G,a)$ . We have

\mathbb{E}(X_{i})\,=\,\left(\frac{{{a-b}\choose b}}{{a\choose b}}\right)^{m},\hskip 18.06749pt\text{which implies}\hskip 18.06749pt\mathbb{E}(X)\,=\,\sum_{i=1}^{s}\mathbb{E}\left(X_{i}\right)\,=\,{a\choose b}^{n}\left(\frac{{{a-b}\choose b}}{{a\choose b}}\right)^{m}.

Notice that, since $m>0$ , $a<2b$ implies $\mathbb{E}(X)=0$ . We will now establish an upper bound on $\mathbb{E}(X)$ when $a\geqslant 2b$ . We see

\mathbb{E}(X)\,=\,\exp\left(n\ln{a\choose b}+m\ln\left(\frac{{{a-b}\choose b}}{{a\choose b}}\right)\right)\,=\,\exp\left(n\left(\ln{a\choose b}+\rho\ln\left(\frac{{{a-b}\choose b}}{{a\choose b}}\right)\right)\right).

Now we write

	$\displaystyle\ln{a\choose b}+\rho\ln\left(\frac{{{a-b}\choose b}}{{a\choose b}}\right)\,$	$\displaystyle=\,\ln\left(\prod_{j=0}^{b-1}\frac{a-j}{b-j}\right)+\rho\ln\left(\prod_{j=0}^{b-1}\frac{a-b-j}{a-j}\right)$
		$\displaystyle\leqslant\,\sum_{j=0}^{b-1}\left(\ln\left(\frac{a}{b-j}\right)+\rho\ln\left(1-\frac{b}{a}\right)\right)$
		$\displaystyle=\,\sum_{j=0}^{b-1}\left(\ln\left(\frac{a}{b}\right)+\ln b-\ln(b-j)+\rho\ln\left(1-\frac{b}{a}\right)\right)$
	$\displaystyle[\text{since $a/b\leqslant k$}]\qquad\qquad$	$\displaystyle\leqslant\,\sum_{j=0}^{b-1}\left(\ln k+\rho\ln\left(1-\frac{1}{k}\right)\right)+b\ln b-\ln b!$
	$\displaystyle[\text{since $\ln b!\geqslant b\ln b-b$}]\qquad\qquad$	$\displaystyle\leqslant\,\sum_{j=0}^{b-1}\left(1+\ln k+\rho\ln\left(1-\frac{1}{k}\right)\right)$
	$\displaystyle[\text{since $\ln(1-x)\leqslant-x$ for $x<1$}]\qquad\qquad$	$\displaystyle\leqslant\,\sum_{j=0}^{b-1}\left(1+\ln k-\frac{\rho}{k}\right)$
	$\displaystyle[\text{since $k\leqslant\rho/\ln\rho$}]\qquad\qquad$	$\displaystyle\leqslant\,\sum_{j=0}^{b-1}\left(1+\ln\left(\frac{\rho}{\ln\rho}\right)-\ln\rho\right)$
		$\displaystyle=\,b(1-\ln\ln\rho).$

It follows that

\mathbb{E}(X)\,\leqslant\,\exp\left(nb(1-\ln\ln\rho)\right)\,\leqslant\,\exp\left(1-\ln\ln\rho\right)\,\leqslant\,\varepsilon,

(2.1)

since $\rho\geqslant\exp(e/\varepsilon)$ by assumption. Therefore, by Markov’s Inequality we have

\mathbb{P}(X=0)\,=\,1-\mathbb{P}(X\geqslant 1)\,\geqslant\,1-\mathbb{E}(X)\,\geqslant\ 1-\varepsilon.\qed

2.2 Sparse graphs with low probability of $k$ -DP-colorability

In this subsection we construct graphs $G$ with polylogarithmic density that have low probability of $k$ -DP-colorability for any $k\leqslant 2\rho(G)$ .

Proposition 1.5.

Proof.

Fix $\varepsilon>0$ and let $q\in\mathbb{N}$ be sufficiently large as a function of $\varepsilon$ . Consider the graph $G=tK_{q}$ , the disjoint union of $t$ copies of $K_{q}$ , where

t\,=\,\ln(1/\varepsilon)\,(q-1)!^{{q}\choose 2}.

Let us denote the copies of $K_{q}$ in $G$ by $K^{1}$ , …, $K^{t}$ . Note that $\rho=\rho(G)=(q-1)/2$ . Suppose that $k\leqslant 2\rho=q-1$ . For each $r\in[t]$ , let $A_{r}$ be the event that in the cover $\mathcal{H}(G,k)$ , the vertices $(u,i)$ and $(v,i)$ are adjacent for all $uv\in E(K^{r})$ and $i\in[k]$ . Note that if $A_{r}$ happens for some $r\in[t]$ , then $G$ is not $\mathcal{H}(G,k)$ -colorable (because it is impossible to color $K^{r}$ ). The events $A_{1}$ , …, $A_{t}$ are mutually independent, so

\displaystyle\mathbb{P}(\text{$G$ is $\mathcal{H}(G,k)$-colorable})\,\leqslant\,\mathbb{P}\left(\bigcap_{r\in[t]}\overline{A_{r}}\right)\,

\displaystyle=\,\left(1-(k!)^{-{q\choose 2}}\right)^{t}\,<\,\exp\left(-t(k!)^{-{q\choose 2}}\right)\,\leqslant\,\varepsilon.

It remains to observe, using the bound $(q-1)!\leqslant q^{q}$ and assuming $q>\ln(1/\varepsilon)$ , that

|V(G)|\,=\,tq\,=\,\ln(1/\varepsilon)\,(q-1)!^{{q\choose 2}}\,q\,\leqslant\,(q-1)!^{{q\choose 2}}\,q^{2}\,\leqslant\,q^{q^{3}/2},

and we have, for large enough $q$ ,

\left(\frac{\ln q^{q^{3}/2}}{\ln\ln q^{q^{3}/2}}\right)^{1/3}\,=\,\left(\frac{q^{3}\ln q}{2(3\ln q-\ln 2+\ln\ln q)}\right)^{1/3}\,\leqslant\,\left(\frac{q^{3}}{6}\right)^{1/3}\,=\,\frac{q}{6^{1/3}}\,<\,\frac{q-1}{2}\,=\,\rho.\qed

3 DP-colorability with probability close to $1$ for dense graphs

Now we prove Theorem 1.2, which we state here again for convenience:

Theorem 1.2.

k\,\geqslant\,\left(1+\varepsilon\right)\left(1+\frac{s}{1-2s}\right)\frac{\rho(G)}{\ln\rho(G)}.

Then $G$ is $k$ -DP-colorable with probability at least $1-\varepsilon$ .

Proof.

Without loss of generality, we assume that $\varepsilon<1$ . Consider an arbitrary graph $G$ with $n$ vertices, $m$ edges, and maximum density $\rho=\rho(G)$ such that $\rho\geqslant n^{1-s}$ , and let $k$ satisfy the bound in the statement of the theorem. Throughout the proof, we shall treat $\varepsilon$ and $s$ as fixed, while $n$ will be assumed to be sufficiently large as a function of $\varepsilon$ and $s$ . In particular, when we employ asymptotic notation, such as $O(\cdot)$ , $o(\cdot)$ , and $\Omega(\cdot)$ , it will always be with respect to $n\to\infty$ , while the implied constants will be allowed to depend on $\varepsilon$ and $s$ . As usual, the asymptotic notation $\tilde{O}(\cdot)$ and $\tilde{\Omega}(\cdot)$ hides polylogarithmic factors.

We enumerate all transversals of $\mathcal{H}(G,k)=(L,H)$ as $\{I_{i}\}_{i=1}^{k^{n}}$ . Throughout the proof, the variables $i$ and $j$ will range over $[k^{n}]$ . Let $E_{i}$ be the event that $I_{i}$ is independent and let $X_{i}$ be the indicator random variable for the event $E_{i}$ . Define $X=\sum_{i=1}^{k^{n}}X_{i}$ , so $X$ is the random variable that counts the $\mathcal{H}(G,k)$ -colorings of $G$ . For convenience, we set $p=(k-1)/k$ . Clearly,

\mathbb{E}(X)\,=\,k^{n}\left(\frac{k-1}{k}\right)^{m}\,=\,k^{n}p^{m}.

Notice that

\displaystyle\mathrm{Var}(X)\,=\,\sum_{(i,j)}\mathrm{Cov}(X_{i},X_{j})\,=\,\sum_{(i,j)}\left(\mathbb{E}(X_{i}X_{j})-\mathbb{E}(X_{i})\mathbb{E}(X_{j})\right)\,=\,\sum_{(i,j)}\mathbb{E}(X_{i}X_{j})\,-\,\mathbb{E}(X)^{2}.

(3.1)

Now, for each $(i,j)\in[k^{n}]^{2}$ , we need to compute $\mathbb{E}(X_{i}X_{j})$ . To this end, for every edge $uv\in E(G)$ , let $I_{i}\cap L(u)=\{(u,i_{u})\}$ , $I_{i}\cap L(v)=\{(v,i_{v})\}$ , $I_{j}\cap L(u)=\{(u,j_{u})\}$ , and $I_{j}\cap L(v)=\{(v,j_{v})\}$ . Define $A_{uv}$ as the event $(u,i_{u})(v,i_{v})\not\in E(H)$ and $B_{uv}$ as the event $(u,j_{u})(v,j_{v})\not\in E(H)$ , and let $E_{uv}=A_{uv}\cap B_{uv}$ . Now we consider three cases.

(a)

$i_{u}=j_{u}$ and $i_{v}=j_{v}$ .

In this case, we have $\mathbb{P}(E_{uv})=(k-1)/k=p$ .

(b)

$i_{u}\neq j_{u}$ and $i_{v}=j_{v}$ , or $i_{u}=j_{u}$ and $i_{v}\neq j_{v}$ .

In this case, regardless of whether $i_{v}=j_{v}$ or $i_{u}=j_{u}$ , we have

\mathbb{P}(E_{uv})\,=\,\frac{k-2}{k}\,=\,p^{2}-\frac{1}{k^{2}}\,\leqslant\,p^{2}.

To compute $\mathbb{P}(E_{uv})$ in this case, we let $C_{uv}$ be the event $(u,i_{u})(v,j_{v})\in E(H)$ . Note that $C_{uv}\subseteq B_{uv}$ since $E_{H}(L(u),L(v))$ is a matching. Therefore,

	$\displaystyle\mathbb{P}(E_{uv})\,$	$\displaystyle=\,\mathbb{P}(A_{uv})\cdot\mathbb{P}(B_{uv}\|A_{uv})$
		$\displaystyle=\,\mathbb{P}(A_{uv})\cdot\left(\mathbb{P}\left(C_{uv}\|A_{uv}\right)+\mathbb{P}\left(B_{uv}\cap\overline{C_{uv}}\|A_{uv}\right)\right)$
		$\displaystyle=\,\mathbb{P}(A_{uv})\cdot\left(\mathbb{P}\left(C_{uv}\|A_{uv}\right)+\mathbb{P}\left(\overline{C_{uv}}\|A_{uv}\right)\cdot\mathbb{P}\left(B_{uv}\|A_{uv}\cap\overline{C_{uv}}\right)\right)$
		$\displaystyle=\,\left(\frac{k-1}{k}\right)\left(\frac{1}{k-1}+\left(\frac{k-2}{k-1}\right)^{2}\right)\,=\,p^{2}+\frac{1}{k^{2}(k-1)}.$

Let the number of edges in $E(G)$ satisfying the conditions from cases (a), (b), and (c) be $\alpha_{i,j}$ , $\beta_{i,j}$ , and $\gamma_{i,j}$ , respectively. Since the matchings in $H$ corresponding to different edges of $G$ are chosen independently, we conclude that

\mathbb{E}(X_{i}X_{j})\,\leqslant\,p^{\alpha_{i,j}}p^{2\beta_{i,j}}\left(p^{2}+\frac{1}{k^{2}(k-1)}\right)^{\gamma_{i,j}}.

Using (3.1) and the fact that $\alpha_{i,j}+\beta_{i,j}+\gamma_{i,j}=m$ , we now obtain

	$\displaystyle\frac{\mathrm{Var}(X)}{\mathbb{E}(X)^{2}}\,$	$\displaystyle=\,\frac{\sum_{(i,j)}\mathbb{E}(X_{i}X_{j})}{k^{2n}p^{2m}}-1$
		$\displaystyle\leqslant\,k^{-2n}p^{-2m}\sum_{(i,j)}p^{\alpha_{i,j}}p^{2\beta_{i,j}}\left(p^{2}+\frac{1}{k^{2}(k-1)}\right)^{\gamma_{i,j}}-1$
		$\displaystyle=\,k^{-2n}\sum_{(i,j)}p^{-\alpha_{i,j}}\left(\frac{p^{2}+\frac{1}{k^{2}(k-1)}}{p^{2}}\right)^{\gamma_{i,j}}-1$
		$\displaystyle=\,k^{-2n}\sum_{(i,j)}\left(1+\frac{1}{k-1}\right)^{\alpha_{i,j}}\left(1+\frac{1}{(k-1)^{3}}\right)^{\gamma_{i,j}}-1.$

Note that, for given $i$ and $j$ , $\alpha_{i,j}$ is exactly the number of edges of $G$ with both endpoints in the set $\{v\in V(G):L(v)\cap I_{i}=L(v)\cap I_{j}\}$ . Since the density of every subgraph of $G$ is at most $\rho$ , we conclude that if $|I_{i}\cap I_{j}|=\nu$ , then $\alpha_{i,j}\leqslant\mu(\nu)$ , where

\mu(\nu)\,=\,\min\left\{{\nu\choose 2},\,\rho\nu\right\}\,\leqslant\,\min\{\nu^{2},\,\rho\nu\}.

Also, $\gamma_{i,j}\leqslant m\leqslant\rho n$ . As there are ${n\choose\nu}k^{n}(k-1)^{n-\nu}$ pairs $(i,j)$ with $|I_{i}\cap I_{j}|=\nu$ , we have

	$\displaystyle\frac{\mathrm{Var}(X)}{\mathbb{E}(X)^{2}}\,$	$\displaystyle\leqslant\,k^{-2n}\sum_{\nu=0}^{n}\left[{n\choose\nu}k^{n}(k-1)^{n-\nu}\left(1+\frac{1}{k-1}\right)^{\mu(\nu)}\left(1+\frac{1}{(k-1)^{3}}\right)^{\rho n}\right]-1$
		$\displaystyle=\,\left(1+\frac{1}{(k-1)^{3}}\right)^{\rho n}\sum_{\nu=0}^{n}\left[{n\choose\nu}{k^{-\nu}}\left(1-\frac{1}{k}\right)^{n-\nu}\left(1+\frac{1}{k-1}\right)^{\mu(\nu)}\right]\,-\,1.$

For ease of notation, we define

g(\nu)\,=\,{n\choose\nu}{k^{-\nu}}\left(1-\frac{1}{k}\right)^{n-\nu}\left(1+\frac{1}{k-1}\right)^{\mu(\nu)}.

Note that $g(\nu)=0$ for $\nu\notin[0:n]$ . Observe that, since $\rho\geqslant n^{2/3}$ and $k=\tilde{\Omega}(\rho)$ ,

\left(1+\frac{1}{(k-1)^{3}}\right)^{\rho n}\,\leqslant\,1+\frac{\rho n}{(k-1)^{3}}\,=\,1+\tilde{O}\left(\frac{n}{\rho^{2}}\right)\,=\,1+\tilde{O}(n^{-1/3})\,=\,1+o(1).

(Recall that the asymptotic notation here is with respect to $n\to\infty$ .) Therefore,

\frac{\mathrm{Var}(X)}{\mathbb{E}(X)^{2}}\,\leqslant\,(1+o(1))\sum_{\nu=0}^{n}g(\nu)\,-\,1.

(3.2)

The key to our analysis is to divide the summation according to the magnitude of $\nu$ . Define

\delta\,=\,\frac{1-3s}{4},

and note that $\delta>0$ since $s<1/3$ .

Claim 3.1.

The following asymptotic bounds hold as $n\to\infty$ :

\sum_{\nu\,\leqslant\,n^{s+\delta}}g(\nu)\,\leqslant\,1+o(1),\qquad\sum_{n^{s+\delta}\,<\,\nu\,\leqslant\,k-1}g(\nu)\,=\,o(1),\qquad\text{and}\qquad\sum_{\nu=k}^{n}g(\nu)\,=\,o(1).

Claim 3.1 and inequality (3.2) imply that $\mathrm{Var}(X)/\mathbb{E}(X)^{2}=o(1)$ , so, by Chebyshev’s inequality,

\mathbb{P}(X>0)\,=\,1-\mathbb{P}(X=0)\,\geqslant\,1-\frac{\mathrm{Var}(X)}{\mathbb{E}(X)^{2}}\,\geqslant\,1-o(1),

and hence this probability exceeds $1-\varepsilon$ for all large enough $n$ . Consequently, our proof of Theorem 1.2 will be complete once we verify Claim 3.1.

To prove the first bound in Claim 3.1, we note that for $\nu\leqslant n^{s+\delta}$ , we have $\mu(\nu)\leqslant\nu^{2}\leqslant\nu n^{s+\delta}$ . Hence, for $\nu\leqslant n^{s+\delta}$ ,

\displaystyle g(\nu)\,\leqslant\,{n\choose\nu}{k^{-\nu}}\left(1-\frac{1}{k}\right)^{n-\nu}\left(1+\frac{1}{k-1}\right)^{\nu n^{s+\delta}}.

Using the bounds $1+x\leqslant e^{x}\leqslant 1+2x$ valid for all $x\in(0,1)$ , we write

\left(1+\frac{1}{k-1}\right)^{n^{s+\delta}}\,\leqslant\,\exp\left(\frac{n^{s+\delta}}{k-1}\right)\,\leqslant\,\exp\left(n^{-1+2s+2\delta}\right)\,\leqslant\,1+2n^{-1+2s+2\delta},

where the second inequality holds for all large enough $n$ since $k=\tilde{\Omega}(n^{1-s})$ . Thus,

g(\nu)\,\leqslant\,{n\choose\nu}\left(\frac{1+2n^{-1+2s+2\delta}}{k}\right)^{\nu}\left(1-\frac{1}{k}\right)^{n-\nu}.

By the binomial formula,

\sum_{\nu\,\leqslant\,n^{s+\delta}}g(\nu)\,\leqslant\,\sum_{\nu=0}^{n}{n\choose\nu}\left(\frac{1+2n^{-1+2s+2\delta}}{k}\right)^{\nu}\left(1-\frac{1}{k}\right)^{n-\nu}\,=\,\left(1+\frac{2n^{-1+2s+2\delta}}{k}\right)^{n}.

Using again that $k=\tilde{\Omega}(n^{1-s})$ and assuming that $n$ is large enough, we obtain

\left(1+\frac{2n^{-1+2s+2\delta}}{k}\right)^{n}\,\leqslant\,\left(1+n^{-2+3s+3\delta}\right)^{n}\,\leqslant\,1+n^{-1+3s+3\delta}\,=\,1+o(1),

where in the last step we use that $3\delta<1-3s$ .

For the second part of Claim 3.1, note that $\mu(\nu)\leqslant\nu(k-1)$ for $\nu\leqslant k-1$ . Since $(1+1/x)^{x}<e$ for all $x>0$ and ${n\choose\nu}\leqslant(en/\nu)^{\nu}$ for all $\nu\in[0:n]$ , we see that for $n^{s+\delta}<\nu\leqslant k-1$ ,

\displaystyle g(\nu)\,\leqslant\,{n\choose\nu}{k^{-\nu}}\left(1+\frac{1}{k-1}\right)^{\nu(k-1)}\,\leqslant\,\left(\frac{e^{2}n}{\nu k}\right)^{\nu}\,\leqslant\,\left(\frac{e^{2}n^{1-s-\delta}}{k}\right)^{\nu}\,\leqslant\,n^{-\delta\nu/2}\,\leqslant\,n^{-\delta\,n^{s+\delta}/2},

where the second to last inequality holds for all large enough $n$ since $k=\tilde{\Omega}(n^{1-s})$ . Therefore,

\sum_{n^{s+\delta}\,<\,\nu\,\leqslant\,k-1}g(\nu)\,\leqslant\,n\cdot n^{-\delta\,n^{s+\delta}/2}\,=\,n^{-\delta\,n^{s+\delta}/2+1}\,=\,o(1).

Finally, we consider the case $\nu\geqslant k$ . This is the only part of the proof where the parameter $\rho$ is used and where the specific constant factor in front of $\rho/\ln\rho$ in the lower bound on $k$ plays a role. Given $\nu\geqslant k$ , we use the bound $\mu(\nu)\leqslant\rho\nu$ to write

g(\nu)\,\leqslant\,{n\choose\nu}{k^{-\nu}}\left(1+\frac{1}{k-1}\right)^{\rho\nu}.

Since $1/(1-\varepsilon/2)<1+\varepsilon$ for $0<\varepsilon<1$ , for all large enough $n$ , we have

k-1\,\geqslant\,(1+\varepsilon)\frac{(1-s)\rho}{(1-2s)\ln\rho}-1\,\geqslant\,\frac{(1-s)\rho}{(1-\varepsilon/2)(1-2s)\ln\rho}.

Since $1+x\leqslant e^{x}$ for all $x\in\mathbb{R}$ , we conclude that

\left(1+\frac{1}{k-1}\right)^{\rho}\,\leqslant\,\exp\left(\frac{\rho}{k-1}\right)\,\leqslant\,\exp\left(\frac{(1-\varepsilon/2)(1-2s)\ln\rho}{1-s}\right)\,=\,\rho^{\frac{(1-\varepsilon/2)(1-2s)}{1-s}}.

Therefore,

\frac{1}{k}\,\rho^{\frac{(1-\varepsilon/2)(1-2s)}{1-s}}\,\leqslant\,\frac{(1-2s)\ln\rho}{(1+\varepsilon)(1-s)\rho}\,\rho^{\frac{(1-\varepsilon/2)(1-2s)}{1-s}}\,=\,\frac{(1-2s)\ln\rho}{(1+\varepsilon)(1-s)}\,\rho^{-\frac{s}{1-s}-\frac{\varepsilon(1-2s)}{2(1-s)}}\,\leqslant\,n^{-s-\varepsilon(1-2s)/4},

where the last inequality holds for large $n$ since $\rho\geqslant n^{1-s}$ . Thus, for each $\nu\geqslant k$ ,

g(\nu)\,\leqslant\,\left(\frac{en}{\nu}\cdot n^{-s-\varepsilon(1-2s)/4}\right)^{\nu}\,\leqslant\,n^{-\varepsilon(1-2s)\nu/8},

as $k=\tilde{\Omega}(n^{1-s})$ . Hence,

\sum_{\nu=k}^{n}g(\nu)\,\leqslant\,n\cdot n^{-\varepsilon(1-2s)\nu/8}\,=\,n^{-\varepsilon(1-2s)\nu/8+1}\,=\,o(1),

and the proof is complete. ∎

4 DP-colorability based on degeneracy

4.1 Greedy Transversal Procedure

Consider a graph $G$ and an ordering of its vertices $(v_{i})_{i\in[n]}$ . Let $d_{i}^{-}$ be the back degree of $v_{i}$ , which is equal to the number of neighbors of $v_{i}$ whose indices are less than $i$ . Recall that a graph $G$ is $d$ -degenerate if there exists some ordering of vertices in $V(G)$ such that $d_{i}^{-}\leqslant d$ for all $i\in[n]$ , and the degeneracy of a graph $G$ is the smallest $d$ such that $G$ is $d$ -degenerate.

In order to prove Theorems 1.3 and 1.10, we shall employ the following greedy procedure to select a $b$ -fold transversal from a given cover:

Procedure 4.1 (Greedy Transversal Procedure (GT Procedure)).

This procedure takes as input a $d$ -degenerate graph $G$ , an $a$ -fold cover $\mathcal{H}=(L,H)$ of $G$ with $L(v)=\{(v,j):j\in[a]\}$ for all $v\in V(G)$ , and $b\in\mathbb{N}$ satisfying $b\leqslant a$ . The procedure gives as output a $b$ -fold transversal $T$ for $\mathcal{H}$ . For ease of notation we let $n=|V(G)|$ . For $(v,j)\in L(v)$ , we call $j$ the index of $(v,j)$ .

1.

Order the vertices $V(G)$ as $(v_{i})_{i\in[n]}$ so that $d_{i}^{-}\leqslant d$ for all $i\in[n]$ .
2.
Initialize $T=\emptyset$ and repeat the following as $i$ goes from $1$ to $n$ .
1. (a)
  
  Let $L^{\prime}(v_{i})=L(v_{i})\setminus N_{H}(T)$ .
2. (b)
  
  If $|L^{\prime}(v_{i})|\geqslant b$ , form a $b$ -element subset $T(v_{i})\subseteq L^{\prime}(v_{i})$ by selecting $b$ elements of $L^{\prime}(v_{i})$ with the smallest indices; otherwise, let $T(v_{i})=\{(v_{i},j):j\in[b]\}$ .
3. (c)
  
  Replace $T$ with $T\cup T(v_{i})$ .
3.

Output $T$ .

By construction, the output of this procedure is a $b$ -fold transversal for $\mathcal{H}$ . Furthermore, this transversal is independent if and only if $|L^{\prime}(v_{i})|\geqslant b$ for all $i\in[n]$ .¹¹1Alternatively, we could say that the procedure fails if $|L^{\prime}(v_{i})|<b$ for some $i$ . However, for the ensuing analysis it will be more convenient to assume that the procedure runs for exactly $n$ steps and that the sets $L^{\prime}(v_{i})$ and $T(v_{i})$ are well defined for all $i$ .

A crucial role in our analysis is played by the notion of negative correlation. A collection $(Y_{i})_{i\in[k]}$ of $\{0,1\}$ -valued random variables is negatively correlated if for every subset $I\subseteq[k]$ , we have

\mathbb{P}\left(\bigcap_{i\in I}\{Y_{i}=1\}\right)\,\leqslant\,\prod_{i\in I}\mathbb{P}(Y_{i}=1).

This notion is made useful by the fact that sums of negatively correlated random variables satisfy Chernoff–Hoeffding style bounds, as discovered by Panconesi and Srinivasan [PS97]. The exact formulation we use is from the paper [Mol19] by Molloy:

Lemma 4.2 ([PS97, Theorem 3.2], [Mol19, Lemma 3]).

Let $(X_{i})_{i\in[k]}$ be $\{0,1\}$ -valued random variables. Set $Y_{i}=1-X_{i}$ and $X=\sum_{i\in[k]}X_{i}$ . If $(Y_{i})_{i\in[k]}$ are negatively correlated, then

\mathbb{P}\left(X<\mathbb{E}(X)-t\right)\,<\,\exp\left(-\frac{t^{2}}{2\mathbb{E}(X)}\right)\quad\text{for all }0<t\leqslant\mathbb{E}(X).

Now consider running the GT Procedure on a $d$ -degenerate graph $G$ and the random $a$ -fold cover $\mathcal{H}(G,a)=(L,H)$ , producing a $b$ -fold transversal $T$ . For each $i\in[n]$ and $j\in[a]$ , let $X_{i,j}$ be the indicator random variable of the event $\{(v_{i},j)\in L^{\prime}(v_{i})\}$ and let $Y_{i,j}=1-X_{i,j}$ .

Lemma 4.3.

Consider the set of random variables $X_{i,j}$ as defined above.

(i)

For all $i\in[n]$ and $j\in[a]$ , we have $\displaystyle\mathbb{E}(X_{i,j})\,\geqslant\,\left(1-\frac{b}{a}\right)^{d}.$
(ii)

For each $i\in[n]$ , the variables $(Y_{i,j})_{j\in[a]}$ are negatively correlated.

Proof.

Similar statements have appeared in the literature; see, e.g., \cites[272]Molloy[Lemma 4.3]BKZ[Lemma 3.2]B2. Since our setting is somewhat different from these references, we include the proof here for completeness.

Fix any $i\in[n]$ . Write $t=d^{-}_{i}$ and let $u_{1}$ , …, $u_{t}$ be the neighbors of $v_{i}$ that precede it in the ordering $(v_{i})_{i\in[n]}$ . The sets $T(u_{1})$ , …, $T(u_{t})$ are constructed in a way that is probabilistically independent from the matchings in $H$ corresponding to the edges $u_{1}v_{i}$ , …, $u_{t}v_{i}$ . Therefore,

S_{r}\,=\,\{j\in[a]\,:\,(v_{i},j)\in N_{H}(T(u_{r}))\}

for $r\in[t]$ are mutually independent uniformly random $b$ -element subsets of $[a]$ . Hence,

\mathbb{E}(X_{i,j})\,=\,\mathbb{P}(j\notin S_{r}\text{ for all }r\in[t])\,=\,\left(1-\frac{b}{a}\right)^{t}\,\geqslant\,\left(1-\frac{b}{a}\right)^{d},

where in the last step we use that $t=d^{-}_{i}\leqslant d$ . This proves part (i).

For part (ii), we first note that if $b=a$ , then the output of the GT Procedure on $\mathcal{H}(G,a)$ is deterministic, so the negative correlation holds trivially in this case. Now suppose that $b<a$ and consider any $I\subset[a]$ and $j\in[a]\setminus I$ . We claim that

\mathbb{P}\left(I\subseteq S\,\middle|\,j\notin S\right)\,\geqslant\,\mathbb{P}\left(I\subseteq S\right),

(4.1)

where $S=\bigcup_{r\in[t]}S_{r}$ . To show (4.1), pick $b$ -element subsets $S_{1}^{\prime}$ , …, $S_{t}^{\prime}$ of $[a]\setminus\{j\}$ independently and uniformly at random and let $S^{\prime}=\bigcup_{r\in[t]}S_{r}^{\prime}$ . The event $\{j\notin S\}$ occurs if and only if $j\notin S_{r}$ for all $r\in[t]$ . It follows that the distribution of the tuple $(S_{1},\ldots,S_{t})$ conditioned on the event $\{j\notin S\}$ is the same as the distribution of $(S_{1}^{\prime},\ldots,S_{t}^{\prime})$ . Therefore, we need to argue that

\mathbb{P}\left(I\subseteq S^{\prime}\right)\,\geqslant\,\mathbb{P}\left(I\subseteq S\right).

To this end, we employ a coupling argument. Form $b$ -element subsets $S_{r}^{\prime\prime}\subseteq[a]\setminus\{j\}$ as follows: If $j\notin S_{r}$ , then let $S_{r}^{\prime\prime}=S_{r}$ ; otherwise, pick $j_{r}\in[a]\setminus S_{r}$ uniformly at random and let $S_{r}^{\prime\prime}=(S_{r}\setminus\{j\})\cup\{j_{r}\}$ . By construction, $S_{1}^{\prime\prime}$ , …, $S_{t}^{\prime\prime}$ are independent and uniformly random $b$ -element subsets of $[a]\setminus\{j\}$ , so, letting $S^{\prime\prime}=\bigcup_{r\in[t]}S^{\prime\prime}_{r}$ , we can write

\displaystyle\mathbb{P}\left(I\subseteq S^{\prime}\right)\,=\,\mathbb{P}\left(I\subseteq S^{\prime\prime}\right)\,\geqslant\,\mathbb{P}\left(I\subseteq S\right),

where the inequality is satisfied because $S^{\prime\prime}\supseteq S\setminus\{j\}$ .

Since for any events $A$ , $B$ , the inequalities $\mathbb{P}(A|B)\geqslant\mathbb{P}(A)$ and $\mathbb{P}(B|A)\geqslant\mathbb{P}(B)$ are equivalent, we conclude from (4.1) that $\mathbb{P}(j\notin S|I\subseteq S)\geqslant\mathbb{P}(j\notin S)$ , or, equivalently, $\mathbb{P}(j\in S|I\subseteq S)\leqslant\mathbb{P}(j\in S)$ . Using the definition of the set $S$ , this inequality can be rewritten as

\mathbb{P}\left(Y_{i,j}=1\,\middle|\,\bigcap_{j^{\prime}\in I}\{Y_{i,j^{\prime}}=1\}\right)\,\leqslant\,\mathbb{P}\left(Y_{i,j}=1\right).

(4.2)

Finally, given any set $I=\{j_{1},\ldots,j_{k}\}\subseteq[a]$ , we apply (4.2) iteratively with $\{j_{1},\ldots,j_{\ell-1}\}$ in place of $I$ and $j_{\ell}$ in place of $j$ to obtain the desired inequality

\mathbb{P}\left(\bigcap_{j\in I}\{Y_{i,j}=1\}\right)\,\leqslant\,\prod_{j\in I}\mathbb{P}(Y_{i,j}=1).\qed

4.2 DP-colorability based on degeneracy

We now apply the GT Procedure to prove Theorem 1.3, whose statement we repeat here for convenience.

Theorem 1.3.

Proof.

We construct a transversal $T$ using the GT Procedure with inputs $G$ , $a=k$ , the cover $\mathcal{H}(G,k)$ , and $b=1$ . Our aim is to argue that, with probability at least $1-\varepsilon$ , the sets $L^{\prime}(v_{i})$ for all $i\in[n]$ are nonempty, and hence $T$ is independent with probability at least $1-\varepsilon$ , as desired.

Recall from §4.1 that for $i\in[n]$ and $j\in[k]$ , $X_{i,j}$ is the indicator random variable of the event $\{(v_{i},j)\in L^{\prime}(v_{i})\}$ . Let

X_{i}\,=\,\sum_{j\in[k]}X_{i,j}\,=\,|L^{\prime}(v_{i})|.

Using Lemma 4.3 (i) and the linearity of expectation, we get

\mathbb{E}(X_{i})\,\geqslant\,k\left(1-\frac{1}{k}\right)^{d}\,\geqslant\,k\,\exp\left(-(1-o(1))\frac{d}{k}\right)\,>\,d^{2\varepsilon/3},

where the last inequality holds for $\varepsilon<1/2$ assuming that $n$ is large enough as a function of $\varepsilon$ (since then $d$ and $k$ are also large). Combining Lemma 4.3 (ii) with Lemma 4.2, we obtain

\displaystyle\mathbb{P}(X_{i}=0)\,\leqslant\,\mathbb{P}\left(X_{i}<\frac{\mathbb{E}(X_{i})}{2}\right)\,<\,\exp\left(-\frac{\mathbb{E}(X_{i})}{8}\right)\,\leqslant\,e^{-d^{2\varepsilon/3}/8}\,\leqslant\,e^{-\ln^{4/3}n/8}\,<\,\frac{\varepsilon}{n},

where the last inequality holds for large $n$ . By the union bound, it follows that

\mathbb{P}(X_{i}=0\text{ for some }i\in[n])\,<\,\varepsilon,

and we are done. ∎

4.3 Fractional DP-colorability based on degeneracy

Here we prove Theorem 1.10:

Theorem 1.10.

Proof.

Without loss of generality, we may assume that $\varepsilon<1$ . Take $a$ , $b\in\mathbb{N}$ such that

(1+\varepsilon/2)\frac{d}{\ln d}\,\leqslant\,\frac{a}{b}\,\leqslant\,k.

Here we may—and will—assume that $a$ and $b$ are sufficiently large as functions of $n$ . We construct a $b$ -fold transversal $T$ using the GT Procedure with inputs $G$ and $\mathcal{H}(G,a)$ . Our aim is to show that the sets $L^{\prime}(v_{1})$ , …, $L^{\prime}(v_{n})$ all have size at least $b$ with probability at least $1-\varepsilon$ , which implies that $T$ is independent with probability at least $1-\varepsilon$ , as desired.

As in the proof of Theorem 1.3 presented in §4.2, we recall that for $i\in[n]$ and $j\in[a]$ , $X_{i,j}$ is the indicator random variable of the event $\{(v_{i},j)\in L^{\prime}(v_{i})\}$ , and define

X_{i}\,=\,\sum_{j\in[a]}X_{i,j}\,=\,|L^{\prime}(v_{i})|.

Using Lemma 4.3 (i) and the linearity of expectation, we get

	$\displaystyle\mathbb{E}(X_{i})\,\geqslant\,a\left(1-\frac{b}{a}\right)^{d}\,$	$\displaystyle\geqslant\,b\cdot(1+\varepsilon/2)\frac{d}{\ln d}\cdot\left(1-\frac{\ln d}{(1+\varepsilon/2)d}\right)^{d}$
		$\displaystyle\geqslant\,b\cdot(1+\varepsilon/2)\frac{d}{\ln d}\cdot d^{-1/(1+\varepsilon/2)}\,>\,b\,d^{\varepsilon/3},$

where in the last step we use that $\varepsilon<1$ and $d$ is large as a function of $\varepsilon$ . In particular, assuming $d$ is large enough, we have $\mathbb{E}(X_{i})>2b$ . By Lemma 4.3 (ii) and Lemma 4.2, we have

\displaystyle\mathbb{P}(X_{i}<b)\,\leqslant\,\mathbb{P}\left(X_{i}<\frac{\mathbb{E}(X_{i})}{2}\right)\,<\,\exp\left(-\frac{\mathbb{E}(X_{i})}{8}\right)\,\leqslant\,e^{-b/4}\,<\,\frac{\varepsilon}{n},

where for the last inequality we assume that $b$ is large enough as a function of $n$ . By the union bound, it follows that

\mathbb{P}(X_{i}<b\text{ for some }i\in[n])\,<\,\varepsilon,

and the proof is complete. ∎

5 DP-thresholds

Combining Proposition 1.1 and Theorem 1.2, we obtain DP-thresholds and sharp DP-thresholds for sufficiently dense graph sequences:

Theorem 5.1.

Let $\mathcal{G}=(G_{\lambda})_{\lambda\in\mathbb{N}}$ be a sequence of graphs with $|V(G_{\lambda})|$ , $\rho(G_{\lambda})\to\infty$ as $\lambda\to\infty$ . Define a function $t_{\mathcal{G}}(\lambda)=\rho(G_{\lambda})/\ln\rho(G_{\lambda})$ . If

\lim_{\lambda\to\infty}\frac{\ln\rho(G_{\lambda})}{\ln\ln|V(G_{\lambda})|}\,=\,\infty,

(5.1)

then $t_{\mathcal{G}}(\lambda)$ is a DP-threshold function for $\mathcal{G}$ . Furthermore, if

\lim_{\lambda\to\infty}\frac{\ln\rho(G_{\lambda})}{\ln|V(G_{\lambda})|}\,=\,1,

(5.2)

then $t_{\mathcal{G}}(\lambda)$ is a sharp DP-threshold function for $\mathcal{G}$ .

Proof.

Assume (5.1). Set $n_{\lambda}=|V(G_{\lambda})|$ and $\rho_{\lambda}=\rho(G_{\lambda})$ . Since $n_{\lambda}\to\infty$ , (5.1) implies that $\rho_{\lambda}\to\infty$ as well. Take any sequence $\kappa=(k_{\lambda})_{\lambda\in\mathbb{N}}$ of positive integers satisfying $k_{\lambda}\leqslant t_{\mathcal{G}}(\lambda)$ . Given $\varepsilon>0$ , for all large enough $\lambda\in\mathbb{N}$ , we have $\rho_{\lambda}\geqslant\exp(e/\varepsilon)$ and $k_{\lambda}\leqslant\rho_{\lambda}/\ln\rho_{\lambda}$ . Therefore, by Proposition 1.1, $\mathbb{P}(\text{$G_{\lambda}$ is $\mathcal{H}(G_{\lambda},k_{\lambda})$-colorable})\leqslant\varepsilon$ for all large enough $\lambda$ , so $\mathcal{G}$ is non- $\kappa$ -DP-colorable w.h.p. Now suppose a sequence $\kappa=(k_{\lambda})_{\lambda\in\mathbb{N}}$ satisfies $k_{\lambda}/t_{\mathcal{G}}(\lambda)\to\infty$ . Let $d_{\lambda}$ be the degeneracy of $G_{\lambda}$ and note that $\rho_{\lambda}\leqslant d_{\lambda}\leqslant 2\rho_{\lambda}$ . Take any $\varepsilon\in(0,1/2)$ . By (5.1), $d_{\lambda}\geqslant\rho_{\lambda}\geqslant\ln^{2/\varepsilon}n$ for all large enough $\lambda$ . Since

\lim_{\lambda\to\infty}\left.k_{\lambda}\middle/\frac{d_{\lambda}}{\ln d_{\lambda}}\right.\,=\,\lim_{\lambda\to\infty}\left.k_{\lambda}\middle/\frac{\rho_{\lambda}}{\ln\rho_{\lambda}}\right.\,=\,\infty,

we can apply Theorem 1.3 to conclude that $\mathbb{P}(\text{$G_{\lambda}$ is $\mathcal{H}(G_{\lambda},k_{\lambda})$-colorable})\geqslant 1-\varepsilon$ . As $\varepsilon$ is arbitrary, it follows that $\mathcal{G}$ is $\kappa$ -DP-colorable w.h.p.

To prove the “furthermore” part, assume that (5.2) holds. Take any $\varepsilon>0$ and suppose a sequence $\kappa=(k_{\lambda})_{\lambda\in\mathbb{N}}$ satisfies $k_{\lambda}\geqslant(1+\varepsilon)t_{\mathcal{G}}(\lambda)$ for all large enough $\lambda$ . Consider any $\varepsilon^{\prime}\in(0,\varepsilon)$ and set $s_{\lambda}=1-\ln\rho_{\lambda}/\ln n_{\lambda}$ , so $\rho_{\lambda}=n_{\lambda}^{1-s_{\lambda}}$ . By (5.2), $s_{\lambda}\to 0$ as $\lambda\to\infty$ . Thus, for all large enough $\lambda$ ,

1+\frac{s_{\lambda}}{1-2s_{\lambda}}\,\leqslant\,\sqrt{1+\varepsilon^{\prime}}.

For every such $\lambda$ , we may apply Theorem 1.2 with $\varepsilon^{\prime\prime}=\sqrt{1+\varepsilon^{\prime}}-1<\varepsilon^{\prime}$ in place of $\varepsilon$ to conclude that $\mathbb{P}(\text{$G_{\lambda}$ is $\mathcal{H}(G_{\lambda},k_{\lambda})$-colorable})\geqslant 1-\varepsilon^{\prime\prime}\geqslant 1-\varepsilon^{\prime}$ . Since $\varepsilon^{\prime}$ is arbitrary, it follows that $\mathcal{G}$ is $\kappa$ -DP-colorable w.h.p., and the proof is complete. ∎

The following observation is immediate from the definitions:

Observation 5.2.

If $t(\lambda)$ is a sharp DP-threshold function for a sequence of graphs $\mathcal{G}=(G_{\lambda})_{\lambda\in\mathbb{N}}$ and $t^{\prime}(\lambda)$ is another function such that $\lim_{\lambda\to\infty}t^{\prime}(\lambda)/t(\lambda)=1$ , then $t^{\prime}(\lambda)$ is also a sharp DP-threshold function for $\mathcal{G}$ .

We will now use this to find threshold functions for specific sequences of graphs.

Corollary 1.6.

For $\mathcal{G}=(K_{n})_{n\in\mathbb{N}}$ , the sequence of complete graphs, $t_{\mathcal{G}}(n)=n/(2\ln n)$ is a sharp DP-threshold function.

Proof.

The maximum density of $K_{n}$ is $\rho_{n}=(n-1)/2$ . By Theorem 5.1, a sharp DP-threshold function for $\mathcal{G}$ is $\rho_{n}/\ln\rho_{n}=(n-1)/(2\ln((n-1)/2))$ . Since

\lim_{n\to\infty}\left.\frac{n}{2\ln n}\middle/\frac{n-1}{2\ln\left(\frac{n-1}{2}\right)}\right.\,=\,1,

we see that $n/(2\ln n)$ is a sharp DP-threshold function for $\mathcal{G}$ by Observation 5.2. ∎

Corollary 1.7.

Proof.

The maximum density of $K_{m\times n}$ is $\rho_{n}=(m-1)n/2$ . This is a linear function of $n$ , so we may apply Theorem 5.1 to conclude that a sharp DP-threshold function for $\mathcal{G}$ is

\frac{\rho_{n}}{\ln\rho_{n}}\,=\,\frac{(m-1)n}{2\ln\left(\frac{(m-1)n}{2}\right)}.

The desired result follows by Observation 5.2 since

\lim_{n\to\infty}\left.\frac{(m-1)n}{2\ln n}\middle/\frac{(m-1)n}{2\ln\left(\frac{(m-1)n}{2}\right)}\right.\,=\,1.\qed

Acknowledgment. We are grateful to the anonymous referee for helpful comments.

References

[Alo00] N. Alon “Degrees and choice numbers” In Random Structures & Algorithms 16, 2000, pp. 364–368
[AL02] A. Amit and N. Linial “Random graph coverings I: General theory and graph connectivity” In Combinatorica 22.1, 2002, pp. 1–18
[AL06] A. Amit and N. Linial “Random lifts of graphs: Edge expansion” In Combin. Probab. Comput. 15.3, 2006, pp. 317–332
[ALM02] A. Amit, N. Linial and J. Matoušek “Random lifts of graphs: Independence and chromatic number” In Random Structures & Algorithms 20.1, 2002, pp. 1–22
[ACK19] S. Assadi, Y. Chen and S. Khanna “Sublinear algorithms for $({\Delta}+1)$ vertex coloring” Full version: https://arxiv.org/abs/1807.08886 In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019, pp. 767–786
[Ber16] A. Bernshteyn “The asymptotic behavior of the correspondence chromatic number” In Discrete Math. 339, 2016, pp. 2680–2692
[Ber19] A. Bernshteyn “The Johansson–Molloy theorem for DP-coloring” In Random Structures & Algorithms 54.4, 2019, pp. 653–664
[Ber+23] A. Bernshteyn, T. Brazelton, R. Cao and A. Kang “Counting colorings of triangle-free graphs” In J. Combin. Theory Ser. B 161, 2023, pp. 86–108
[BK18] A. Bernshteyn and A. Kostochka “On differences between DP-coloring and list coloring (in Russian)” English version: https://arxiv.org/abs/1705.04883 In Matematicheskie Trudy 21.2, 2018, pp. 61–71
[BKP17] A. Bernshteyn, A. Kostochka and S. Pron “On DP-coloring of graphs and multigraphs (in Russian)” English version: https://arxiv.org/abs/1609.00763 In Siberian Mathematical Journal 58.1, 2017, pp. 36–47
[BKZ20] A. Bernshteyn, A. Kostochka and X. Zhu “Fractional DP-colorings of sparse graphs” In J. Graph Theory 39.2, 2020, pp. 203–221
[Cas11] C.J. Casselgren “Vertex coloring complete multipartite graphs from random lists of size 2” In Discrete Math. 11.13, 2011, pp. 1150–1157
[Cas12] C.J. Casselgren “Coloring graphs from random lists of size 2” In European J. Combin. 33.2, 2012, pp. 168–181
[Cas14] C.J. Casselgren “Coloring graphs from random lists of fixed size” In Random Structures & Algorithms 44.13, 2014, pp. 317–327
[Cas18] C.J. Casselgren “Coloring graphs of various maximum degree from random lists” In Random Structures & Algorithms 52.1, 2018, pp. 54–73
[CH16] C.J. Casselgren and R. Häggkvist “Coloring complete and complete bipartite graphs from random lists” In Graphs Combin. 32, 2016, pp. 533–542
[DP18] Z. Dvořák and L. Postle “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8” In J. Combin. Theory Ser. B 129, 2018, pp. 38–54
[DY23] Z. Dvořák and L. Yepremyan “Correspondence coloring of random graphs” https://arxiv.org/abs/2307.15048 (preprint), 2023
[ERT79] P. Erdős, L. Rubin and H. Taylor “Choosability in graphs” In Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI 26, 1979, pp. 125–157
[GR01] C. Godsil and G. Royle “Algebraic Graph Theory” 207, Graduate Texts in Mathematics New York: Springer, 2001
[KN04] M. Krivelevich and A. Nachmias “Colouring complete powers of cycles from random lists” In European J. Combin. 25.7, 2004, pp. 961–968
[KN06] M. Krivelevich and A. Nachmias “Coloring complete bipartite graphs from random lists” In Random Structures & Algorithms 29.4, 2006, pp. 436–449
[LR05] N. Linial and E. Rozenman “Random lifts of graphs: Perfect matchings” In Combinatorica 25.4, 2005, pp. 407–424
[Mol19] M. Molloy “The list chromatic number of graphs with small clique number” In J. Combin. Theory Ser. B 134, 2019, pp. 264–284
[PS97] A. Panconesi and A. Srinivasan “Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds” In SIAM J. Comput. 26.2, 1997, pp. 350–368
[Viz76] V.G. Vizing “Coloring the vertices of a graph in prescribed colors (in Russian)” In Diskret. Analiz. 29, 1976, pp. 3–10
[Wes20] D.B. West “Combinatorial Mathematics” Cambridge, UK: Cambridge University Press, 2020

	$\displaystyle\mathbb{P}(E_{uv})\,$	$\displaystyle=\,\mathbb{P}(A_{uv})\cdot\mathbb{P}(B_{uv}\|A_{uv})$
		$\displaystyle=\,\mathbb{P}(A_{uv})\cdot\left(\mathbb{P}\left(C_{uv}\|A_{uv}\right)+\mathbb{P}\left(B_{uv}\cap\overline{C_{uv}}\|A_{uv}\right)\right)$
		$\displaystyle=\,\mathbb{P}(A_{uv})\cdot\left(\mathbb{P}\left(C_{uv}\|A_{uv}\right)+\mathbb{P}\left(\overline{C_{uv}}\|A_{uv}\right)\cdot\mathbb{P}\left(B_{uv}\|A_{uv}\cap\overline{C_{uv}}\right)\right)$
		$\displaystyle=\,\left(\frac{k-1}{k}\right)\left(\frac{1}{k-1}+\left(\frac{k-2}{k-1}\right)^{2}\right)\,=\,p^{2}+\frac{1}{k^{2}(k-1)}.$

DP-Coloring of Graphs from Random Covers

Abstract

1 Introduction

1.1 Basic terminology and notation

1.2 Graph coloring, list coloring, and DP-coloring

1.3 Random DP-covers

1.4 Outline of the main results

1.4.1 DP-colorability and density

Proposition 1.1.

Theorem 1.2.

Theorem 1.3.

Conjecture 1.4.

Proposition 1.5.

1.4.2 Threshold functions

Corollary 1.6.

Corollary 1.7.

Question 1.8.

1.4.3 Fractional DP-coloring

Proposition 1.9.

Theorem 1.10.

2 DP-colorability with probability close to 0

2.1 A First Moment argument

Observation 2.1.

Proof.

Proposition 1.9.

Proof.

2.2 Sparse graphs with low probability of kk-DP-colorability

Proposition 1.5.

Proof.

3 DP-colorability with probability close to 11 for dense graphs

Theorem 1.2.

Proof.

Claim 3.1.

4 DP-colorability based on degeneracy

4.1 Greedy Transversal Procedure

Procedure 4.1 (Greedy Transversal Procedure (GT Procedure)).

Lemma 4.2 ([PS97, Theorem 3.2], [Mol19, Lemma 3]).

Lemma 4.3.

Proof.

4.2 DP-colorability based on degeneracy

Theorem 1.3.

Proof.

4.3 Fractional DP-colorability based on degeneracy

Theorem 1.10.

Proof.

5 DP-thresholds

Theorem 5.1.

Proof.

Observation 5.2.

Corollary 1.6.

Proof.

Corollary 1.7.

Proof.

References

2 DP-colorability with probability close to $0$

2.2 Sparse graphs with low probability of $k$ -DP-colorability

3 DP-colorability with probability close to $1$ for dense graphs