Hadwiger conjecture
A graph that needs many colors is predicted to contain a correspondingly large complete graph after edges are contracted and vertices removed.
Combinatorics
Within Combinatorics · Search all subjects
Hadwiger–Nelson problem
How many colors are needed to color every point of the plane so that points exactly one unit apart always have different colors?
Hadamard matrix conjecture
Square matrices of plus and minus ones can have mutually orthogonal rows. The conjecture predicts one for every size divisible by four.
Union-closed sets conjecture
If a finite collection of sets contains every union of two of its members, must some element occur in at least half the sets?
Lonely runner conjecture
Runners start together on a circular track at different constant speeds. Each is predicted to eventually be well separated from all the others.
Erdős–Hajnal conjecture
Forbidding one fixed induced graph is predicted to force a large group of vertices that are all connected to each other or all disconnected.
Diagonal Ramsey numbers
Color every edge of a complete graph red or blue. How many vertices force k vertices whose connecting edges all have the same color?
Graceful tree conjecture
Every tree is predicted to admit vertex numbers whose differences across edges are all distinct and fill the required range.
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?
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?
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?
Hadwiger’s illumination conjecture
Can every convex body in n dimensions have its entire boundary illuminated from at most 2ⁿ directions?
Kissing number in five dimensions
How many equal five-dimensional balls can touch one central ball without overlapping each other?
Singmaster’s conjecture
Is there a fixed limit on how often any number greater than one can appear in Pascal’s triangle?
Erdős–Ulam problem
Can points be dense throughout the plane while every distance between two of them is rational?
Moser’s convex worm problem
What is the smallest-area convex region that can contain every planar curve of length one after repositioning it?
Minimum opaque barrier for a square
How little total barrier length can intercept every straight line that passes through a unit square?
Seymour’s second-neighborhood conjecture
Must a directed graph without two-way edges have a vertex reaching at least as many new vertices in two steps as in one?
Borsuk’s conjecture in dimension four
Can every bounded four-dimensional set be split into five pieces of strictly smaller diameter?
Small-Set Expansion hypothesis
Is it computationally hard to distinguish a graph with a small nearly isolated set from one where every equally small set strongly expands?
Densest-k-subgraph approximation
Can a fast algorithm always choose k vertices spanning within a fixed factor of the largest possible number of edges?