Prague dimension of random graphs
- Series
- ACO Student Seminar
- Time
- Friday, November 20, 2020 - 13:00 for 1 hour (actually 50 minutes)
- Location
- ONLINE
- Speaker
- Kalen Patton – Math, Georgia Tech – kpatton33@gatech.edu
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.