19 problems

Let $Y$ be a graph, let $\overline{Y}$ be its complement, and let $\operatorname{Acyc}(\overline{Y})$ denote the acyclic orientations of $\overline{Y}$. Let…

Let $n$, $\delta_1$, and $\delta_2$ be positive integers, and let $c>0$ be a constant. Sharpness conjecture. There exists a constant $c>0$ such that, for every triple satisfying ……

Let $X$ and $Y$ be connected graphs on $n$ vertices. For a graph $G$, write $\delta(G)$ for its minimum degree, and let $\operatorname{FS}(X,Y)$ denote the friends-and-strangers gr…

Disjoint-path connectivity conjecture. The maximum number of disjoint paths between any two permutations $\sigma$ and $\rho$ in $G$ equals $\min\{\deg(\sigma),\deg(\rho)\}$. This w…

Let $X$ be a connected simple graph, and let $c^{(X)}$ and $c^{(\mathsf{Star}_n)}$ be multiplicity lists, with equal total capacity. Let the center of $\mathsf{Star}_n$ have multip…

Let $X,Y\sim\mathcal{G}(n,p)$ denote independent Erdős–Rényi random graphs on $n$ vertices, and let $X,Y\sim\mathcal{G}(K_{n,n},p)$ denote independent random bipartite graphs with…

The isolated-vertex threshold conjecture. The threshold probabilities for connectivity of randomly generated friends-and-strangers graphs should coincide with the thresholds for co…

Let $X$ be an arbitrary connected graph with finite girth, and let $\mathcal C$ be the set of cycle subgraphs in $\mathsf{FS}(X,\operatorname{Star}_n)$ that achieve its girth. For…

Let $Y$ be a graph on $n\geq 3$ vertices such that $\overline{Y}$ is a forest consisting of trees $\mathcal T_1,\dots,\mathcal T_r$ with … Let $X$ be a biconnected graph on $n$ ver…

Let $\mathcal G$ be the set of simple graphs whose friends-and-strangers graph with a star factor has the relevant girth property, and let $\tilde{\mathcal G}$ be the explicitly de…

Let $X$ be a connected graph with finite girth, let $\mathcal C$ be the set of cycle subgraphs of $\mathsf{FS}(X,\textsf{Star}_n)$ that achieve its girth, and for each…

Let $Y$ be a graph on $n\geq 3$ vertices such that its complement is a forest consisting of trees $\mathcal T_1,\dots,\mathcal T_r$ with … If $X$ is a biconnected graph on $n$ vert…

Let $Y$ be a graph on $n$ vertices, and let $\mathsf{FS}(\textsf{Cycle}_n,Y)$ denote its friends-and-strangers graph. The quadratic diameter conjecture asserts that the maximum dia…

Let $K_{r,r}$ be the complete bipartite graph with two parts of size $r$, and let $d_{r,r}$ be the smallest natural number such that any two edge-subgraphs $X$ and $Y$ of $K_{r,r}$…

Let $d_n$ be the smallest natural number such that, for any two graphs $X$ and $Y$ on $n$ vertices with $delta(X)\ge d_n$ and $delta(Y)\ge d_n$, the friends-and-strangers graph…

Let $d_{r,r}$ denote the parameter defined in the paper’s bipartite minimum-degree theorem, and let $r$ be a positive integer. Bipartite minimum-degree threshold conjecture. We hav…

Let $d_n$ denote the parameter defined in the paper’s minimum-degree theorem for friends-and-strangers graphs. Minimum-degree threshold conjecture. We have … This conjecture predic…

Let $r$ be a positive integer, let $p\in[0,1]$, and let $X$ and $Y$ be independently chosen random graphs from $\mathcal G(K_{r,r},p)$, where $K_{r,r}$ is the complete bipartite gr…

Coprime forest conjecture. If $X$ is biconnected, then $\operatorname{FS}(X,Y)$ is connected.