Transposition Distance between two permutations.

Question

I'm working on the following problem.

Suppose that $A \subseteq S_n$ is a subset of at least $n!/2$ permutations, and let $A(t)$ be the set of permutations that can be obtained from starting at some element of $A$, and then applying at most $t$ transpositions. Prove that there is some absolute constant $c > 0$ so that $$A(t) \geq (1-e^{-ct^2/n})n!$$

My first thoughts are that I want to use the Talagrand concentration theorem, but for that I need to write $S_n$ as a product space. Since I can write any permutation $\sigma$ as a product of transpositions, I thought maybe I could think of $S_n$ as the product of $m = \binom{n}{2}$ independent identically distributed random variables taking values either $0$ or $1$, and a vector of $0$'s and $1$'s would correspond to whether or not the indicated transposition was in a minimal representation of $\sigma$ as a product of transpositions.

This has some problems however. First of all, I doubt this is well defined since there are several ways we can write $\sigma$ as a product of transpositions. The second problem is that order matters, since $(12)(23)$ and $(23)(12)$ give different permutations.

Is there any way I can use Talagrand concentration to approach this problem, probably with a different setup? Does anyone have any thoughts on a different approach?

Answer 1

Concentration of measure on the permutation group (with respect to Hamming distance) is due to Maurey (1979) [1] who used the Martingale method in his proof. This is one of the early influential concentration results. Expositions and generalizations are in the Book by Milman-Schechtman, and in Naor's lecture notes [3], See Theorem 13 there. The Hamming and transposition distance are related by $$\frac{1}{2} d_H \le d_T \le d_H-1 \,. \quad (*)$$ and therefore concentration in the Hamming metric yields concentration in the transposition metric. The right-hand inequality follows from the standard fact (easily verifiable by induction) that any permutation on $k$ elements is a product of at most $k-1$ transpositions. Further generalizations, discussion of the sharp constants and these comparison inequalities is in [4] and [5].

[1] B. Maurey. Construction de suites sym´etriques. C. R. Acad. Sci. Paris S´er. A-B, 288(14):A679–A681, 1979.

[2] Milman, V.D. and Schechtman, G., 1986. Asymptotic Theory of Finite Dimensional Normed Spaced.

[3] Assaf Naor Lecture notes, https://cims.nyu.edu/~naor/homepage%20files/Concentration%20of%20Measure.pdf

[4] Bobkov, S.G., Houdré, C. and Tetali, P., 2006. The subgaussian constant and concentration inequalities. Israel Journal of Mathematics, 156(1), pp.255-283. https://link.springer.com/content/pdf/10.1007/BF02773835.pdf

[5] Samson, Paul-Marie. "Transport-entropy inequalities on locally acting groups of permutations." Electronic Journal of Probability 22 (2017). https://projecteuclid.org/download/pdfview_1/euclid.ejp/1502244025

Answer 2

See Section 5.8 in my PhD thesis, in particular the last display on p. 65: https://www.cs.bgu.ac.il/~karyeh/thesis.pdf

There is a 1-to-1 correspondence between $\Omega_1\times\ldots\times\Omega_n$ and $S_n$, so the normalized counting measure on the two sets is identical. The aforementioned result gives subgaussian concentration on this set under the Hamming metric, which immediately implies the result you're seeking (see Sec. 2.3.1 ibid. on Levy families and the connection between subgaussian concentration and the type of result you've stated).