Erdős–Sós fixed-part conjecture for bipartite host graphs

From papers

Let Ta,b=(A,B)T_{a,b}=(A,B) be a tree whose bipartition satisfies

A=a,B=b,ab.|A|=a,\qquad |B|=b,\qquad a\geq b.

For a bipartite graph HH, let exbip(m,n;H)\operatorname{ex}_{\mathrm{bip}}(m,n;H) be the maximum number of edges in an HH-free bipartite graph with part-sizes mm and nn. Fixed-part conjecture. For every tree Ta,bT_{a,b} and all mb1m\geq b-1, na1n\geq a-1,

exbip(m,n;Ta,b)(b1)n+{(ab)mif a2b1,(b1)mif a2b1.\operatorname{ex}_{\mathrm{bip}}(m,n;T_{a,b})\leq(b-1)n+\begin{cases} (a-b)m&\text{if}\ a\geq2b-1,\\ (b-1)m&\text{if}\ a\leq2b-1. \end{cases}

This refines the order-form problem by prescribing both part-sizes. The source motivates it through lower-bound constructions, but provides no resolution status for the conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Lucas Waite and Nuh Aydin, “Bipartite Extremal Numbers of Trees”, arXiv:2607.29579 (2026).

Solutions 0

No solutions have been posted yet.