Optimal chain density, entropy, and space-time tradeoffs for the TSP

Abstract

We nearly settle a natural extremal question about set systems over $[n]$: the tradeoff between the {size} (number of sets) and the number of {full chains}. This question was initially raised by Johnson, Leader, and Russell [Combin.~Probab.~Comp., 2015] as a counterpart to Sperner-type results in combinatorics. Recently, a framework introduced by Ameli, Nederlof, and Wang, and independently by Dallant and Kozma [FOCS 2026] linked this question to the space- and time-complexity of Bellman-Held-Karp-style dynamic programming algorithms for permutation problems such as the traveling salesman (TSP). Precisely, they showed that a space-time product $γ^{n+o(n)}$ is feasible for the TSP, whenever a set system of (normalized) size $S$ and chain density $D$ exists, with ${\hat{I}}^3=S^2/D$. In this paper we show an essentially {optimal} bound of ${\hat{I}}^3\approx 3.1819$ for this quantity, closing the gap between the previous best lower and upper bounds of ${\hat{I}}^3\ge 3.015$ and ${\hat{I}}^3\le 3.572$ respectively. This implies a TSP algorithm with space-time product $O(3.1819^n)$ for input size $n$, as well as a limit to further improvements in this broad framework. More generally, we can obtain close to optimal values $D$ for any feasible value $S$, effectively settling the question of the number of full chains at every size. The crucial step towards our results is casting the extremal combinatorics question as an {information~vs.~entropy} tradeoff involving two random variables. This reformulation {exactly} captures the optimal tradeoff for the combinatorial problem, leading to a framework in which primal-dual certificates can be derived, proving rigorous upper and lower bounds on ${\hat{I}}^3$. We also give a further application of our techniques, improving a bound of Duffus, Sands, and Winkler on the minimum size of fibres in the Boolean lattice.

Topics & keywords