Abstract: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 by the vertex-deletion distance to split graphs. This improves a result of Jansen and Kratsch (Inf. Comput., 2013).
From: Ishay Haviv [view email]
[v1]
Fri, 19 Jun 2026 10:21:09 UTC (16 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。