2025/10/05 by Liu, Elliott, Tang, Linus, Wan, Jessica
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2510.04335
We study long r-twins in random words and permutations. Motivated by questions posed in works of Dudek-Grytczuk-Ruciński, we obtain the following. For a uniform word in [k]n we prove sharp one-sided tail bounds showing that the maximum r-power length (the longest contiguous block that can be partitioned into r identical subblocks) is concentrated around (log n)/((r-1)log k). For random permutations, we prove that for fixed k and r→∞, a uniform permutation of [rk] a.a.s. contains r disjoint increasing subsequences of length k, generalizing a previous result that proves this for k=2. Finally, we use a computer-aided pattern count to improve the best known lower bound on the length of alternating twins in a random permutation to αn ≥ (\tfrac13+0.0989-o(1))n, strengthening the previous constant.