DR's Open Problems

My Favorite Open Problems

... on Graphs

A graph with m edges is antimagic provided there is an injective labeling of the edges with $\{1,2,...,m\}$ such that, if each vertex is assigned the sum of the labels of the incident edges, the vertex sums are pairwise distinct.
Conjecture: "Every connected graph different from $K_2$ is antimagic."
This was posed by Hartsfield and Ringle [1990, pp 108].
A natural generalization is: A graph with $m$ edges is $k$-antimagic provided there is an injective labeling of the edges with $\{1,2,...,m+k\}$ such that... the vertex sums are pairwise distinct.
Question: For what $k$ is every connected graph, except $K_2$, $k$-antimagic?
Berikkyzy et al. [2014+] proved that every connected graph on $n \geq 3$ vertices is $\left\lfloor \frac{4n}{3} \right\rfloor$-antimagic.
A pseudograph is an undirected graph with loops and multiple edges allowed. An $\{r-t,t\}$-factor of an $r$-regular graph is a spanning subgraph in which every vertex has degree either $r-t$ or $t$. Assume henceforth that $0 < t \leq \frac{r}{2}$.
Akbari and Kano [2014] showed that if $r > 4$ is odd and either $t$ is even or $t \geq \frac{r}{3}$ is odd, then every $r$-regular pseudograph has an $\{r-t,t\}$-factor. They further conjectured this to be the case for odd $r$ and all $t$.
Axenovich and Rollin [2015] disproved their conjecture, showing that for odd $t$ with $(t+1)(t+2) \leq r$, there exists an $r$-regular graph with no $\{r-t,t\}$-factor.
The smallest values of $r$ and $t$ for which Akbari and Kano's conjecture remains open are $r = 5$ and $t = 1$.
Conjecture: Every $5$-regular pseudograph contains a $\{4,1\}$-factor.
Bernshteyn et al. [2016+] established about a dozen conditions that must apply to a vertex-minimal $5$-regular pseudograph with no $\{4,1\}$-factor, provided such a graph exists.

... in Geometry

Question: What is the greatest number of non-overlapping congruent regular tetrahedra that can share a common vertex?
You can slice up a regular icosahedron into $20$ non-regular tetrahedra touching the center, and these are short, fat tetrahedra, so you can fit a regular tetrahedron within each.
By calculating the solid angle cut out by a regular tetrahedron, you find that at most $22$ can fit within the full solid angle.
This question first emerged no later than 1958, yet it remains open whether the answer is $20$, $21$, or $22$.
Lagarias and Zong [2012] give more details for this and other tetrahedra-packing problems.
There are many ways one might define how "close" a simple polygon is to being convex. For example, every exterior angle of a polygon has measure at least $\pi$, so a polygon with a minimum exterior angle near zero might be considered "very unconvex."
Conjecture 1: Every set of $n$ points (no $3$ colinear) has a simple polygonization with minimum exterior angle at least $\frac{2\pi}{n-1}$.
Rorabaugh [2014+] posed this along with the following partial results:
(i) ... minimum exterior angle at least $\frac{\pi}{(n-1)(n-x)}$, where $x$ is the number of points on the convex hull.
(ii) If the conjecture is correct, it is tight, achieved by $n-1$ points in a circle with $1$ point in the center.
A subset $S \subseteq R^d$ is a Danzer set provided every convex body of volume $1$ in $R^d$ contains a point in $S$. Assume $d \geq 2$.
Question: Does there exist a Danzer set with density $O(1)$--that is, with $O(r^d)$ points in the ball of radius $r \rightarrow \infty$?
Bambah and Woods [1971] showed that a Danzer set cannot be the union of a finite number of grids, but there exist Danzer sets with density $O\!\left((\log r)^{(d-1)}\right)$.
Solomon and Weiss [2014] improved both results, showing that a Danzer set cannot be a cut-and-project set, but there exist Danzer sets with density $O(\log r)$.

Gowers [2000] asked whether there exists a Danzer set $S$ with $d = 2$ and a constant $C$ such that every convex body of area $1$ contains at most $C$ points in $S$.
Solan, Solomon, and Weiss [2015] proved that no such set exists; moreover, given a Danzer set $S$ with $d \geq 2$, for any positve $n$ and $\varepsilon$, there exists an ellipsoid with volume at most $\varepsilon$ and with at least $n$ points in $S$.

Conway offers $1000 for a solution to the following Danzer problem variant:
"Dead Fly Problem: If a set of points in the plane contains one point in each convex region of area $1$, then must it have pairs of points at arbitrarily small distances?"
The Solan-Solomon-Weiss result does not give a positive answer to Conway's question because the longest diameter of their ellipsoid can grow with $n$.
A point-set $S$ in the plane satisfies geometric characterization $GC_n$ provided for each $x \in S$, there is a set of $n$ lines such that $x$ is not on any of the lines by each point in $S-\{x\}$ is on at least one line.
Conjecture: Given a $GC_n$ point-set $S$, there exists a line containing $n-1$ points of $S$.
This is a conjecture of Gasca and Maeztu [1982].
It is known to be true for $n \leq 5$: Busch [1990] proved it for $n = 4$ and Hakopian, Jetter, and Zimmermann [2013] for $n = 5$.
This problem was my 2014 submission to the Rocky Mountain-Great Plains Graduate Research Workshop in Combinatorics.
Call two filled triangle in $\mathbb{R}^3$ almost-disjoint provided they intersect in at most one point and, if they do, that point is a vertex of both triangles. Let $f(n)$ be the maximum number of pairwise almost-disjoint triangles one can embed in $\mathbb{R}^3$ so that the total number of vertex points is $n$. For example $4$ faces of an octahedron can be selected so that no two share more than one point, and this is the greatest number of pairwise almost-disjoint triangles on $6$ vertex points, of so $f(6) = 4$.
Question: What is the asymptotic growth of $f(n)$?
Since each pair of vertices is contained in at most one edge, and there are only three edges per triangle, $f(n) \leq {n \choose 2}/3 \ll n^2$.
This question was asked by Kalai in 1995, as told by Károlyi and Solymosy [2002], who proved that $f(n) \gg n^{3/2}$.
This problem was my 2015 submission to the Rocky Mountain-Great Plains Graduate Research Workshop in Combinatorics.
An intersecting family is a collection of sets such that every pair of sets has a non-empty intersection. An $r$-set is a set with $r$ elements.
Erdős, Ko, and Rado [1961] proved that the maximum size of an intersecting family of $r$-subsets of $\{1,2,...,n\}$ with $2r \leq n$ is ${n-1 \choose r-1}$.
Equality can be attained by fixing one element and taking the collection of all $r$-sets containing that element. Thus there are $n-1$ options for the other $r-1$ elements.
Kalai [2015] proposed an analogous result for polygon triangulations:
"Let $\mathcal{T}_n$ be the family of all triangulations on an $n$-gon using $n-3$ non-intersecting diagonals. The number of triangulations in $\mathcal{T}_n$ is $C_{n-2}$ the $(n-2)$-th Catalan number. Let $\mathcal{S} \subset \mathcal{T}_n$ be a subfamily of triangulations with the property that every two triangulations of $\mathcal{S}$ have a common diagonal.
Problem: Show that $|\mathcal{S}| \leq |\mathcal{T}_{n-1}|$."
Similarly to the set situation, equality can be attained by fixing a diagonal that divides the n-gon into a triangle and an $(n-1$)-gon, leaving $|\mathcal{T}_{n-1}|$ possibilities for the rest of the triangulation.

... on Words

The period of word $W$, denoted $p(W)$, is the least positive $p$ such that $W[i] = W[i+p]$ for all $i$. A bifix or border of $W$ is a proper factor that is both a prefix and suffix of $W$. Thus $p(W) = |W|$ iff $W$ is bifix-free/unbordered. Let $\mu(W)$ be the length of the largest bifix-free factor of $W$. Trivially, $\mu(W) \leq p(W)$.
Question: What word-lengths $|W|$ imply that $\mu(W) = p(W)$?
This was first explored by Ehrenfeucht and Silberger [1979], who conjectured that $|W| \geq 2\mu(W)$ is sufficient.
Assous and Pouzet [1979] disproved that conjecture, providing couterexamples when $|W| = \frac{7}{3}\mu(W) - 4$. They conjectured that $|W| \geq 3\mu(W)$ is sufficient and best possible.
Duval [1982] proved that $|W| \geq 4\mu(W) - 6$ is sufficient.
Harju and Nowotka [2003] proved that $|W| \geq 3\mu(W) - 2$ is sufficient and conjectured that even $|W| \geq \frac{7}{3}\mu(W) - 3$ suffices.
Question: Do there exist words $u_1, \ldots, u_n$ such that
- $(u_1 u_2 \cdots u_n)^2 = (u_1)^2 (u_2)^2 \cdots (u_n)^2$ and
- $(u_1 u_2 \cdots u_n)^3 = (u_1)^3 (u_2)^3 \cdots (u_n)^3$,
and the words do not all pairwise commute, that is, $u_i u_j \neq u_j u_i$ for at least one pair $(i,j)$?
Holub [2003+] offers a reward of 200 € for a solution.

... on Numbers

The Collatz Conjecture or $3n+1$ Problem.
Consider the following process: if a number is odd, multiply by three and add one; if it is even, divide by two.
Conjecture: Every positive integer, under repeated application of the $3n+1$ process, will eventually reach $1$.
Starting with $7$, for example, $7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$.
You can read more on MathWorld or Wikipedia.
This is an extremely popular problem, as demonstrated by Lagarias' annotated bibliographies (1963—1999 and 2000—2009) and the hundreds of "collatz"-related sequences on the OEIS.
I myself investigated a generalization for my undergraduate thesis [2010], which I have since enjoyed sharing with other undergrads [2012].
As of March 2016, the conjecture has been verified for every positive integer up to $2^{60}$, according to Roosendaal's website.
Before you descend into this rabbit hole, consider a warning from xkcd.

My Favorite Open Problems

Other Problem Sources