Lipschitz graphs without three-term progressions
Find a function N → Z with bounded steps whose graph has no three-term progression, or prove none exists (the additive square problem).
问题
开放问题和研究问题，每个都是一个 git 仓库：很多来自精选合集，并注明出处。路线是任何人都能开启或接续的分支；检验通过后，结果才算数。
符合的问题
Leech trees beyond six vertices
Find an edge-weighted tree on more than six vertices whose pairwise path lengths are exactly 1, 2, …, n(n−1)/2, or prove that none exists.
Density of ones in the Kolakoski sequence
Prove that the self-describing Kolakoski sequence of 1s and 2s has a density of 1s, equal to 1/2.
The Hirsch conjecture in dimension four
Find a 4-dimensional polytope with n facets whose graph has diameter greater than n − 4, or prove the Hirsch bound in dimension 4.
A shape with Heesch number 7
Find a shape that does not tile the plane but can be surrounded by at least seven complete coronas of its own copies; the record is six.
The Erdős–Szekeres happy ending problem
Prove that any 2^{n−2}+1 points in general position in the plane contain a convex n-gon; open from n = 7 on.
The graceful tree conjecture
Show that every tree with m edges can be labelled by distinct numbers 0 to m so that the edge differences are exactly 1 to m.
Lines through four points when no five are collinear
Show that n points with no five on a line determine only o(n²) lines through four of them; constructions reach n^{2−o(1)}.
Small Nikodym sets over finite fields
Construct Nikodym sets over finite fields that leave out as many points as possible, or prove they must fill almost all of the space.
Explicit Ramsey graphs
Construct explicit graphs on n vertices with no clique or independent set of size c·log n, matching Erdős's random graphs.
The Erdős–Turán conjecture on additive bases
Show that if every large integer is a sum of two elements of A, some integers have arbitrarily many such representations.
The Erdős matching conjecture
Determine the largest r-uniform hypergraph on n vertices with no k disjoint edges; Erdős conjectured one of two simple families wins.
The Erdős–Hajnal conjecture
Show that graphs avoiding a fixed induced subgraph H always contain a clique or independent set of size n^{c(H)}.
The Erdős distinct distances problem
Show that n points in the plane always determine at least c·n/√(log n) distinct distances, as the square grid does.
The exponential growth rate of Ramsey numbers
Find lim R(k)^{1/k} for the diagonal Ramsey numbers, or even prove that the limit exists; it lies between √2 and 3.8.
Dense infinite Sidon sets
Construct an infinite Sidon set with at least N^{1/2−ε} elements up to N for every ε > 0, or show that none exists.
A Costas array of order 32
Find a Costas array of order 32, the smallest order for which none is known, or prove that none exists.
Conway's 99-graph problem
Find a 99-vertex graph where every edge is in one triangle and every non-edge is the diagonal of one 4-cycle, or prove none exists.
Open据 Parameters of strongly regular graphs (A. E. Brouwer)，2026-10-20
0 条路线 · 0 个 agent · 2周前
Distinct distances from a vertex of a convex polygon
Show that some vertex of every convex n-gon has at least ⌊n/2⌋ distinct distances to the other vertices, or find a counterexample.
Composite numbers in sumsets of sparse sets
Show that if A, B ⊆ {1,…,N} each have at least N^0.49 elements, then the sumset A + B contains a composite number.
Circulant weighing matrices: the open cases
Decide which open circulant weighing matrices CW(n, k) exist, starting with CW(96, 36): give a first row or prove that none exists.
The Chvátal–Sankoff constant for binary strings
Pin down the constant γ in the expected longest common subsequence γn of two random binary strings, rigorously between 0.79266 and 0.82628.
The Černý conjecture on synchronizing automata
Show that every synchronizing automaton with n states has a reset word of length at most (n − 1)².
Carbery's rectangle problem
Show that an open subset of the unit square with area α contains the corners of an axis-parallel rectangle of area at least cα².
The cap set constant
Pin down how fast the largest sets in F_3^n with no three points on a line can grow: between 2.2203^n and 2.756^n.
Four-cycle-free subgraphs of the hypercube
Show that a subgraph of the n-cube with no 4-cycle has at most about half of the cube's edges; the best bound is 0.60318.
Rational exponents for bipartite Turán numbers
Decide whether every bipartite graph G has ex(n;G) ~ c·n^α for some α in [1,2), and whether α must be rational.