2025/12/09 by Joos, Felix, Mattos, Letícia
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis #Stochastic processes and statistical mechanics
paper · doi:10.48550/arxiv.2512.08899
The Prague dimension of a graph G is defined as the minimum number of complete graphs whose direct product contains G as an induced subgraph. Introduced in the 1970s by Nešetřil, Pultr, and Rödl -- and motivated by the work of Dushnik and Miller, as well as by the induced Ramsey theorem -- determining the Prague dimension of a graph is a notoriously hard problem. In this paper, we show that for all ε > 0 and p such that n-1+ε ≤ p ≤ n-ε, with high probability the Prague dimension of Gn,p is Θε(pn), which improves upon a recent result by Molnar, Rödl, Sales and Schacht. Inspired by the work of Bennett and Bohman, our approach centres on analysing a random greedy process that builds an independent set of size Ω(p-1log pn) by iteratively selecting vertices uniformly at random from the common non-neighbourhood of those already chosen. Using the differential equation method, we show that every non-edge is essentially equally likely to be covered by this process, which is key to establishing our bound.