520 problems

Let $G$ be a finite graph, let $\lambda(G)$ denote the spectral radius of its adjacency matrix, and let $G_p$ be obtained from $G$ by retaining each edge independently with probabi…

Let $H$ be a fixed connected graph, let $G_{n,p}$ be the Erdős–Rényi random graph, and let $X_H$ denote the number of copies of $H$ in $G_{n,p}$. Define…

Carpentier's motif-counting conjecture. If

Optimal Power of Few conjecture. There is a function $f(x)$ such that $f(x)>1/2$ for $x>0$, $f(x)$ tends to $1$ as $x$ tends to infinity, and, in majority dynamics on $G(n,p)$ with…

Let $T$, $B$, $F$, and $C$ be the four random variables defined in the depth-first search analysis of the random digraph. Joint asymptotic normality conjecture. All four variables…

Let $\mathbb{G}_n=G(\mathbf{Y}^{(n)},\mathbf{W}^{(n)},\kappa_n)$ satisfy the assumptions of the local weak convergence theorem in the source, except for the assumption imposing reg…

Let $\theta_n$ satisfy the scaling condition in the source, and let $X_n=(X_n(k);k=0,1,\dotsm)$ be the breadth-first walk on the random graph $\mathscr{G}_n^\theta$ constructed for…

Let $(G_n)_n=(V_n,E_n)_n$ be a sequence of finite, connected, vertex-transitive graphs with vertex degree $\bDelta_n$ diverging as $n\to\infty$. For a fixed sequence and fixed $u$,…

Let $ell geqslant 2$ and let ${\mathcal R}$ be an $ell$-vertex size rule. Define $t_{\mathrm{b}}^{{\mathcal R}}$ as the supremum of the set of $t \geqslant 0$ for which the suscept…

Let $p_3(n)$ denote the third critical probability at which the relative covariance of paths in $\vec G(n,p)$ changes sign, where $p_1(n)<p_2(n)<p_3(n)$ are the three critical prob…

Let $\kappa$ satisfy condition … be the fixed-point equation for the corresponding branching-process generating function. Necessary-and-sufficient condition for subcriticality. One…

Let $G_n$ be a family of vertex-transitive bipartite graphs with $|G_n|\to\infty$. Let $\Delta_n$ denote the diameter of $G_n$, and let $f_n$ be uniformly random in…

Consider the GN$(1,\underline{\alpha})$ model on a Poisson process on $\mathbb{R}$, where $\alpha_i$ are the connection parameters and clusters are formed according to the model's…

Let $G$ be the evolving random graph process, and write $\tau(\mathcal E)$ for the hitting time at which event $\mathcal E$ first occurs. Let ${\cal M}$ be the perfect matching gam…

Let ${\cal H}$ be the set of Hamiltonian cycles in $K_n$. For a family of winning sets ${\cal F}$, let $b_{\cal F}^p$ denote the smallest bias for which Breaker wins the random gam…

A graph is greedy if every configuration of $\pi(G)$ pebbles can be solved at any specified root using only greedy pebbling steps. It is tree-solvable if every configuration of siz…

Let … be its associated integral operator with norm … has an eigenfunction … satisfying $<$; conversely, $=0$ if $>0$ but no such eigenfunction exists or an eigenfunction exists wi…

Let $\rho(c)$ denote the giant-component fraction as a function of the scaling parameter $c$, and let $c_0$ be the critical value. Theorem5(i) establishes analyticity under conditi…

For a complete bipartite graph $K_{n,n}$ with independent exponentially distributed edge appearance times of rate $1$, let $L_{nn}(n)$ denote the length of a minimum $n$-assignment…

Let $P(\mathcal{X}_n)$ and $P(\mathcal{D}_n)$ be the matrices associated with the random geometric graph and its deterministic comparison model, and let $\lambda_i(\mathcal{X}_n)$…

Graded-graph path-count conjecture. One has

Let $p_c(n)$ be the critical probability for the random subgraph of the $n$-cube, let $V=2^n$, and write … Assume $\epsilon\rightarrow0$ and…

Independent-set density existence conjecture. For every $c>0$ and $r\geq 3$, the limits

Fix an integer $k\geq 2$, and let $G(n,cn)$ be the sparse random graph with $n$ vertices and $cn$ edges. The graph is $k$-colorable when its vertices can be assigned colors…

A random K-SAT instance has $n$ Boolean variables and $m=cn$ clauses, where $c$ is the clause-to-variable ratio and $K$ is the number of literals per clause. The linear phase trans…