DP-coloring of graphs from random covers

Title of the Talk: DP-coloring of graphs from random covers
Speakers: Hemanshu Kaul
Host Faculty: Dr.Rogers Mathew
Date: May 30, 2025
Time: 11:00am to 12:00 pm
Venue: CS-LH1

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 tso an independent transversal in an auxiliary structure called a DP-cover of $G$ (that arises from related concept of covering maps in topology).

In this talk, we will discuss the notion of random DP-covers (equivalently, random lifts introduced by Amit and Linial in 2002) and study the behavior of DP-coloring from such random covers. We will describe 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$ goes to infinity 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 and show bounds on cover size $k$ that are within a factor of 2 of each other, for density at least polylog in number of vertices. We also prove fractional DP-coloring analogs of some of these results.

This is joint work with A. Bernshteyn, D. Dominik, and J. Mudrock.

Speaker:

Hemanshu Kaul, Associate professor, Department of Applied Mathematics, Illinois Institute of Technology, Chicago