Abstract
Let H, G be graphs on k (small) and n (large) vertices respectively. We denote by p(H,G) the probability that a randomly chosen set of k vertices in G spans a subgraph isomorphic to H. For fixed k, the vector (p(H,G) | H is a k-vertex graph) is called the k-profile of G.
Q1: What do the k-profiles of large graphs look like? ("Local graph theory")
Q2: Given information about G's k-profile, what conclusions can we draw? (Local-global graph theory).
Similar questions can be asked concerning numerous other combinatorial objects such as tournaments, permutations etc. In this talk I will present some of what is already known in this area as well as the many intriguing questions that are still open.
The talk covers joint work with: Chaim Even Zohar, Hao Huang, Avraham Morgenstern, Humberto Naves, Yuval Peled, Benny Sudakov.