Fall 2013

Local Combinatorics, Or: What To Do With All Those Gigantic Graphs?

Thursday, Aug. 29, 2013 1:45 pm2:30 pm

Add to Calendar

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.