- Series
- Combinatorics Seminar
- Time
- Friday, November 9, 2012 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Humberto Silva Naves – Math, UCLA – hsnaves@gmail.com
- Organizer
- Prasad Tetali
A variety of problems in extremal combinatorics can be stated as: For
two given graphs $H_1$ and $H_2$, if the number of induced copies of
$H_1$ in a $n$-vertex graph $G$ is known, what is the maximum or
minimum number of induced copies of $H_2$ in $G$? Numerous cases of
this question were studied by Tur\'an, Erd\H{o}s, Kruskal and Katona,
and several others. Tur\'an proved that the maximal edge density in
any graph with no cliques of size $r$ is attained by an $r-1$ partite
graph. Kruskal and Katona found that cliques, among all graphs,
maximize the number of induced copies of $K_s$ when $r