Random Networks and Deterministic Diffusion Processes

点击翻译按钮获取中文摘要

This project aims to better understand random and pseudorandom processes and the interplay between them. For example, one major focus of the project is a model from statistical physics that replicates power-law behavior seen in the distributions of the frequencies of earthquakes, avalanches, etc. This model exhibits behavior of striking complexity resulting from simple rules, and is a natural de-randomization of related stochastic models from physics. Another aim of this project involves new kinds of probabilistic analyses of algorithms. These may, for example, give guidance on which algorithms may be efficient for "typical" inputs, and which will not. Finally, this project supports the education and mentorship of undergraduates through opportunities for engagement in research. This proposal concerns two principal research directions. The first concerns a pseudorandom diffusion process -- the Abelian sandpile -- which is at the same time both extremely simple in its mechanics, and extremely complex in its behavior. The rich fractals produced by the model had frustrated decades of inquiry. This project aims to extend the mathematical framework recently developed by the principal investigator and collaborators; for example, to understand the effect the choice of underlying lattice has on the behavior of the sandpile. The second area concerns new kinds of probabilistic analyses of point configurations and networks. For example, the question of the length of the shortest cycle through a collection of points in the plane is the Traveling Salesman Problem for Euclidean space, a problem of both classical theoretical interest and immediate practical utility (in transport problems, drilling problems, etc.). A major educational goal of the project is the mentorship of undergraduate research; the investigator has experience in designing courses and research seminars that have been effective for this goal.