Georgia Institute of Technology College of Sciences

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