The positive bipartite MaxLA proportion conjecture for free trees
The positive bipartite MaxLA proportion conjecture for free trees
Let be the number of vertices, let be the set of all free -vertex trees, and let be the set of those trees for which a maximal bipartite arrangement is also a maximum arrangement. Define
Weak bipartition conjecture. The same limiting assertion as in the strong bipartition conjecture holds with merely ; 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 is not sustained. It would still imply that bipartite MaxLA solves a positive proportion of free trees for large ; 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
Sign in to submit a solution.
No solutions have been posted yet.