Unsolved Problems

Let $G$ be an (additive) abelian group, and for every $S \subseteq G$ let ${\mathit stab}(S) = \{ g \in G: g + S = S \}$. Conjecture Let $M$ be a mat...

Conjecture If $M_1,\ldots,M_k$ are matroids on $E$ and $\sum_{i=1}^k rk_{M_i}(X_i) \ge \ell (k-1)$ for every partition $\{X_1,\ldots,X_k\}$ of $E$, th...

Question Is the binary affine cube $AG(3,2)$ the only 3-connected matroid for which equality holds in the bound $$E(M) \leq c(M) c(M^*) / 2$$where$c(M...

Conjecture Let $r \ge 2$ be an integer and let $H$ be a minor minimal clutter with $\frac{1}{r}\tau_r(H) < \tau(H)$. Then either $H$ has a $J_k$ minor...

Question Does there exist a constant $c>1/2$ and a function $n_0(k)$ such that if $|X|\geq n_0(k)$, then every saturated $k$-Sperner system $\mathcal{...

Let $R(k,k)$ denote the $k^{th}$ diagonal Ramsey number. Conjecture $\lim_{k \rightarrow \infty} R(k,k) ^{\frac{1}{k}}$ exists. Problem Determine th...

Conjecture If $A$ is 2-large, then $A$ is large....

For $k$ and $\ell$ positive integers, the (mixed) van der Waerden number $w(k,\ell)$ is the least positive integer $n$ such that every (red-blue)-colo...

We let $Q_d$ denote the $d$-dimensional cube graph. A map $\phi: E(Q_d) \rightarrow \{0,1\}$ is called edge-antipodal if $\phi(e) \neq \phi(e')$ whene...

Conjecture Let $p_1,p_2,p_3,\ldots$ be a sequence of points in ${\mathbb R}^d$ with the property that for every $i \ge d+2$, the points $p_{i-1}, p_{i...

Let $S$ be a set of points in the plane. Two points $v$ and $w$ in $S$ are visible with respect to $S$ if the line segment between $v$ and $w$ contain...

Conjecture The average diameter of a bounded cell of a simple arrangement defined by $n$ hyperplanes in dimension $d$ is not greater than $d$....

Basic Question: Given any positive integer n, can any convex polygon be partitioned into n convex pieces so that all pieces have the same area and sam...

Problem Does there exist a dense set $S \subseteq {\mathbb R}^2$ so that all pairwise distances between points in $S$ are rational?...

Question What is the minimum cardinality of a decomposition of the $n$-cube into $n$-simplices?...

Conjecture If a finite set of unit balls in $\mathbb{R}^n$ is rearranged so that the distance between each pair of centers does not decrease, then the...

Conjecture Every set of $2^{n-2} + 1$ points in the plane in general position contains a subset of $n$ points which form a convex $n$-gon....

If $X \subseteq {\mathbb R}^2$ is a finite set of points which is 2-colored, an empty triangle is a set $T \subseteq X$ with $|T|=3$ so that the conve...

Question Is is possible to pack $n^n$ rectangular $n$-dimensional boxes each of which has side lengths $a_1,a_2,\ldots,a_n$ inside an $n$-dimensional ...

Question What is the minimum number of colours such that every complete geometric graph on $n$ vertices has an edge colouring such that: \item[Varian...

Conjecture Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning tree...

Problem Classify the point sets with no empty pentagon....

Conjecture For any integer $n \geq 1$, it is impossible to cover a square of side greater than $n$ with $n^2+1$ unit squares....

Problem Enumerate all convex uniform 5-polytopes....

Throughout this post, by projective plane we mean the set of all lines through the origin in $\mathbb{R}^3$. Definition Say that a subset $S$ of the ...

Conjecture For every set $P$ of $n$ points in the plane, not all collinear, there is a point in $P$ contained in at least $\frac{n}{2}-c$ lines determ...

Question What is the least integer $f(n)$ such that every set of at least $f(n)$ points in the plane contains $n$ collinear points or a subset of $n$ ...

Conjecture For each $\ell\geq3$ there is an integer $f(\ell)$ such that every set of at least $f(\ell)$ points in the plane contains $\ell$ collinear ...

Conjecture Associahedra have unbounded chromatic number....

To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total ...

Conjecture Every convex polyhedron has a (nonoverlapping) edge unfolding....

Conjecture Let $k$ be a field of characteristic zero. A collection $f_1,\ldots,f_n$ of polynomials in variables $x_1,\ldots,x_n$ defines an automorphi...

Conjecture Let $X$ be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subva...

The fatness of a 4-polytope $P$ is defined to be $(f_1 + f_2)/(f_0 + f_3)$ where $f_i$ is the number of faces of $P$ of dimension $i$. Question Does ...

Conjecture The order of the largest total curvature of the primal central path over all polytopes defined by $n$ inequalities in dimension $d$ is $n$....

Conjecture For every positive integer $k$, there exists an integer $d$ so that every polytope of dimension $\ge d$ has a $k$-dimensional face which is...

The extension complexity of a polytope $P$ is the minimum number $q$ for which there exists a polytope $Q$ with $q$ facets and an affine mapping $\pi$...

Conjecture Every convex polytope has a non-overlapping edge unfolding....

We let $p(G)$ denote the pebbling number of a graph $G$. Conjecture $p(G_1 \Box G_2) \le p(G_1) p(G_2)$....

The deck of a graph $G$ is the multiset consisting of all unlabelled subgraphs obtained from $G$ by deleting a vertex in all possible ways (counted ac...

Conjecture Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs...

Let $G$ be a finite undirected simple graph. A $k$-page book embedding of $G$ consists of a linear order $\preceq$ of $V(G)$ and a (non-proper) $k$-c...

Problem What is the Shannon capacity of $C_7$?...

Question Is there a constant $c$ such that every $n$-vertex $K_t$-minor-free graph has at most $c^tn$ cliques?...

Given integers $k,n \ge 2$, the 2-stage Shuffle-Exchange graph/network, denoted $\text{SE}(k,n)$, is the simple $k$-regular bipartite graph with the o...

Conjecture If in a bridgeless cubic graph $G$ the cycles of any $2$-factor are odd, then $\omega(G)\leq 2$, where $\omega(G)$ denotes the oddness of t...

Problem ( $\dag$ ) Find a sufficient condition for a straight $\ell$-stage graph to be rearrangeable. In particular, what about a straight uniform gra...

Conjecture Can the approximation ratio $O(\sqrt{n})$ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapp...

Conjecture Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a cons...

Conjecture It has been shown that a $k$-outerplanar embedding for which $k$ is minimal can be found in polynomial time. Does a similar result hold for...