Almost spanning universality in random graphs.

Resumen:

We will study embeddings of large graphs of bounded degree in G(n,p). Johansson, Kahn, Vu determined the threshold for G(n,p) to contain a K_(r+1)-factor, i.e., a collection of n/(r+1) vertex disjoint copies of K_(r+1). The threshold turns out to be the same as for the property ‘every vertex is contained in a (r+1)-clique’, which is a necessary condition for containing a K_(r+1)-factor.

Now for integers t,D, let H(t,D) be the class of t-vertex graphs and maximum degree at most D. It is conjectured that whp G(n,p) should contain every graph in H(n,D) as soon as it contains a K_(D+1)-factor. This problem was the object of interest of many researchers and it is still open for D > 3. Here we study the almost spanning version of the problem as it was done by Ferber, Luh and Nguyen. They proved that, for D>4, whp G(n,p) contains every graph in H((1-o(1))n, D) as soon as it contains a K_(D+1)-factor.

Posted on Oct 23, 2023 in Seminario de Grafos, Seminars