Quasirandomness in hypergraphs
A graph G is called quasirandom if it possesses typical properties of the corresponding random graph G(n,p) with the same edge density as G. A well-known theorem of Chung, Graham and Wilson states that, in fact, many such ‘typical’ properties are asymptotically equivalent and, thus, a graph G posses...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2017
|
| _version_ | 1826286133518008320 |
|---|---|
| author | Aigner-Horev, E Conlon, D Hàn, H Person, Y Schacht, M |
| author_facet | Aigner-Horev, E Conlon, D Hàn, H Person, Y Schacht, M |
| author_sort | Aigner-Horev, E |
| collection | OXFORD |
| description | A graph G is called quasirandom if it possesses typical properties of the corresponding random graph G(n,p) with the same edge density as G. A well-known theorem of Chung, Graham and Wilson states that, in fact, many such ‘typical’ properties are asymptotically equivalent and, thus, a graph G possessing one property immediately satisfies the others. In recent years, more quasirandom graph properties have been found and extensions to hypergraphs have been explored. For the latter, however, there exist several distinct notions of quasirandomness. A complete description of these notions has been provided recently by Towsner, who proved several central equivalences using an analytic framework. The purpose of this paper is to give short purely combinatorial proofs of most of Towsner's results. |
| first_indexed | 2024-03-07T01:39:15Z |
| format | Journal article |
| id | oxford-uuid:964937f4-93e2-47b0-9619-629e86f6f6d2 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:39:15Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:964937f4-93e2-47b0-9619-629e86f6f6d22022-03-26T23:51:51ZQuasirandomness in hypergraphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:964937f4-93e2-47b0-9619-629e86f6f6d2Symplectic Elements at OxfordElsevier2017Aigner-Horev, EConlon, DHàn, HPerson, YSchacht, MA graph G is called quasirandom if it possesses typical properties of the corresponding random graph G(n,p) with the same edge density as G. A well-known theorem of Chung, Graham and Wilson states that, in fact, many such ‘typical’ properties are asymptotically equivalent and, thus, a graph G possessing one property immediately satisfies the others. In recent years, more quasirandom graph properties have been found and extensions to hypergraphs have been explored. For the latter, however, there exist several distinct notions of quasirandomness. A complete description of these notions has been provided recently by Towsner, who proved several central equivalences using an analytic framework. The purpose of this paper is to give short purely combinatorial proofs of most of Towsner's results. |
| spellingShingle | Aigner-Horev, E Conlon, D Hàn, H Person, Y Schacht, M Quasirandomness in hypergraphs |
| title | Quasirandomness in hypergraphs |
| title_full | Quasirandomness in hypergraphs |
| title_fullStr | Quasirandomness in hypergraphs |
| title_full_unstemmed | Quasirandomness in hypergraphs |
| title_short | Quasirandomness in hypergraphs |
| title_sort | quasirandomness in hypergraphs |
| work_keys_str_mv | AT aignerhoreve quasirandomnessinhypergraphs AT conlond quasirandomnessinhypergraphs AT hanh quasirandomnessinhypergraphs AT persony quasirandomnessinhypergraphs AT schachtm quasirandomnessinhypergraphs |