Regularization and asymmetric extremal numbers of subdivisions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918093496778752 |
|---|---|
| author | Jiang, Tao Longbrake, Sean |
| author_facet | Jiang, Tao Longbrake, Sean |
| contents | Given a real $μ\geq 1$, a graph $H$ is $μ$-almost-regular if $Δ(H)\leq μδ(H)$. The celebrated regularization theorem of Erdős and Simonovits states that for every real $0<\varepsilon<1$ there exists a real $μ=μ(\varepsilon)$ such that every $n$-vertex graph $G$ with $Ω(n^{1+\varepsilon})$ edges contains an $m$-vertex $μ$-almost-regular subgraph $H$ with $Ω(m^{1+\varepsilon})$ edges for some $n^{\varepsilon\frac{1-\varepsilon}{1+\varepsilon}}\leq m\leq n$. We develop an enhanced version of it in which the subgraph $H$ also has average degree at least $Ω(\frac{d(G)}{\log n})$, where $d(G)$ is the average degree of $G$. We then give a bipartite analogue of the enhanced regularization theorem.
Using the bipartite regularization theorem, we establish upper bounds on the maximum number of edges in a bipartite graph with part sizes $m$ and $n$ that does not contain a $2k$-subdivision of $K_{s,t}$ or $2k$-multi-subdivisions of $K_p$, thus extending the corresponding work of Janzer to the bipartite setting for even subdivisions. We show these upper bounds are tight up to a constant factor for infinitely many pairs $(m,n)$. The problem for estimating the maximum number of edges in a bipartite graph with part sizes $m$ and $n$ that does not contain a $(2k+1)$-subdivision of $K_{s,t}$ remains open. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03261 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Regularization and asymmetric extremal numbers of subdivisions Jiang, Tao Longbrake, Sean Combinatorics 05C35 Given a real $μ\geq 1$, a graph $H$ is $μ$-almost-regular if $Δ(H)\leq μδ(H)$. The celebrated regularization theorem of Erdős and Simonovits states that for every real $0<\varepsilon<1$ there exists a real $μ=μ(\varepsilon)$ such that every $n$-vertex graph $G$ with $Ω(n^{1+\varepsilon})$ edges contains an $m$-vertex $μ$-almost-regular subgraph $H$ with $Ω(m^{1+\varepsilon})$ edges for some $n^{\varepsilon\frac{1-\varepsilon}{1+\varepsilon}}\leq m\leq n$. We develop an enhanced version of it in which the subgraph $H$ also has average degree at least $Ω(\frac{d(G)}{\log n})$, where $d(G)$ is the average degree of $G$. We then give a bipartite analogue of the enhanced regularization theorem. Using the bipartite regularization theorem, we establish upper bounds on the maximum number of edges in a bipartite graph with part sizes $m$ and $n$ that does not contain a $2k$-subdivision of $K_{s,t}$ or $2k$-multi-subdivisions of $K_p$, thus extending the corresponding work of Janzer to the bipartite setting for even subdivisions. We show these upper bounds are tight up to a constant factor for infinitely many pairs $(m,n)$. The problem for estimating the maximum number of edges in a bipartite graph with part sizes $m$ and $n$ that does not contain a $(2k+1)$-subdivision of $K_{s,t}$ remains open. |
| title | Regularization and asymmetric extremal numbers of subdivisions |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2507.03261 |