10 problems

Non-sensitivity conjecture. The matching cost is non-sensitive: the correlation of the total cost before and after resampling is at least

Let $d\in(1,2)$, and let the total cost of the stable matching be denoted by $C_{n,n}^{\rho}$. Consider any suitable rescaling of this total cost. Stable-limit conjecture. The suit…

The parameters $bb$ and $psilon$ occur in the analysis of the expected number of stable matchings with switching costs, and the relevant regime is $psilonbb=o(1)$. Exact-asymptotic…

Decorrelation transition conjecture. There is a transition at

Vanishing strongly stable matchings conjecture. The fraction of instances with at least one strongly stable matching tends to zero as $n\to\infty$.

Eriksson–Escamocher–O'Sullivan conjecture. Every instance of cyclic preferences has a weakly stable matching.

Let an FPRAS be a fully polynomial randomized approximation scheme, and let $\#\mathrm{BIS}$ denote the problem of approximately counting independent sets in a bipartite graph. An…

Consider a Poisson process in ${\mathbb R}^d$ with $k=3$ colours, where points receive colours independently with probabilities $p_1,p_2,p_3$ satisfying $p_1<p_2=p_3$. Any two poin…

Let a Poisson process of intensity $1$ in ${\mathbb R}^d$ have $k$ colours, with colour $i$ assigned independently with probability $p_i$, where $(p_1,\dots,p_k)$ is a probability…

Let a Poisson process of intensity $1$ in ${\mathbb R}^d$ have points independently colored blue with probability $p\in(0,1)$ and red with probability $1-p$. Consider the asymmetri…