Setwise Distinguishable Permutations
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.21298
curl -X POST /api/v1/records/arxiv/2606.21298/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.21298/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'