论文标题
随机图的布拉格维度
Prague dimension of random graphs
论文作者
论文摘要
1970年代，Nesetril，Pultr和Rodl引入了图形的布拉格维度。证明了furedi和Kantor的猜想，我们表明二项式随机图的布拉格维度通常为n/log n顺序N/log n，用于恒定的边缘概要。主要的新证明成分是带有大均匀性的随机超图（即大小O（log n）的边缘）的Pippenger-Spencer类型边缘色。
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).
