CMI PhD Research Seminar
Date: Monday, 21 October 2024
Time: 09-30 - 10.30 AM
Venue: Seminar Hall
Subsequence frequency in binary words
Krishna Menon P
Chennai Mathematical Institute.
21-10-24

---

Abstract

A binary word is a finite sequence with terms in {0, 1}. We say that a binary word W contains k occurrences of a word P if it has exactly k subsequences that match P. In this context, we usually call P a pattern. The numbers we study are of the form B(n, k, P), which is the number of binary words of length n that have exactly k occurrences of the pattern P. We first obtain expressions for these numbers for small values of k. We then address the following question: For fixed n, P, what is the largest value of k such that B(n, k, P) is non-zero? We end with a conjecture and directions for future research. This is based on joint work with Anurag Singh.