Lower Bounds for Join/Union Expressions of Permutations and Hamiltonian Cycles
Baril, Couceiro and Lagerkvist asked how compactly two families can be written using only two operations: joining compatible pieces and taking the union of alternatives. The families are all orderings of n items (permutations), and all ways to visit n points in a single loop (Hamiltonian cycles). They conjectured that any such description must grow faster than any polynomial in n.This paper shows that both conjectures are true and that they follow from results already in the literature. The main route is Jerrum and Snir's 1982 lower bounds for computations that only add and multiply. A separate route goes through a known lower bound from knowledge compilation. The new work is the translation between these settings, and it gives exact numbers. For n of 3 or more, it gives explicit lower bounds on the size of tree-shaped descriptions. When a description may reuse its parts, it gives the exact fewest joins needed.If set difference is also allowed, Raz's theorem on multilinear formulas shows that tree-shaped descriptions still grow faster than any polynomial, and that descriptions which reuse parts need large depth. The same bounds apply to fixed min-plus (shortest-path style) programs, but not to algorithms that branch on their input.
Authors
- Dana Edwards
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-14
- DOI
- https://doi.org/10.5281/zenodo.24229219
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint