The Quasi-Randomness of Hypergraph Cut Properties

Details The Quasi-Randomness of Hypergraph Cut Properties The Quasi-Randomness of Hypergraph Cut Properties

2010-01-31

arxiv.org/abs/1002.0149v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Quasi-Randomness of Hypergraph Cut Properties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Quasi-Randomness of Hypergraph Cut Properties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Quasi-Randomness of Hypergraph Cut Properties will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-347497