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 \(\{rt,t\}\)factor of an \(r\)regular graph is a spanning subgraph in which every vertex has degree either \(rt\) 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 \(\{rt,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 \(\{rt,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 vertexminimal \(5\)regular pseudograph with no \(\{4,1\}\)factor, provided such a graph exists.
... in Geometry

Question: What is the greatest number of nonoverlapping congruent regular tetrahedra that can share a common vertex?
You can slice up a regular icosahedron into \(20\) nonregular 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 tetrahedrapacking 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}{n1}\).
Rorabaugh [2014+] posed this along with the following partial results:
(i) ... minimum exterior angle at least \(\frac{\pi}{(n1)(nx)}\), where \(x\) is the number of points on the convex hull.
(ii) If the conjecture is correct, it is tight, achieved by \(n1\) 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)^{(d1)}\right)\).
Solomon and Weiss [2014] improved both results, showing that a Danzer set cannot be a cutandproject 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 SolanSolomonWeiss result does not give a positive answer to Conway's question because the longest diameter of their ellipsoid can grow with \(n\).
 A pointset \(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\) pointset \(S\), there exists a line containing \(n1\) 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 MountainGreat Plains Graduate Research Workshop in Combinatorics.
 Call two filled triangle in \(\mathbb{R}^3\) almostdisjoint 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 almostdisjoint 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 almostdisjoint 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 MountainGreat Plains Graduate Research Workshop in Combinatorics.
 An intersecting family is a collection of sets such that every pair of sets has a nonempty 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 \({n1 \choose r1}\).
Equality can be attained by fixing one element and taking the collection of all \(r\)sets containing that element. Thus there are \(n1\) options for the other \(r1\) 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 \(n3\) nonintersecting diagonals. The number of triangulations in \(\mathcal{T}_n\) is \(C_{n2}\) the \((n2)\)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}_{n1}\)."
Similarly to the set situation, equality can be attained by fixing a diagonal that divides the ngon into a triangle and an \((n1\))gon, leaving \(\mathcal{T}_{n1}\) 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 bifixfree/unbordered.
Let \(\mu(W)\) be the length of the largest bifixfree factor of \(W\).
Trivially, \(\mu(W) \leq p(W)\).
Question: What wordlengths \(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.
Other Problem Sources
 Clark Kimberling, Unsolved Problems and Rewards (sequences)
 Craig Larson and Nico Van Cleemput, The Conjecturing Project (graphs)
 Dan Archdeacon, Problems in Topological Graph Theory
 David Eppstein, The Geometry Junkyard: Open Problems (discrete and computational geometry)
 Douglas B. West, Open Problems  Graph Theory and Combinatorics
 Douglas B. West, REGS in Combinatorics  Univ. of Illinois
 Egerváry Research Group, Egres Open (combinatorial optimization)
 Erik D. Demaine, Joseph S. B. Mitchell, and Joseph O'Rourke, The Open Problems Project (computational geometry and related fields)
 Jerry Spinrad, open (graphs, graph algorithms)
 Joshua Cooper, Combinatorial Problem I Like
 MathOverflow, Unanswered Questions
 The Online Encyclopedia of Integer Sequence, sequences with "conjecture" in their entry
 The Online Encyclopedia of Integer Sequence, sequences with "empirical" in their entry
 Open Problem Garden
 Peter J. Cameron, Problem pages index (combinatorics)
 Rocky MountainGreat Plains Graduate Research Workshop in Combinatorics, Problem Gardens
 Rutgers Center for Discrete Mathematics & Theoretical Computer Science, DIMACS Implementation Challenges
 S.C. Locke, Unsolved Problems (graphs, etc.)
 UCSD Mathematics Department, Erdős' Problems on Graphs
 University of Waterloo, CoWiki (words)
 Vašek Chvátal, Perfect Problems (perfect graphs)
 Wikipedia, List of unsolved problems in mathematics
 Wolfram MathWorld, Unsolved Problems