This page is mainly inspired from Aldous' open problems. These problems are probably not that interesting but I still find them challenging. I'd love to see a solution for some of them, but there is no bounty. If you work on it and find a solution, I'm glad that we might have something to discuss next time we meet, and I hope you had fun working with them. Some of these problems might already have been solved, but I'm not aware of it, but if you send me a reference, I will edit the list accordingly.
List of open problems
- Convexity of the growth rate in the longest increasing path in Erdos-Rényi random graph: Consider an Erdos-Rényi random graph, with connection constant p and n vertices. Calling L the length of the longest increasing path in that graph, it is known this quantity grows as n C(p). The function p ⟼ C(p)/p appears to be convex, but I have no idea why. Additional reading on the subject [1], [2].
- Derrida--Retaux model with half-integers: Consider a binary tree of height n. On each leaf of the tree, an i.i.d. number of cars, sampled according to a common law, start climbing down the tree toward the root. In each internal node of that tree, there are two parking spots. If a car finds it empty, it will immediately park in it. Depending on the initial distribution of cars, one of two things will happen as n→ ∞: either all cars will park with high probability, or a number of cars proportional to the number of leaves will have to exit the tree without parking. The question is to determine a test on the initial distribution of cars that expresses if we will be in the first or second case. Some further readings [1], [2].
- Characterization of branching Lévy processes by their law at time 1: Recall that the law of a Lévy process is in one-to-one map with its law at time 1. In this article, we introduced a similar notion for branching Lévy processes, and showed that any infinitely ramified point measure can be represented as the law at time 1 of a branching Lévy process. However, we were not able to show that this is a one-to-one map, as there might in theory be more than one branching Lévy process with a given distribution of children at time 1. However, we conjecture it not to be the case, without being able to find a proof at the moment.