## Prague dimension of random graphs

Series
ACO Student Seminar
Time
Friday, November 20, 2020 - 1:00pm for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Kalen Patton – Math, Georgia Tech – kpatton33@gatech.edu
Organizer
He Guo

Various notions of dimension are important throughout mathematics, and for graphs the so-called Prague dimension 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 He Guo and Lutz Warnke.