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.
The ACO Seminar (2018–2019)