The left LBS-tree edge-activity conjecture

A left LBS tree is a local binary search tree whose root has no right child; that is, it is a planar rooted tree in which each vertex has at most a left child and a right child, with left child smaller and right child larger than the vertex. For 0kn10\leq k\leq n-1, compare the numbers of such trees having specified edge types.

Left LBS-tree edge-activity conjecture. For 0kn10\leq k\leq n-1, the number of left LBS trees with kk edges of the form (i+1,i)(i+1,i) is equal to the number of left LBS trees with kk edges of the form (n,i)(n,i).

This conjecture was motivated by the Athanasiadis question and by the correspondence between regions of the Linial arrangement, LBS trees, and NBC trees. The authors report computer evidence but leave the claimed equality as a conjecture.

Sources & referencesView supporting material

Primary source

Rigoberto Flórez and David Forge, “Activity from matroids to rooted trees and beyond”, arXiv:2209.03446 (2023).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.