Journal article icon

Journal article

Hereditary quasirandomness without regularity

Abstract:

A result of Simonovits and Sós states that for any fixed graph H and any ∊ > 0 there exists δ > 0 such that if G is an n-vertex graph with the property that every S ⊆ V (G) contains p^e(H) |S|^v(H) ± δn^v(H) labeled copies of H, then G is quasirandom in the sense that every S ⊆ V (G) contains ½p|S|^2 ± ∊n^2 edges. The original proof of this result makes heavy use of the regularity lemma, resulting in a bound on δ^-1 which is a tower of twos of height polynomial in ∊^-1. We give an alter...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1017/S0305004116001055

Authors


More by this author
Institution:
University of Oxford
Oxford college:
Wadham College
Role:
Author
More from this funder
Name:
European Research Council
Funding agency for:
Conlon, D
Grant:
676632
More from this funder
Name:
Royal Society
Funding agency for:
Conlon, D
Grant:
676632
More from this funder
Name:
Alfred P. Sloan Foundation
Grant:
Fellowship
More from this funder
Name:
Swiss National Science Foundation
Grant:
200021-149111
More from this funder
Name:
National Science Foundation
Grant:
DMS-1352121
Publisher:
Cambridge University Press
Journal:
Mathematical Proceedings of the Cambridge Philosophical Society More from this journal
Publication date:
2017-01-01
Acceptance date:
2016-11-21
DOI:
EISSN:
1469-8064
ISSN:
0305-0041
Pubs id:
pubs:661129
UUID:
uuid:fcf47b56-aecf-41ce-8e70-ff04c1f59e73
Local pid:
pubs:661129
Source identifiers:
661129
Deposit date:
2016-11-22

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP