MATH Seminar

Title: Hereditary quasirandom properties of hypergraphs
Seminar: Combinatorics
Speaker: Domingos Dellamonica of Emory University
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2009-10-23 at 4:00PM
Venue: W306
Download Flyer
Abstract: Thomason, and Chung, Graham and Wilson were the first to investigate systematically properties of quasirandom graphs. They have stated several quite disparate graph properties -- such as having uniform edge distribution or containing a prescribed number of certain subgraphs -- and proved that these properties are equivalent in a deterministic sense. Simonovits and Sos introduced a hereditary property (which we call S) stating the following: for a small fixed graph L, a graph G on n vertices is said to have the property S if for every subset X of V(G), the number of labeled copies of L in G[X] (the subgraph of G induced by the vertices of (X) is given by $2^{-e(L)} \|X\|^{v(L)} + o(n^{v(L)})$. They have shown that S is equivalent to the other quasirandom properties. In this talk we give a natural extension of the result of Simonovits and Sos to k-uniform hypergraphs, answering a question of Conlon et al. Our approach yields an alternative, and perhaps simpler, proof of their theorem.