Premium
The quasi‐randomness of hypergraph cut properties
Author(s) -
Shapira Asaf,
Yuster Raphael
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20364
Subject(s) - hypergraph , combinatorics , randomness , mathematics , partition (number theory) , algebraic number , discrete mathematics , mathematical analysis , statistics
Let $\alpha_1,\ldots,\alpha_k$ satisfy $\sum_i\alpha_i=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,\ldots,A_k$ of sizes $\alpha_1n,\ldots,\alpha_kn$ , the number of edges intersecting $A_1,\ldots,A_k$ is (asymptotically) 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 $\alpha_1=\cdots=\alpha_k=1/k$ . This resolves an open problem raised in 1991 by Chung and Graham [J AMS 4 (1991), 151–196]. While hypergraphs satisfying the property corresponding to $\alpha_1=\cdots=\alpha_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. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011