On the generalized Turán number of complete bipartite graphs
2026-06-08 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a problem in graph theory about how many small patterns (copies of one graph, F) can appear inside a large graph that avoids another pattern (H). They focus on special cases where F and H are complete bipartite graphs with certain sizes and show the maximum number grows roughly like n to the power s, where n is the number of vertices. They also prove a wider result that for any graph F with at least one edge, you can find infinitely many exponent values r such that the maximum number of F copies in some H-free graph grows like n to the r. Their work answers some previously open questions proposed by another researcher named Spiro.
generalized Turán numbergraph theorycomplete bipartite graphextremal graph theoryn verticespattern avoidanceasymptotic growthcopy countingSpiro conjectureex(n,F,H)
Authors
Oliver Janzer, Sean Longbrake, Liana Yepremyan
Abstract
For graphs $F$ and $H$, the generalized Turán number $\mathrm{ex}(n,F,H)$ denotes the maximum number of copies of $F$ in an $H$-free graph on $n$ vertices. We prove that if $s\in \{2,3\}$, $s< a\leq b$ and $t$ is sufficiently large, then $\mathrm{ex}(n,K_{a,b},K_{s,t})=Θ(n^s)$. The $s=2$, $a=b=3$ case of this result answers a question of Spiro. Proving another conjecture of Spiro, we show that for every graph $F$ with at least one edge, there exist infinitely many real numbers $r$ such that $\mathrm{ex}(n,F,H)=Θ(n^r)$ holds for some graph $H$.