## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, April 13, 2017, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Nemanja Skoric

## Bootstrapping graph packing

For given graphs H and G, H-packing in G is a union of vertex disjoint copies of H in G. Conlon, Gowers, Samotij, and Schacht showed that for a constant gamma > 0, there exists C > 0 such that if p >= C n^{-1/m2(H)} then a.a.s. spanning subgraph G of the random graph G(n,p) with minimum degree at least (1 - 1/crc(H) + gamma )np contains an H-packing that covers all but at most gamma n vertices. Here, crc(H) denotes the critical chromatic threshold, a parameter introduced by Komlós and m2(H) is a certain density measure of H. We show that this theorem can be bootstraped to obtain an H-packing covering all but at most gamma (C/p)^{m_2(H)} vertices, which gives a sublinear leftover when p >> n^{-1/m2(H)}. In the case where H is a triangle this answers the question of Balogh, Lee, and Samotij. Furthermore, we give an upper bound on the size of an H-packing for certain ranges of p. The talk is based on a joint work with Rajko Nenadov.

Information for students and suggested topics for student talks