Bipartite Turán Numbers of Trees and Star Forests

@misc{khormali2026bipartite,
  title = {{Bipartite Turán Numbers of Trees and Star Forests}},
  author = {Omid Khormali},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.01873},
  eprint = {2608.01873},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.01873},
}

TY  - UNPB
TI  - Bipartite Turán Numbers of Trees and Star Forests
AU  - Omid Khormali
PY  - 2026
DA  - 2026/09/27
PB  - arXiv
DO  - 10.48550/arxiv.2608.01873
UR  - https://arxiv.org/abs/2608.01873
AB  - The bipartite Turán number of a graph H, denoted ex(m, n; H), is the maximum number of edges in any H-free bipartite graph G = (A, B; E) with parts of size |A| = m and |B| = n. We study this problem for two families. For a tree T = T(r, s) with parts R and S of sizes |R| = r ≤ s = |S|, we prove (r − 1) n ≤ ex(m, n; T(r, s)) ≤ (r − 1) n + C(m,r,s) for n sufficiently large compared to m, r, and s, where C(m,r,s) does not depend on n, determining the leading-order term exactly (with the star case r = 1 solved with an exact formula). For a star forest F = ⋃_i=1^k S_d_i with d_1 ≥ ⋯ ≥ d_k, we determine the exact value ex(m, n; F) = (k − 1) n + (d_k − 1)(m − k + 1) for n sufficiently large, and characterize the unique extremal graph.
ER  -