Cardinality of Balls in Permutation Spaces

2013/02/28 by Liviu P. Dinu, Dinu, Liviu P., Catalin Zara +1
Computer Science · Engineering · Mathematics · #05A05 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems #math.CO #msc:05A05

paper · pdf · doi:10.48550/arxiv.1303.0016

arxiv created 2013/02/28 · openalex publication_date 2013/02/28 · arxiv updated 2013/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a right invariant distance on a permutation space S_n we give a sufficient condition for the cardinality of a ball of radius R to grow polynomially in n for fixed R. For the distance ℓ₁ we show that for an integer k the cardinality of a sphere of radius 2k in S_n (for n \geqslant k) is a polynomial of degree k in n and determine the high degree terms of this polynomial.

Related

• A generalization of Gerzon's bound on spherical s-distance sets
• New upper bound for the cardinalities of s-distance sets on the unit sphere
• VC-dimension of Salem sets over finite fields
• Asymptotic structures of cardinals
• Selected topics from the theory of intersections of balls