CAREER: Phase Transitions in Some Discrete Random Models and Mixing of Markov Chains

University Of Delaware, Newark DE

Investigators

Abstract

Water turning into ice at its freezing point or the magnetization of iron are examples of phase transitions in physical systems. At the transition point, the properties of the system such as the volume or heat capacity may change discontinuously. The aim of our research is to study phase transitions in mathematical models using probabilistic tools in the following three directions. (1) The longest increasing subsequence (LIS) of a permutation is the length of a maximal subsequence of the permutation in which the elements increase. How long is the LIS for a uniformly random permutation? This question has been studied in connection with practical applications such as sorting sequences, disk drive scheduling and airplane boarding times. The mathematical study of the LIS has revealed deep and unexpected connections of the problem with areas such as the theory of random matrices, analytic combinatorics and random polymer models. The proposed research aims to study the LIS when the permutation is drawn from certain non-uniform distributions and associated phase transitions. (2) Many computational problems can be phrased as constraint satisfaction problems (CSPs) where one wants to find a solution to a number of variables with a set of constraints imposed on them. CSPs were first studied in computer science motivated by applications to artificial intelligence. To study the difficulty of finding solutions in typical rather than worst case scenarios, researchers study random CSPs. Using sophisticated heuristics, physicists have made detailed predictions about the location and nature of phase transitions in random CSPs. The accuracy of these heuristic predictions motivates the importance of discovering the rigorous mathematical foundations of these techniques. (3) Interacting particle processes are used to model large, randomly evolving interacting systems of agents that arise in the natural sciences including in physics and in biology. The exclusion and interchange random walks are examples of such interacting particle processes. In the symmetric case the long term mixing behavior of the random walk and the nature of phase transitions is well studied. The goal of this research is to understand the mixing properties of natural asymmetric and weighted versions of these processes. While achieving these three goals, the principal investigator will create exciting research opportunities for graduate and undergraduate students in probability, mentoring programs with the goal of retention of women in mathematics, and the development of online curricular material. The main aim of this project is to develop new theory and analysis for phase transitions in certain discrete probabilistic models. The first problem is to study the limiting distribution of the LIS in non-uniformly random permutations by way of analyzing the fluctuations of the LIS as the parameter of the distribution is varied. The distribution is known to be Gaussian in one regime of the parameter and Tracy-Widom in another and we aim to study this transition. The second problem is to study the condensation and clustering transitions in random CSPs such as the hardcore model on random graphs. The research aims to identify the location of the reconstruction threshold more precisely in these models and to explore the connection to the clustering transition. Finally, the proposal will consider Markov processes such as asymmetric exclusion and interchange and attempt to relate the mixing times and spectral gaps of these processes to the corresponding quantities for a single particle and to understand the cutoff phenomenon for these processes.