Prague dimension of random graphs

DOI10.1007/S00493-023-00016-9MaRDI QIDQ6081403zbMATH OpenFDO

Authors He Guo, Kalen Patton, Lutz Warnke

Publication date 4 October 2023

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.09459

zbMATH Keywords

differential equation methodPrague dimensionrandom greedy approachsemi-random approach

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

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).

Recommendations

• Covering the edges of a random graph by cliques
• Clique coverings of the edges of a random graph
• Publication:4945058
• scientific article; zbMATH DE number 3762108
• The chromatic number of random graphs

Cited in

(4)

• Fractal networks: topology, dimension, and complexity
• A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
• Covering the edges of a random hypergraph by cliques
• On the concentration of the chromatic number of random graphs

This page was built for publication: Prague dimension of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081403)