Name
Abstract | ||
|---|---|---|
Extending the Szemeredi Regularity Lemma for graphs, P. Frankl and V. Rodl (14) established a 3-graph Regularity Lemma guaranteeing that all large triple systems Gn admit bounded partitions of their edge sets, most classes of which consist of regularly distributed triples. Many applications of this lemma require a companion Counting Lemma (30), allowing one to find and enumerate subhypergraphs of a given isomorphism type in a "dense and regu- lar" environment created by the 3-graph Regularity Lemma. Combined applications of these lemmas are known as the 3-graph Regularity Method. In this paper, we provide an algorithmic version of the 3-graph Regularity Lemma which, as we show, is compatible with a Counting Lemma. We also discuss some applications. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/060652385 | SIAM Journal on Computing |
Keywords | Field | DocType |
algorithmic regularity lemma for hypergraphs,counting lemma for hypergraphs | Aubin–Lions lemma,Discrete mathematics,Combinatorics,Handshaking lemma,Partition regularity,Teichmüller–Tukey lemma,Zorn's lemma,Szemerédi regularity lemma,Pumping lemma for context-free languages,Mathematics,Lemma (mathematics) | Journal |
Volume | Issue | ISSN |
37 | 6 | 0097-5397 |
Citations | PageRank | References |
12 | 1.56 | 31 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| P. E. Haxell | 1 | 212 | 26.40 |
| Brendan Nagle | 2 | 207 | 23.53 |
| Vojtech Rödl | 3 | 877 | 139.49 |