Prague dimension of random graphs
arXiv:2011.09459 · doi:10.1007/s00493-023-00016-9
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).
arXiv comment20 pages
References in corpus (10)
- On the method of typical bounded differences
- Upper tails for arithmetic progressions in random subsets
- On Wormald's differential equation method
- Pseudorandom hypergraph matchings
- Large girth approximate Steiner triple systems
- Packing nearly optimal Ramsey R(3,t) graphs
- On the missing log in upper tail estimates
- On the product dimension of clique factors
- Counting extensions revisited
- Graph fractal dimension and structure of fractal networks: a combinatorial perspective