Concentration versus spread - tools, lower bounds and applications

Concentration is a key phenomenon which has been observed in random graphs as well as in many other random discrete structures.

The first goal of the project is the systematic study of concentration and the development of versatile tools that will be applicable in many different contexts.

There is a particular gap in our current knowledge concerning lower bounds for concentration, that is, methods to prove that a random variable typically fluctuates by a lot.

This will therefore be a focus of the project, building upon a framework I recently developed to study the chromatic number. The chromatic number is a central graph theoretic concept. Recently I proved that the chromatic number of random graphs fluctuates considerably, solving a well-known question.

The second focus of the project is the fine-grained random behaviour of the chromatic number and in particular a recent beautiful and surprising conjecture called the Zigzag Conjecture.

The third goal of the project is the application of the developed methods to a range of open problems in probability theory, with connections to physics and computer science.

This includes first passage percolation, a model of fluid flow through a random medium, as well as the longest common subsequence problem, which concerns unstructured strings of 0-1-bits.

I plan to attack the first and second goal in parallel, moving on to the third when the first has progressed substantially. I will work with a PhD student on the first and third goal.