Sparse universal graphs (Q1612288)

Improving a recent result of Alon et al., Alon and Asodi give an explicit construction of a graph of order \(n\) having \(O(n^{2-\varepsilon})\) edges, for \(\varepsilon=0.133\dots \), that is universal for the graphs of order \(n\) and maximum degree three, i.e. it contains all such graphs as subgraphs. As a second main result the authors prove that the minimum number of edges in a graph that is universal for the graphs having at most \(n\) edges and no isolated vertices is \(\Theta ( \frac{n^2}{\log^2 n})\) which proves that a corresponding lower bound due to Babai et al. is essentially best-possible. The proofs strongly rely on probabilistic methods.