Regularity, uniformity, and quasirandomness

摘要

Graph theory is the appropriate language for discussing binary relations on objects. Results in graph theory have numerous applications in biology, chemistry, computer science, and physics. In cases of multiple relations, instead of binary relations more general structures known as hypergraphs are the right tools. However, it turns out that because of their extremely complex structure, hyper-graphs are very difficult to deal with. As with number theory, there are questions about hypergraphs that are easy to state but very difficult to answer. In this issue of PNAS, Roedl et al. extend a powerful tool, the regularity lemma, from graphs to hypergraphs.