|国家预印本平台
首页|Bipartite Turán numbers via edge-gluing

Bipartite Turán numbers via edge-gluing

Bipartite Turán numbers via edge-gluing

来源:Arxiv_logoArxiv
英文摘要

In 1984, Erdős and Simonovits asked the following: given a bipartite graph $H$, do there exist constants $0 \leq α< 1$ and $β, C > 0$ such that any graph $G$ on $n$ vertices and $pn^2\geq C n^{1+ α}$ edges contains at least $βn^{\mathrm{v}(H)} p^{\mathrm{e}(H)}$ copies of $H$? We show that edge-gluing preserves the satisfiability of this conjecture under some mild symmetry conditions. Namely, if two graphs $H_1$ and $H_2$ satisfy this conjecture, and if furthermore, gluing them along a fixed edge produces a unique graph then the resulting graph satisfies the conjecture as well. We also show that if $H$ satisfies the conjecture then if we glue several copies of (labeled) $H$ along the same labeled copy of a subforest of $H$ then the resulting graph also satisfies the conjecture. We also show that Zarankiewicz numbers are additive in the order of magnitude under gluing edges. Indeed, for a (signed) bipartite graph $H$ with parts coloured $+$ and $-$, recall $z(m,n, H)$ is the maximum number of edges in a signed bipartite graph $G$ with $+$ side being of size $m$ and $-$ side being of size $n$ such that $G$ does not contain a copy of $H$ with $+$ side embedded in the $+$ side of $G$. We show that for any two (signed) bipartite graphs $H_1$ and $H_2$ if we glue them along an edge preserving the sign of the edge then the resulting graph $H$ satisfies $z(m,n, H) = Θ(z(m,n, H_1) + z(m,n, H_2))$.

Zihao Jin、Sean Longbrake、Liana Yepremyan

数学

Zihao Jin,Sean Longbrake,Liana Yepremyan.Bipartite Turán numbers via edge-gluing[EB/OL].(2025-07-22)[2025-08-10].https://arxiv.org/abs/2507.16804.点此复制

评论