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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Lower Bounds for Join/Union Expressions of Permutations and Hamiltonian Cycles

Dana Edwards
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Lower Bounds for Join/Union Expressions of Permutations and Hamiltonian Cycles

Dana Edwards
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon