62 problems

Let $r,\delta\geq2$ be fixed integers, and let $G$ be a connected graph of order $n$ and minimum degree $\delta$. Erdős–Pach–Pollack–Tuza conjecture. (i) If $G$ is $K_{2r}$-free an…

Let $M(\Delta \leqslant k)$ denote the maximum inversion diameter among graphs whose maximum degree is at most $k$. The complete graph gives $M(\Delta \leqslant k) \geqslant k$. Ma…

Let $G$ be a graph with Laplacian matrix $L(G)$, and let a Fiedler vector be an eigenvector associated with the second-smallest eigenvalue of $L(G)$. The diameter of $G$ is the max…

Stochastic diameter monotonicity conjecture. If

Let $GPG(n,s)$ be the generalized Petersen graph and let $C_n(1,s)$ be the circulant graph with step sizes $1$ and $s$. Let $n\geq 5$ and…

Let $G=\mathbb{Z}_n$ with $n$ prime, and fix the number of random generators $k$. Let $\operatorname{diam}(G_k)$ denote the diameter of the random Cayley graph. Diameter limit conj…

Let $\mathbb{F}$ be a field and let $\operatorname{Mat}_n(\mathbb{F})$ be the algebra of $n\times n$ matrices over $\mathbb{F}$. Let $\Gamma(\mathbb{F},n)$ be the graph whose verti…

Consider the long-range percolation graph on the vertex set $\{0,1,\ldots,N\}^d$, where vertices at distance $r$ are connected with probability approximately $\beta/r^s$. Linear di…

Consider the one-dimensional long-range percolation graph on the finite circle with vertex set $\{0,1,\ldots,N\}$, in which neighboring vertices are joined with probability one and…

Consider the one-dimensional long-range percolation graph on the finite circle with vertex set $\{0,1,\ldots,N\}$. Neighboring vertices are joined with probability one, and distinc…

Let $G$ be a finite transitive graph, let $|G|$ denote its number of vertices, and let $p^G$ be its percolation threshold. Diameter criterion conjecture. There is a constant $C<1$…

Critical-exponent conjecture. (A) If $s=2$, then the diameter's order of magnitude is $N^\delta$, where $\delta$ is a function of $\beta$. (B) If $1<s<2$, then the diameter is…

Minimum-degree diameter conjecture. For every $d\geq3$ and $epsilon0$,

Large-surplus conjecture. Fix $epsilon0$. If $n2(boldsymbol{d}^n)leq(1- epsilon)n$ and $sn=s(boldsymbol{d}^n)tobinfty$, then

Let $m\ge 2$ and $\delta>0$, and let $G_n\sim \operatorname{PA}_n^{(m,\delta)}$. Let … Here $\nu$ is the exponential growth rate of the local weak limit of the preferential attachm…

Let $C\!D(k,q)$ be a connected component of $D(k,q)$. Schneider's conjecture. For every prime power $q$, $\operatorname{diam}(C\!D(3,q))=6$. For $k>3$ odd, the diameter is $k+5$, a…

Let $C\!D(k,q)$ be a connected component of $D(k,q)$, with $k\ge 2$ and $q$ a prime power. Lazebnik–Ustimenko–Woldar's conjecture. There is a positive constant $C$ such that … This…

Let $n=2m$ with $n\geq 6$, and consider the Schreier coset graph of $S_n$ on binary strings with $m$ zeros and $m$ ones. Let $d_n$ be the distance from the specified starting verte…

Let $S_n$ be the symmetric group with the LRX generators, and let the element described in the source be the observed element of length $n(n-1)/2$. Uniqueness conjecture. This elem…

Let $S_n$ be the symmetric group equipped with the cyclic shift and transposition generators defining the LRX Cayley graph, and let its diameter be the maximum word length of an el…

Let $(0,b,1,e)$ be a reduced prototype with $D\equiv 1\pmod 4$, and let the target prototype be $(0,(D-1)/4,1,\pm1)$, with the sign determined by the spin invariant when…

Repetition-ratio conjecture. For every $\delta\geq4$,

Czabarka–Singgih–Székely conjecture. If $\omega(G)\leq k$, then

Let $G$ be a finite non-abelian group. Its commuting graph $\Gamma(G)$ is the simple graph with vertex set … where two vertices are adjacent if and only if they commute in $G$. Ira…

Let $K_n$ be the complete graph on $n$ vertices, and let $\mathcal{U}(K_n)$ be its unlabelled inversion graph, obtained by identifying vertices of the inversion graph corresponding…