Back to Search
Start Over
Rational exponents in extremal graph theory
- Publication Year :
- 2015
-
Abstract
- Given a family of graphs $\mathcal{H}$, the extremal number $\textrm{ex}(n, \mathcal{H})$ is the largest $m$ for which there exists a graph with $n$ vertices and $m$ edges containing no graph from the family $\mathcal{H}$ as a subgraph. We show that for every rational number $r$ between $1$ and $2$, there is a family of graphs $\mathcal{H}_r$ such that $\textrm{ex}(n, \mathcal{H}_r) = \Theta(n^r)$. This solves a longstanding problem in the area of extremal graph theory.<br />Comment: 11 pages. arXiv admin note: text overlap with arXiv:1411.0856
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1506.06406
- Document Type :
- Working Paper