Title: Induced subgraphs with distinct size or order
Speaker: Alexander Kostochka, University of Illinois at Urbana-Champaign
When: December 6, 16:30-17:30
Where: Wean Hall 5302
For a graph G, let \phi(G) denote the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G. Let hom(G) denote the maximum number of vertices in an induced clique or an induced independent set in G. An n-vertex graph is c-Ramsey, if hom(G) \leq c log n. Erdos, Faudree and Sos conjectured that for every positive constant c, there is a positive constant b = b(c) such that if G is a c-Ramsey graph on n vertices, then \phi(G) ≥ bn^{5/2}. They also proved the weaker lower bound Ω(n^{3/2}).
We prove the bound Ω(n^2) for the wider class of n-vertex graphs with average degree at least 0.001n and at most 0.999n. The order of magnitude of the bound cannot be improved in this class as shown, for example, by the complete bipartite n-vertex graphs.
This is joint work with N. Alon.
