84 problems

Let $G(n,d,p)$ be the spherical random geometric graph and let $G(n,p)$ be the Erdős–Rényi random graph. For probability distributions on a finite set, define total variation dista…

Gupta–Kumar connectivity conjecture. The graph

Let the graph size be $n$, and consider a random geometric graph in the sparse regime, where the edge probability vanishes with $n$. Geometry is conjectured to be lost at dimension…

Let $G_d(n,p)$ be the random geometric graph model, and let $\mathcal{F}$ be a non-trivial monotone graph property, where monotonicity means monotonicity under adding edges. Random…

Connectivity threshold conjecture. For the $G^{(k)}(n,r)$ filtered graph,

Let $K\subseteq {\mathbb R}^d$ be a convex body with smooth boundary, and let the distribution be uniform on $K$. Write $r_n$ for the radius parameter and ${{\mathcal R}}(n,r_n)$ f…

Critical logarithmic CLT conjecture. Let $d\in\mathbb{N}$. There exists a constant $σ_{d,d/2}^2\in(0,\infty)$ such that

Penrose–Ong conjecture. Suppose $d\in\mathbb{N}$. The limit theorems for $\d835α\in(0,d/4)$, namely the variance limits and the corresponding Gaussian convergence for the binomial…

Let $G(n,d,p)$ be the spherical random geometric graph formed from $n$ independent uniform points on the unit sphere $\mathbb{S}^{d-1}\subseteq\mathbb{R}^d$, with the distance thre…

Detection threshold conjecture. The largest dimension at which the random geometric graph can be statistically distinguished from the Erdős–Rényi graph with the same edge density s…

For integers $d\geq 1$, let $T_d(n,r)$ be the random graph obtained by sampling $n$ random points of the $d$-dimensional torus $(\mathds{R}/\mathds{Z})^d$ and joining two vertices…

Continuous-circle greedy-routing conjecture. For every $\varepsilon>0$, there exists a constant $K_0=K_0(\varepsilon)$ such that, for all $K\geq K_0$ and sufficiently large $n$, wi…

Spectral estimation conjecture. The critical dimension for estimation is conjectured to be

Spectral detection conjecture. The sharp threshold for distinguishing the RGG from its Erdős–Rényi counterpart is determined by

Bubeck et al.'s geometry-loss conjecture. The geometry of a sparse RGG is lost once

Spectral-gap conjecture. Above a critical dimension, the second largest eigenvalue of $\mathcal G(n,d,p)$ satisfies the optimal bound

Semicircle-threshold conjecture. The true threshold for semicircle convergence is

Let $H_t(\mathcal{G})$ denote the entropy of the random geometric graph distribution at parameter $t$, and let $\bar{p}_{\max}$ be the corresponding edge-probability parameter at w…

Let $p$ denote the dispersion parameter of a random bipartite geometric (RBG) graph, and let the branching-process lower bound be … Here $f$ is a general monotone decreasing connec…

Step-isometry extension conjecture. The map $T$ can be extended to a step-isometry on the whole of $X$.

Strong non-Rado conjecture. Typical countable dense sets in $X$ are strongly non-Rado.

Let $d$ be the latent dimension, $n$ the number of vertices, and $p$ the average edge density of a random geometric graph; let $h(p)$ denote the binary entropy function. The associ…

Given an integer $n$ and a real number $r\in[0,1]$, let $G(n,r)$ be the random geometric graph obtained by placing $n$ points independently and uniformly in $[0,1]$ and joining pai…

Long-cycle extension conjecture. For a suitable choice of $c_3$ and $C_3$, the same conclusion holds for all $L\in[c_3^{-1},n]$.

Matching-size conjecture. Under this assumption,