pith. sign in

arxiv: 2501.12953 · v3 · pith:WIAMX5S5new · submitted 2025-01-22 · 🧮 math.CO

Bipartite Tur\'an problems via graph gluing

classification 🧮 math.CO
keywords graphbipartiteodotoperatornameproblemsamebiglbigr
0
0 comments X
read the original 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\H{o}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 $\operatorname{ex}(n, H_1^u \odot H_2^v) = \Theta \bigl( \operatorname{ex}(n, H) \bigr)$. As a corollary, we provide a short self-contained disproof of a conjecture of Erd\H{o}s, which was recently disproved by Janzer.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.