Hereditary quasirandom properties of hypergraphs

Abstract

Thomason and Chung, Graham and Wilson were the first to systematically investigate 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 Sós 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 set X ⊆ 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|^υ(L) + o(n ^υ(L)). They have shown that S is equivalent to the other quasirandom properties.

In this paper we give a natural extension of the result of Simonovits and Sós to k-uniform hypergraphs, answering a question of Conlon et al. Our approach also yields an alternative, and perhaps simpler, proof of one of their theorems.