Erdős–Sós order-form conjecture for bipartite host graphs

From papers

Every tree is bipartite. Write Ta,b=(A,B)T_{a,b}=(A,B) when the two parts of TT satisfy

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

For a bipartite graph HH, let exbip(N;H)\operatorname{ex}_{\mathrm{bip}}(N;H) be the maximum number of edges in an HH-free bipartite graph on NN vertices. Order-form conjecture. For every tree Ta,bT_{a,b},

exbip(N;Ta,b){12(a1)Nif a2b1,(b1)Nif a2b1.\operatorname{ex}_{\mathrm{bip}}(N;T_{a,b})\leq\begin{cases} \frac12(a-1)N& \text{if}\ a\geq2b-1,\\ (b-1)N& \text{if}\ a\leq2b-1. \end{cases}

The claim is motivated by two natural lower-bound constructions, whose comparison suggests a transition at a=2b1a=2b-1. Its resolution is not supplied in the source material.

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.