2018
Dec
24

# Combinatorics: Benny Sudakov (ETH) "Subgraph statistics"

11:00am to 1:00pm

## Location:

Rothberg CS room B500, Safra campus, Givat Ram

Speaker: Benny Sudakov, ETH, Zurich

Title: Subgraph statistics

Abstract:

Consider integers $k,\ell$ such that $0\le \ell \le \binom{k}2$. Given

a large graph $G$, what is the fraction of $k$-vertex

subsets of $G$ which span exactly $\ell$ edges? When $G$ is empty or

complete, and $\ell$ is zero or $\binom k 2$,

this fraction can be exactly 1. On the other hand if $\ell$ is not one

these extreme values, then by Ramsey's theorem, this

fraction is strictly smaller than 1.

Title: Subgraph statistics

Abstract:

Consider integers $k,\ell$ such that $0\le \ell \le \binom{k}2$. Given

a large graph $G$, what is the fraction of $k$-vertex

subsets of $G$ which span exactly $\ell$ edges? When $G$ is empty or

complete, and $\ell$ is zero or $\binom k 2$,

this fraction can be exactly 1. On the other hand if $\ell$ is not one

these extreme values, then by Ramsey's theorem, this

fraction is strictly smaller than 1.