Prague dimension of random graphs

Graph Theory Seminar
Tuesday, January 26, 2021 - 3:45pm for 1 hour (actually 50 minutes)
Location For password, please email Anton Bernshteyn (bahtoh ~at~
He Guo – Georgia Institute of Technology – he.guo@gatech.edu
Anton Bernshteyn

The Prague dimension of graphs was introduced by Nešetřil, Pultr and Rödl in the 1970s. Proving a conjecture of Füredi 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.