Algebra and Combinatorics Seminar

Date: February 26, 2021

Time: 3:00PM - 4:00PM

Location: Zoom

Speaker: He Guo, Georgia Tech

Title: Prague dimension of random graphs

Abstract: The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/log n for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n). Based on joint work with Kalen Patton and Lutz Warnke.