Bipartite Extremal Numbers of Trees

Abstract

We study a restriction of the classical Erdős--Sós problem, the extremal number of trees, to the class of bipartite host graphs, both when only the order of the host is prescribed and when its two part-sizes are fixed. We give natural lower-bound constructions and formulate corresponding linear upper-bound conjectures. We apply a weighted variant of $k$-minimality to prove upper bounds for a broad family of trees including brooms, trees with part-sizes obeying certain inequalities, and all trees on at most seven vertices, resolving part of a problem of Caro, Patkós and Tuza up to additive constants. We also relate the fixed-part extremal number of a tree to the ordinary extremal number, and consider an oriented bipartite extremal function analogous to the Zarankiewicz function.

Disclosure

“opic, reviewing an earlier version of this manuscript, and giving detailed feedback. We note that Khormali independently investigated the same problem using a distinct approach after the majority of our work was completed. Declaration of generative AI and AI-assisted technologies in the manuscript preparation process During the preparation of this work the authors used ChatGPT-5.6 Sol in order to improve readability of the manuscript and put references in the required format. After usin”

PDF page 12

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T19:18:58.491578Z

Structural counts