Regularization and asymmetric extremal numbers of subdivisions

Abstract

Given a real $\hat{I}¼\ge 1$, a graph $H$ is $\hat{I}¼$-almost-regular if $\hat{I}”(H)\le \hat{I}¼\hat{I}´(H)$. The celebrated regularization theorem of Erdős and Simonovits states that for every real $0<\epsilon <1$ there exists a real $\hat{I}¼=\hat{I}¼(\epsilon )$ such that every $n$-vertex graph $G$ with $\hat{I}\text{c◯}(n^{1+\epsilon })$ edges contains an $m$-vertex $\hat{I}¼$-almost-regular subgraph $H$ with $\hat{I}\text{c◯}(m^{1+\epsilon })$ edges for some $n^{\epsilon \frac{1-\epsilon }{1+\epsilon }}\le m\le n$. We develop an enhanced version of it in which the subgraph $H$ also has average degree at least $\hat{I}\text{c◯}(\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.

29 pages