Nonnegative inverse eigenvalue problem
Which lists of numbers can be the eigenvalues of a square matrix whose entries are all nonnegative?
Explore all problems.
Rota’s basis conjecture
Given n bases of an n-dimensional space, can their vectors always be rearranged into n new bases, each taking one vector from every original base?
Caccetta–Häggkvist conjecture
If every vertex of a directed graph points to many others, must the graph contain a correspondingly short directed cycle?
Falconer distance conjecture
A sufficiently large fractal set is predicted to determine a set of pairwise distances with positive ordinary length.
Sphere packing in five dimensions
How densely can identical nonoverlapping spheres fill five-dimensional Euclidean space?
Graph reconstruction conjecture
Delete each vertex of a graph in turn and keep the resulting graphs without labels. Does this collection determine the original graph?
Erdős–Szekeres convex polygon conjecture
How many points in the plane guarantee a convex polygon with a specified number of vertices? The proposed exact threshold remains unproved.
Erdős–Straus conjecture
Can every fraction 4/n, with n at least 2, be written as the sum of three reciprocals of positive integers?
Legendre’s conjecture
Must a prime number occur between n squared and the next integer’s square, however large n becomes?
Artin’s primitive root conjecture
For a fixed eligible integer, how often do its powers generate every nonzero residue modulo a prime?
Leopoldt’s conjecture
Do the independent units of a number field remain independent when measured using p-adic arithmetic?
Sarnak’s conjecture
Does the arithmetic Möbius sequence average to zero against every sequence generated by a system with zero topological entropy?
Kakeya conjecture
A set can contain a unit line segment pointing in every direction and still have zero volume. Must it nevertheless have full fractal dimension?
Turán’s tetrahedron problem
How many triples can a large collection of points contain while never containing all four triples on any four points?
Tutte’s five-flow conjecture
Can every graph without a bridge carry a balanced flow that never vanishes and uses only four positive magnitudes?
Erdős–Gallai cycle decomposition conjecture
Can the edges of any graph be split into only a constant times its number of vertices worth of cycles and individual edges?
Euler–Mascheroni constant
The difference between the harmonic series and a logarithm approaches a famous constant. Is that constant a ratio of integers?
Erdős–Moser equation
Can a power of an integer equal the sum of the same powers of every smaller positive integer, apart from 1 + 2 = 3?
Mersenne primes
Do prime numbers of the form 2 to a prime exponent, minus 1, continue forever?
3SUM hypothesis
Can finding three integers with a specified additive relation be done faster than essentially quadratic time?
Online matrix–vector multiplication
Can a fixed Boolean matrix answer a sequence of arriving vectors in truly subcubic total time when each answer is needed before the next vector arrives?
Log-rank conjecture
Does the linear-algebraic rank of a Boolean table control how many bits two people must exchange to evaluate an entry?
Minimum Circuit Size Problem
Given every output of a Boolean function, how hard is it to decide whether a small circuit can produce that table?
Frege proof lower bounds
Can one exhibit propositional truths whose proofs must be superpolynomially long even in a flexible standard deductive system?