Graph Theory and Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Gregory 307
- Date
- Mar 26, 2024 1:00 pm
- Speaker
- The Nguyen (UIUC)
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Views
- 60
- Originating Calendar
- Combinatorics Research Area Calendar
Speaker: The Nguyen (UIUC)
Title: Permutation codes in Levenshtein, Ulam and Generalized Kendall--tau MetricsAbstract: Permutation codes in the Levenshtein metric are known to have a close relationship with those in Ulam and generalized Kendall--tau metrics. In this work, we first show a logarithmic improvement on the Gilbert--Varshamov lower bound of the maximum size of a permutation code capable of correcting $t$ deletions. Then, we present a new connection between different kinds of distances over two permutations, including Hamming, Levenshtein, Ulam, and generalized Kendall--tau distance. From this new connection and some known permutation codes in the Hamming metric, we obtain new permutation codes in Levenshtein, Ulam, and generalized Kendall--tau metrics with better size. In particular, we show that there exist permutation codes of length $n$ for correcting $t$ deletions with at most $(3t+1) \log n+o(\log n)$ bits of redundancy. If time permits, we present the construction of our permutation codes for correcting $t$ deletions with a specific decoding process. This is joint work with Yeow Meng Chee, Van Khu Vu, and Shuche Wang.