Combinatorics Seminar

When: Sunday, April 1, 10am Where: Schreiber 309 Speaker: Noga Alon, Tel Aviv University Title: The Turan number of sparse spanning graphs

Abstract:

A classical result of Ore asserts that the maximum possible number of edges of a simple graph on n vertices which contains no Hamilton cycle is {{n-1} \choose 2} +1. I will show that this is also the maximum possible number of edges of a graph on n vertices which contains no copy of H, for any bounded degree n-vertex graph H with minimum degree 2, describe a more general statement, and show that an analogous statement for hypergraphs fails. This settles a problem of Glebov, Person and Weps. The proofs are surprisingly simple, serving as a gentle reminder that interesting results don't necessarily require hard solutions.

Joint work with Raphy Yuster