- Series
- Combinatorics Seminar
- Time
- Friday, March 5, 2010 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Asaf Shapira – School of Mathematics, Georgia Tech
- Organizer
- Prasad Tetali

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 number of 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