Loading Events

CMSA Combinatorics, Probability and Physics Seminar: Prague dimension of random graphs

CMSA EVENTS

When: November 23, 2021
9:30 am - 10:30 am
Where: Virtually
Speaker: Lutz Warnke - UC San Diego
The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s: as a combinatorial measure of complexity, it is closely related to clique edges coverings and partitions. 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 Kalen Patton, see https://arxiv.org/abs/2011.09459   

Password: 1251442