{"id":"arxiv/2607.11311","url":"https://arxiv.org/abs/2607.11311","tags":["cs.DS","math.CO"],"score":0,"title":"Optimal chain density, entropy, and space-time tradeoffs for the TSP","domain":"cs.DS","source":"arxiv","authors":["Alexandr Andoni","Justin Dallant","László Kozma","Hantao Yu"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}