Itai Benjamini
Krzysztof Burdzy
Tom Liggett
Ofer Zeitouni

Open problems

New (5/10) A broad class of open problems, suitable for thesis topics, concerns

• First passage percolation (SI epidemics) on finite graphs.

I categorize problems on a conceptual-technical spectrum. That is

• Type 1 We have a question in words, but we don't know how to state a precise mathematical problem which both seems capable of solution and whose solution would be interesting.
• Type 2 We have a precise mathematical problem, but we do not see any plausible outline for a potential proof.
• Type 3 We have a precise mathematical problem, and a plausible outline for a potential proof, but we cannot carry through the technical details.

• (0.5) Martingale, for practical purposes.
• (0.7) Congestion in networks: SOC, HOT and the percolation-fragmentation phase transition.
• (1.7) The constrained Ising model as an algorithm for storage in dynamic graphs.
• (1.8) Bacon and eggs: task scheduling into batches.
• (1.9) Metropolis on Cayley graphs.
• (2.0) Coding invariant processes on infinite trees.
• (2.1) Mixing times for the branch-rotation chain on cladograms.
• (2.2) Random Eulerian circuits.
• (2.6) Percolation and empires.
• (2.7) Greedy tour length and the greedy spatial service algorithm.
• (3.0) Wright-Fisher diffusions with negative mutation rate!
• (3.2) How many Brownian particles escape when you control with total drift = 1?.
• (3.3) The low-density limit of coalescing branching random walk.

In a different realm, I really really really want someone to do this simulation. Of course, it's not easy!

Also, pages 9-12 of Lecture 3 in these Local weak convergence of random graphs and networks lectures give a "recursive distributional equation" I would like someone to solve numerically.

Former open problems, now solved or irrelevant.

• Spectral gap for the interchange (exclusion) process on a finite graph.
• Independent sets in sparse random graphs
• Power laws and killed branching random walk.
• Mixing time for a Gibbs sampler on the simplex.
• Scaling window for percolation of averages in the mean-field setting.