43 problems

Goemans–Linial conjecture. The integrality gap satisfies

Let $X$ be an $n$-point metric space of negative type. Matoušek's conjecture. The metric space $X$ embeds into $L_1$ with distortion $O(1)$. This conjecture is attributed to Matouš…

Let $X$ be an $n$-point subset of $L_1$, and let $c_2(X)$ denote its least distortion when embedding $X$ into Hilbert space. The hypercube conjecture. Every $n$-point subset of…

Let $G$ be a graph of girth $g$, meaning that $g$ is the length of its shortest cycle, and suppose that every vertex of $G$ has degree at least $3$. Let $c_2(G)$ denote the least d…

Hypermetric integrality-gap conjecture. The integrality gap is still $2-o(1)$ when we impose the condition that the solution is a Hypermetric.

Fix $0<delta<1$ and $epsilon>0$. For each $k\in\mathbb{N}$, let $Emb(1+epsilon,k,delta)$ denote the least dimension $N$ such that every subset of $\{0,1\}^N$ of density at least…

Fix $k\in\mathbb{N}$ and $0<delta<1$. Let $Emb(1,delta,k)$ be the smallest $N$ such that every subset $\mathcal{D}\subset\{0,1\}^N$ of density at least $delta$ contains the image o…

$K_{1,3}$ characterization conjecture. The following statements are equivalent:

Four-point obstruction conjecture. The following statements are equivalent:

Let $(X,d)$ be an infinite ultrametric space. A metric space is weakly similar to another when there is a similarity between them, allowing a positive rescaling of distances. Infin…

Let $(X,\delta)$ be a finite ordinal space and let $n\in\mathbb N^+$. For a subset $A\subseteq X$, write $A\hookrightarrow\mathbb R^n$ when the induced ordinal space on $A$ embeds…

Let $(X,\delta)$ be an ordinal space with $|X|=n\in\mathbb N^+$, and let $x_1,x_2,\ldots,x_n$ be an enumeration of its points satisfying the majorization property. Write…

Let $W_4$ denote the wheel graph on four vertices, and let $(\ell_\infty^2,\ell_\infty)$-flattenable graphs be those graphs whose edge-length preserving embeddings from…

Embedding-framework conjecture. The approximation can be improved, and the preprocessing time can also be made polynomial via the low average distortion embeddings framework.

The construction recursively extends graphs using randomized graph extensions, with $t$ graphs and appropriately chosen edge lengths. Recursive graph-extension conjecture. Recursiv…

Suppose $(X,d)$ is a metric space and $X=A\cup B$, where $c_p(A)$ and $c_p(B)$ are finite. Here $c_p(S)$ denotes the least bi-Lipschitz distortion with which the metric space $S$ e…

Low-dimensional special linear group conjecture. For every prime power $\mathfrak{q}$ there exist $D=D(\mathfrak{q})\geqslant1$ and positive constants $c=c(\mathfrak{q})$,…

Special linear group Euclidean distortion conjecture. For every $k\in\mathbb{N}$ and every prime power $\mathfrak{q}$,

Finite-dimensional snowflake embedding conjecture. For every $\upomega\in(0,\tfrac12)$, there exists $\mathsf{C}_\upomega>0$ such that, for every integer $k\geqslant 2$, the…

Reverse implication impossibility conjecture. In general, the average John theorem cannot be formally deduced from the quadratic matrix-dimension inequality

Negative superreflexive snowflake conjecture. There exists a superreflexive Banach space $X$ such that no $\upomega(X)$-snowflake of $X$, for any $\upomega(X)\in(0,1]$, embeds with…

Let $(\mathcal{M},d_\mathcal{M})$ be an $n$-point metric space. For $p,D\geqslant 1$, a bi-Lipschitz distortion-$D$ embedding of $\mathcal{M}$ into a metric space means an embeddin…

Let $(X,\delta)$ be a diversity with induced metric $d$, and consider embeddings constructed solely from $d$. Induced-metric embedding conjecture. There exists such an embedding th…

Let $\mathcal{M}\subseteq \ell_1$ be a subset with $|\mathcal{M}|=n$. An embedding of $\mathcal{M}$ into a normed space has distortion $D$ if distances are preserved up to a multip…

Let $L$ be a finite set of graphs. A graph excludes $L$ as a minor if it contains no member of $L$ as a minor, where minors are obtained by edge contractions, edge deletions, and v…