{"id":"arxiv/2606.21298","url":"https://arxiv.org/abs/2606.21298","tags":["cs.DM","cs.CC","math.CO"],"score":0,"title":"Setwise Distinguishable Permutations","domain":"cs.DM","source":"arxiv","authors":["Ishay Haviv"],"reviews":0,"subject":"cs.DM","summary":"A family of permutations of $[n]$ is called setwise distinguishable if for every permutation in the family there exists a subset of $[n]$ whose image under this permutation differs from its image under any other permutation in the family. We prove that there exists a setwise distinguishable family of $2^{(2-o(1)) \\cdot n}$ permutations of $[n]$. The result is optimal up to the $o(1)$ term in the exponent and is achieved through an explicit construction. As an application, we obtain nearly tight conditional lower bounds on the kernelization complexity of graph coloring problems parameterized…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-19","reactions":{}}