Back to Search
Start Over
More on the Extremal Number of Subdivisions
- Source :
- Combinatorica. 41:465-494
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- Given a graph $H$, the extremal number $\mathrm{ex}(n,H)$ is the largest number of edges in an $H$-free graph on $n$ vertices. We make progress on a number of conjectures about the extremal number of bipartite graphs. First, writing $K'_{s,t}$ for the subdivision of the bipartite graph $K_{s,t}$, we show that $\mathrm{ex}(n, K'_{s,t}) = O(n^{3/2 - \frac{1}{2s}})$. This proves a conjecture of Kang, Kim and Liu and is tight up to the implied constant for $t$ sufficiently large in terms of $s$. Second, for any integers $s, k \geq 1$, we show that $\mathrm{ex}(n, L) = \Theta(n^{1 + \frac{s}{sk+1}})$ for a particular graph $L$ depending on $s$ and $k$, answering another question of Kang, Kim and Liu. This result touches upon an old conjecture of Erd\H{o}s and Simonovits, which asserts that every rational number $r \in (1,2)$ is realisable in the sense that $\mathrm{ex}(n,H) = \Theta(n^r)$ for some appropriate graph $H$, giving infinitely many new realisable exponents and implying that $1 + 1/k$ is a limit point of realisable exponents for all $k \geq 1$. Writing $H^k$ for the $k$-subdivision of a graph $H$, this result also implies that for any bipartite graph $H$ and any $k$, there exists $\delta > 0$ such that $\mathrm{ex}(n,H^{k-1}) = O(n^{1 + 1/k - \delta})$, partially resolving a question of Conlon and Lee. Third, extending a recent result of Conlon and Lee, we show that any bipartite graph $H$ with maximum degree $r$ on one side which does not contain $C_4$ as a subgraph satisfies $\mathrm{ex}(n, H) = o(n^{2 - 1/r})$.<br />Comment: 21 pages
- Subjects :
- Rational number
Conjecture
010102 general mathematics
0102 computer and information sciences
16. Peace & justice
01 natural sciences
Prime (order theory)
Combinatorics
Computational Mathematics
010201 computation theory & mathematics
Limit point
FOS: Mathematics
Bipartite graph
Graph (abstract data type)
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Combinatorics (math.CO)
0101 mathematics
Constant (mathematics)
Mathematics
Subjects
Details
- ISSN :
- 14396912 and 02099683
- Volume :
- 41
- Database :
- OpenAIRE
- Journal :
- Combinatorica
- Accession number :
- edsair.doi.dedup.....30bfd493079be57c4f4db8f9d8994739