Combinatorics Seminar
When: Sunday, November 29, 10am
Where: Schreiber 309
Speaker: Raphy Yuster, University of Haifa
Title: The Quasi-Randomness of Cut Properties in Hypergraphs
Abstract:
We study quasi-random k-uniform hypergraphs, specifically,
hypergraphs whose edge distribution is similar to that of
random hypergraphs. We consider properties defined by the
number of edges of the hypergraph that cross a cut of
a given type. We obtain the following results:
1. Our first result is a precise characterization of the cut
properties that force a k-uniform hypergraph to be quasi-random.
This extends a result of Chung and Graham who obtained
a characterization of the cut properties that force a graph to be
quasi-random.
2. Let P be a hypergraph cut property that does not necessarily
force a hypergraph to be quasi-random. Our second result strengthens
the result of Chung and Graham by supplying a characterization of
the hypergraphs satisfying such a property.
The proofs combine probabilistic and algebraic arguments with
results from the theory of association schemes.
Joint work with Asaf Shapira.