The ACO Seminar (2018–2019)

January 31, 3:30pm, Wean 8220
Michael Anastos, Carnegie Mellon University
Coloring (random) hypergraphs

Abstract:

The talk will consist of two parts, both concerning colorings of (random) hypergraphs. 1. Let $W_q$ denote the set of proper $q$-colorings of the random graph $G_{n,m}$, $m = dn/2$ and let $H_q$ be the graph with vertex set $W_q$ where two vertices are connected iff the corresponding proper colorings differ in a single vertex. We show that for sufficiently large $d$, if $q>(1+o(1))d/\log d$ then $H_q$ is connected, providing an asymptotic matching upper bound to the lower bound given by Achliopta and Coja-Oghlan. We then extend our result to random hypergraphs. 2. We study an MCMC algorithm for sampling a (near) uniform q-coloring of a simple k-uniform hypegraph with n vertices and maximum degree D. Here $q>max(C_1(k) \log n, C_2(k)D^{1/k-1}$. This is joint work with Alan M. Frieze.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.