My Favorite Open Problems in Mathematics
... 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.
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 On-line Encyclopedia of Integer Sequence,
sequences with "conjecture" in their entry
-
The On-line Encyclopedia of Integer Sequence,
sequences with "empirical" in their entry
-
Open Problem Garden
-
Peter J. Cameron,
Problem pages index
(combinatorics)
-
Rocky Mountain-Great 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