Published 2018
| Submitted
Journal Article
Open
Rational exponents in extremal graph theory
- Creators
- Bukh, Boris
-
Conlon, David
Abstract
Given a family of graphs ℌ, the extremal number ex(n, ℌ) is the largest m for which there exists a graph with n vertices and m edges containing no graph from the family ℌ as a subgraph. We show that for every rational number r between 1 and 2, there is a family of graphs ℌ_r such that ex (n, ℌ_r) = Θ(n^r). This solves a longstanding problem in the area of extremal graph theory.
Additional Information
© 2018 European Mathematical Society. Published online: 2018-05-22. Bukh research supported in part by a Sloan Research Fellowship, NSF grant DMS-1301548, and NSF CAREER grant DMS-1555149. Conlon research supported by a Royal Society University Research Fellowship and ERC Starting Grant 676632. We would like to thank Jacques Verstraete for interesting discussions relating to the topic of this paper. We would also like to thank an anonymous referee and Lisa Sauermann for a number of useful comments and corrections.Attached Files
Submitted - 1506.06406.pdf
Files
1506.06406.pdf
Files
(183.4 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:320401991be7dfde8f8ccdf171f12ab5
|
183.4 kB | Preview Download |
Additional details
- Eprint ID
- 97838
- Resolver ID
- CaltechAUTHORS:20190812-163000355
- Alfred P. Sloan Foundation
- DMS-1301548
- NSF
- DMS-1555149
- NSF
- Royal Society
- 676632
- European Research Council (ERC)
- Created
-
2019-08-16Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field