2026/07/31 by Lucas Waite, Nuh Aydin
Mathematics · #math.CO #msc:05C05 #msc:05C35
13 pages, no figures
arxiv created 2026/07/31 · arxiv published 2026/07/31 · arxiv updated 2026/08/03
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 differing by at most one, and all trees on at most 7 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.