 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, December 04, 2014, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

## Almost-spanning universality in random graphs

A graph $G$ is said to be $\mathcal{H}(N, \Delta)$-universal if it contains a copy of every graph on $N$ vertices with maximum degree at most $\Delta$. Determining the threshold for the property that a typical graph $G \sim G(n,p)$ is $\mathcal{H}(N, \Delta)$-universal is an intriguing question in the theory of random graphs, with two most common scenarios being $N = n$ (spanning subgraphs) and $N = (1 - \varepsilon)n$ (almost-spanning subgraphs). A result of Alon, Capalbo, Kohayakawa, Rödl, Ruciński and Szemerédi shows that for $N = (1 - \varepsilon)n$ it suffices to take $p \ge (\log n / n)^{1/\Delta}$. This was further improved by Dellamonica, Kohayakawa, Rödl and Rucińcki, who showed that for the same value of $p$ one can take $N$ to be as large as $n$. On the other hand, the only known lower bound on the threshold for these two properties is of order $n^{-2/(\Delta + 1)}$. It is worth noting that even for the simpler property of containing a single (arbitrary) spanning graph $H \in \mathcal{H}(n, \Delta)$, no better bound on $p$ is known (result of Alon and Füredi).

We make a step towards closing this gap. In particular, we improve the result of Alon et al. by showing that, in the case $\Delta \ge 3$, a typical graph $G \sim G(n, p)$ is $\mathcal{H}((1 - \varepsilon)n, \Delta)$-universal for $p \ge n^{-1/(\Delta - 1)} \log^5 n$. This determines, up to the logarithmic factor, the asymptotic value of the threshold in case $\Delta = 3$. Using similar ideas, we also show that there exists a constant $\delta > 0$ such that for any graph $H \in \mathcal{H}(n, \Delta)$ and $p \ge n^{-1/\Delta - \delta}$, a typical graph $G \sim G(n,p)$ contains a copy of $H$. This gives a slight improvement over the result of Alon and Füredi.

Joint work with David Conlon, Asaf Ferber and Nemanja Škorić.

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks