Continuously increasing subsequences of random multiset permutations. (May 2023)

• Record Type: Journal Article
• Authors: Clifton, Alexander; Deb, Bishal; Huang, Yifeng; Spiro, Sam; Yoo, Semin
• Is Part Of: European journal of combinatorics. Volume 110(2023)
• Publication Date: 2023-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2023.103708
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: For a word π and an integer i, we define L ( π ) to be the length of the longest subsequence of the form i ( i + 1 ) ⋯ j for some i, and we let L 1 ( π ) be the length of the longest such subsequence beginning with 1. In this paper, we estimate the expected values of L 1 ( π ) and L ( π ) when π is chosen uniformly at random from all words which use each of the first n positive integers exactly m times. We show that E [ L 1 ( π ) ] ∼ m if n is sufficiently large in terms of m as m tends towards infinity, confirming a conjecture of Diaconis, Graham, He, and Spiro. We also show that E [ L ( π ) ] is asymptotic to the inverse gamma function Γ − 1 ( n ) if n is sufficiently large in terms of m as m tends towards infinity.