Charles Kenney, Rutgers University

Abstract

The p-random subset X_p of X is given by independently keeping each x in X with probability p (and throwing it away with probability 1-p.) Let H be a nontrivial hypergraph on X. Let p_c(H) be the unique probability such that X_{p_c(H)} contains an edge of H with probability 1/2.

We say a random set A is q-spread if, for all S, the probability that S is a subset of A is at most q^(#S). We say a hypergraph H supports the random set A if A is an edge of H with probability 1. A seminal result of Frankston, Kahn, Narayanan, and Park (FKNP), proved at Rutgers in the late teens, relates values of q for which H supports a q-spread distribution, to p_c(H). Finding a well-spread distribution (i.e. q-spread with small q) is often easier than directly finding p_c.

A series of papers, culminating in Jain & Pham/Keevash 2022, applied FKNP to bound p_c for Latin Squares, which can be phrased as a random list edge coloring problem on K_{n,n}. The heart of these results is the construction of q-spread measures on these colorings. In this talk, I will introduce (without proof) FKNP, its strengthening by (Jinyoung) Park and Pham, and a non-uniform extension by (Bryan) Park and Vondrak. I will then discuss applications of these results to random list coloring in a more general, but less stringent, setting than that of Jain & Pham/Keevash.