Twins in words and long common subsequences in permutations

DOI10.1007/S11856-016-1323-8zbMATH Open1354.68213arXiv1307.0088OpenAlexW1793292512MaRDI QIDQ314398FDOQ314398

Authors: Boris Bukh, Lidong Zhou 

Publication date: 16 September 2016

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: A large family of words must contain two words that are similar. We investigate several problems where the measure of similarity is the length of a common subsequence. We construct a family of n^{1/3} permutations on n letters, such that LCS of any two of them is only cn^{1/3}, improving a construction of Beame, Blais, and Huynh-Ngoc. We relate the problem of constructing many permutations with small LCS to the twin word problem of Axenovich, Person and Puzynina. In particular, we show that every word of length n over a k-letter alphabet contains two disjoint equal subsequences of length cnk^{-2/3}. Many problems are left open.

Full work available at URL: https://arxiv.org/abs/1307.0088

Recommendations

• Order-isomorphic twins in permutations
• Variations on twins in permutations
• Tight multiple twins in permutations
• Longest common subsequences in sets of words
• A regularity lemma and twins in words

zbMATH Keywords

bounds for twin problempermutation wordword twins

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

Cites Work

• The difference between consecutive primes. II
• Title not available (Why is that?)
• A variational problem for random Young tableaux
• Expected length of the longest common subsequence for large alphabets
• A regularity lemma and twins in words
• The value of multiple read/write streams for approximating frequency moments
• Longest common subsequences in sets of words

Cited In (16)

• Tight multiple twins in permutations
• Erdős-Szekeres theorem for multidimensional arrays
• Universal arrays
• Universality for random permutations and some other groups
• Order-isomorphic twins in permutations
• Variations on twins in permutations
• Title not available (Why is that?)
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Long twins in random words
• A note on the expected length of the longest common subsequences of two i.i.d. random permutations
• Exponential Erdős-Szekeres theorem for matrices
• Shuffle squares and reverse shuffle squares
• Longest common subsequences in sets of words
• A regularity lemma and twins in words
• On the longest common subsequence of conjugation invariant random permutations
• Broadcast transmission to prioritizing receivers

This page was built for publication: Twins in words and long common subsequences in permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q314398)