Bipartite Turán problems via graph gluing

Abstract

For graphs $H_1$ and $H_2$, if we glue them by identifying a given pair of vertices $u\in V(H_1)$ and $v\in V(H_2)$, what is the extremal number of the resulting graph $H_1^u\odot H_2^v$? In this paper, we study this problem and show that interestingly it is equivalent to an old question of Erdős and Simonovits on the Zarankiewicz problem. When $H_1,H_2$ are copies of a same bipartite graph $H$ and $u,v$ come from a same part, we prove that $\mathrm{ex}(n,H_1^u\odot H_2^v)=\hat{I}˜(\mathrm{ex}(n,H))$. As a corollary, we provide a short self-contained disproof of a conjecture of Erdős, which was recently disproved by Janzer.

11 pages, 3 figures