May 3, 1:00pm, Wean 8220

Asaf Shapira, Georgia Tech

The Quasi-Randomness of Hypergraph Cut Properties

Asaf Shapira, Georgia Tech

The Quasi-Randomness of Hypergraph Cut Properties

Abstract:

Let a_1,...,a_k satisfy a_1+...+a_k=1 and suppose a k-uniform
hypergraph on n vertices satisfies the following property; in any
partition of its vertices into k sets A_1,...,A_k of sizes
a_1*n,...,a_k*n, the numberof edges intersecting A_1,...,A_k is
the number one would expect to find in a random k-uniform
hypergraph. Can we then infer that H is quasi-random? We show
that the answer is negative if and only if a_1=...=a_k=1/k. This
resolves an open problem raised in 1991 by Chung and Graham
[J. AMS '91].

While hypergraphs satisfying the property corresponding to a_1=...=a_k=1/k are not necessarily quasi-random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi-random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of Association Schemes.

Joint work with Raphy Yuster