Given a real $\mu\geq 1$, a graph $H$ is $\mu$-almost-regular if $\Delta(H)\leq \mu \delta(H)$. The celebrated regularization theorem of Erd\H{ o}s and Simonovits states that for every real $0<\varepsilon<1$ there exists a real $\mu=\mu(\varepsilon)$ such that every $n$-vertex graph $G$ with $\Omega(n^{ 1+\varepsilon})$ edges contains an $m$-vertex $\mu$-almost-regular subgraph $H$ with $\Omega(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 $\Omega(\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.
Categories: math.CO