## 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, April 26, 2018, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Michael Krivelevich (Tel Aviv University)

## Getting a prescribed number of edges in a subgraph is polynomially unlikely

Let k, l be positive integers with 0 ≤ l ≤ \binom{k}{2}, and let G be a graph of n vertices, for n ≫ k,l. How many k-subsets of G span exactly l edges? In other words, what is the probability that a random k-subset of V(G) spans exactly l edges? This probability can obviously be 1 for l=0, and is easily seen to be possibly as high as an absolute constant for some values of l linear in k. However, we show that for the values of l quadratically in k away from the boundaries 0,\binom{k}{2}, the probability in question is polynomially small in k.

A joint work with Noga Alon, Dan Hefetz and Mykhaylo Tyomkyn.

Information for students and suggested topics for student talks