Research Projects

The spectral gap is one of the main objectives of study for finite Markov chains; it has received considerable attention in probability theory literature. Particularly, the spectral gap is useful in estimating the mixing time (informally, it is a measure of the time required for the Markov chain to approach stationary distribution) of convergent Markov chains. In this project, we focus on developing Aldous-type spectral gap results for two random walk models, viz., the matching process on 2n vertices and a random walk on the hyperoctahedral group. Additionally, we have an ambitious goal of proving/disproving an open conjecture of Petro Caputo -- this is a generalisation of the Aldous spectral gap conjecture in the hypergraph setting. We now explain the random walk models in the following paragraphs: The matching process (MP): This is a continuous-time random walk model on the set of all perfect matchings on 2n vertices. Suppose the vertices are leveled by the numbers 1, 2, ..., 2n; and a permutation in S_{2n} acts on the perfect matchings by permuting the vertex levels. A perfect matching M can move to another perfect matching N if and only if N is obtained from M by the action of a transposition, and the (positive) transition rate depends on the associated transposition. For this model, we are interested in the spectral gap of this process. The detailed objective in given at a later stage. The project idea came in a personal communication with M. K. Srinivasan (Professor at IIT Bombay). Thus, he will be one of my collaborators for this part. The random walk on the hyperoctahedral group (RWH): A signed permutation is a bijection \pi on the set {-n, ..., -1, 1, ..., n} to itself such that \pi(-i)=-\pi(i). It is uniquely determined by its image on the set {1, ..., n}; we use the notation [\pi(1), ..., \pi(n)], known as the window notation, to denote the signed permutation \pi. The signed permutations form a group under the composition of mapping, this group is called the hyperoctahedral group. Our random walk model sends a signed permutation \pi to another signed permutation \sigma if and only if one signed permutation is obtained from the other either by interchanging two letters (with rate depending on the two positions) or by changing the signs of the letters at some positions (with rate depends on the aforementioned positions) in the window notation. This model is motivated by a conjecture of Filippo Cesi; we aim to prove/disprove this conjecture. Gil Alon (Senior lecturer at the open university of Israel) will be one of the collaborators for this part. The random walk model for our ambitious goal on Caputo’s conjecture is a continuous-time random walk on the symmetric group on n letters. Let us select a subset A of {1, ..., n} with (positive) rate x_A, and let \xi be any permutation that only permutes the letters in A. Then, the random walk sends a permutation \alpha to another permutation \xi*\alpha with rate x_A.