## 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: Tuesday, December 02, 2014, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Frank Mousset

## Packing a randomly edge-colored random graph with rainbow k-outs

Let G be a graph on n vertices and let k,c be fixed positive integers. The random subgraph G_k of G is obtained by letting each vertex of G pick k neighbours uniformly at random from its neighbourhood in G ("k-out"). The edge-coloured random subgraph G(p,c) of G is obtained by keeping each edge independently with probability p, and then colouring each edge randomly with a color from the set {1,...,c}.

We show that if p >> log n/delta(G), then in a typical H ~ G(p,kn), one can find t = (1-o(1)) delta(G)p/(2k) edge-disjoint subgraphs H_i, with the following properties: (a) each H_i is almost distributed like G_k, in the sense that monotone properties of G_k transfer to H_i; (b) each H_i is rainbow, i.e., each edge is painted in a different colour. Since the typical vertex of G_k has degree 2k, and since the minimum degree of G(p,kn) is delta(G)p, this result is asymptotically optimal. Let G be a graph on n vertices and let k,c be fixed positive integers. The random subgraph G_k of G is obtained by letting each vertex of G pick k neighbours uniformly at random from its neighbourhood in G ("k-out"). On the other hand, the edge-coloured random subgraph G(p,c) is obtained by keeping each edge independently with probability p, and then colouring each edge randomly with a color from the set {1,...,c}.

Information for students and suggested topics for student talks