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.

Please email me if you are aware of any significant advances on the above problems or if any of my hyperlinks are dead.