Premium
Applications of the regularity lemma for uniform hypergraphs
Author(s) -
Rödl Vojtěch,
Skokan Jozef
Publication year - 2006
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.20108
Subject(s) - hypergraph , lemma (botany) , combinatorics , vertex (graph theory) , mathematics , struct , discrete mathematics , computer science , graph , ecology , poaceae , biology , programming language
In this article we discuss several combinatorial problems that can be addressed by the Regularity Method for hypergraphs. Based on the recent results of Nagle, Schacht, and the authors, we give here solutions to these problems. In particular, we prove the following: Let ℱ be a k‐uniform hypergraph on t vertices and suppose an n‐vertex k‐uniform hypergraph ℋ contains only o ( n t ) copies of ℱ. Then one can delete o ( n k ) edges of ℋ to make it ℱ ‐free . Similar results were recently obtained by W. T. Gowers. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006