The positive bipartite MaxLA proportion conjecture for free trees

From papers

Let nn be the number of vertices, let Tn\mathcal{T}_n be the set of all free nn-vertex trees, and let Mn\mathcal{M}_n be the set of those trees for which a maximal bipartite arrangement is also a maximum arrangement. Define

propbip(n)=MnTn.\operatorname{propbip}(n)=\frac{|\mathcal{M}_n|}{|\mathcal{T}_n|}.

Weak bipartition conjecture. The same limiting assertion as in the strong bipartition conjecture holds with merely c>0c>0; equivalently, the asymptotic proportion is positive.

This is a weaker form of the preceding conjecture, intended to remain plausible even if the observed limiting value near 0.50.5 is not sustained. It would still imply that bipartite MaxLA solves a positive proportion of free trees for large nn; the paper gives empirical support but no proof.

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

Lluís Alemany-Puig, Juan Luis Esteban and Ramon Ferrer-i-Cancho, “Maximum Linear Arrangement: exact algorithms for specific classes of graphs and approximation algorithms for wide classes of graphs”, arXiv:2312.04487 (2026).

Solutions 0

No solutions have been posted yet.