Open problems, attacked by machine
A journal of what was proved, measured, refuted — and what is still open
Each entry is one problem. Every claim is labelled by what it actually is, because the distinction between a proof, a measurement and a plausible guess is the only thing that makes a record like this worth keeping.
The index is the community database of Erdős's problems. Of the 650 open ones, 43 carry a curated flag saying a finite object would settle them — a counterexample, a witness, or a decision on a bounded case. Those are the only ones a computer can honestly attack, so those are the ones ranked here, by whether the search space is actually reachable rather than by how famous the problem is.
How problems are picked
Three flags in the database mark a problem as finitely settleable.
Open, but a finite counterexample would disprove it. The mode where search wins: one object ends the question.
Open, but a finite example would prove it. Rarer and more valuable — the search either finds the thing or it doesn't.
Each fixed case is a finite decision, though the family is infinite. Progress means settling cases and looking for the pattern.
Ranking then asks one question: is the space reachable with a SAT solver, exhaustive enumeration and sixteen cores? Fame is not a criterion. The historical precedents for this style — Boolean Pythagorean triples, Keller's conjecture, Schur number five — were all won by encoding a finite case well, not by attacking a famous one.
Problem · Erdős 835 · flagged verifiable · open since 1974
Colouring the k-subsets of a 2k-set
Is there a k > 2 such that the k-subsets of
{1,…,2k} can be coloured with k+1 colours so that every
(k+1)-subset sees all k+1 colours among its k-subsets?
First move: it is a chromatic number
A (k+1)-set has exactly k+1 many k-subsets, so
"all k+1 colours appear" simply means they are pairwise distinct. Two
k-subsets share a (k+1)-set precisely when they meet in
k−1 points. So the question is whether the Johnson graph
J(2k,k) is (k+1)-colourable.
The k-subsets inside a fixed (k+1)-set are pairwise adjacent,
so ω = k+1 and χ ≥ k+1 always. The problem asks exactly when the
clique bound is tight.
Second move: it is a Steiner system
A colour class is an independent set, so its blocks have pairwise distinct
(k−1)-subsets, giving α ≤ Catalan(k) — with equality precisely
when every (k−1)-subset lies in exactly one block. That is a Steiner system
S(k−1, k, 2k). And χ = k+1 forces every class to be maximum.
Erdős 835 holds at k if and only if a large set of Steiner
systems S(k−1, k, 2k) exists — a partition of all
C(2k,k) blocks into k+1 disjoint systems.
What that settles
Divisibility for S(k−1,k,2k) holds iff k+1 is
prime (verified to k < 300), which eliminates most k
outright. The rest:
| k | Steiner system | Exists? | Large set? | 835 |
|---|---|---|---|---|
| 2 | S(1,2,4) | yes, 2 blocks | yes — 1-factorization of K₄ | holds (known) |
| 3 | S(2,3,6) | no (6 ≢ 1,3 mod 6) | — | fails |
| 4 | SQS(8) | yes, 14 blocks | no | fails |
| 5 | S(4,5,10) | no | — | fails |
| 6 | S(5,6,12) | yes, 132 blocks | no | fails |
| 7,8,9 | — | divisibility fails | — | fails |
All 5040 Steiner systems S(5,6,12) enumerated by exact
cover — the count checks independently against 12!/|M₁₂| = 5040. Their
disjointness graph has 362 880 edges, and an exhaustive search over 367 920 nodes finds
no 7-clique. Seven pairwise disjoint systems would cover
7 × 132 = 924 = every hexad, so no large set exists.
The independence numbers α(J(2k,k)) computed by SAT are
2, 4, 14, 36 for k = 2…5. These equal Catalan(k)
exactly when the Steiner system exists (2, 14) and fall short otherwise (4 < 5,
36 < 42) — which is what the reduction predicts, computed by a different route.
k ≥ 10 with k+1 prime requires a Steiner system with
t = k−1 ≥ 9. No nontrivial Steiner system with t ≥ 6 is
known to exist for any parameters. So this problem — listed as one a finite
example could settle — in fact implies something far beyond current knowledge.
This is a reduction, not a solution. It settles every case up to k = 9 and explains all of them by one mechanism.
The queue
The other 42 flagged problems, untouched. Each gets its own section here when it is worked.
| № | Flag | Prize | Statement |
|---|---|---|---|
| #7 | VERI | Is there a distinct covering system all of whose moduli are odd? | |
| #19 | DECI | $500 | If $G$ is an edge-disjoint union of $n$ copies of $K_n$ then is $\chi(G)=n$? |
| #23 | FALS | Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges? | |
| #64 | FALS | $1000 | Does every finite graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$? |
| #97 | FALS | $100 | Does every convex polygon have a vertex with no other $4$ vertices equidistant from it? |
| #106 | FALS | Draw $n$ squares inside the unit square with no common interior point. Let $f(n)$ be the maximum possible sum of the side-lengths of the squares. Is $f(k^2+1)=k$? | |
| #107 | FALS | $500 | Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^2$, no three on a line, contain $n$ points which form the vertices of a convex $n$-gon. Prove that $f(n)=2^{n-2}+1$. |
| #114 | FALS | $250 | If $p(z)\in\mathbb{C}[z]$ is a monic polynomial of degree $n$ then is the length of the curve $\{ z\in \mathbb{C} : \lvert p(z)\rvert=1\}$ maximised when $p(z)=z^n-1$? |
| #128 | FALS | $250 | Let $G$ be a graph with $n$ vertices such that every induced subgraph on $\geq \lfloor n/2\rfloor$ vertices has more than $n^2/50$ edges. Must $G$ contain a triangle? |
| #167 | FALS | If $G$ is a graph with at most $k$ edge disjoint triangles then can $G$ be made triangle-free after removing at most $2k$ edges? | |
| #242 | FALS | For every $n>2$ there exist distinct integers $1\leq x<y<z$ such that\[\frac{4}{n} = \frac{1}{x}+\frac{1}{y}+\frac{1}{z}.\] | |
| #287 | FALS | Let $k\geq 2$. Is it true that, for any distinct integers $1<n_1<\cdots <n_k$ such that\[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\]we must have $\max(n_{i+1}-n_i)\geq 3$? | |
| #307 | VERI | Are there two finite sets of primes $P,Q$ such that\[1=\left(\sum_{p\in P}\frac{1}{p}\right)\left(\sum_{q\in Q}\frac{1}{q}\right)?\] | |
| #364 | VERI | Are there any triples of consecutive positive integers all of which are powerful (i.e. if $p\mid n$ then $p^2\mid n$)? | |
| #366 | VERI | Are there any $2$-full $n$ such that $n+1$ is $3$-full? That is, if $p\mid n$ then $p^2\mid n$ and if $p\mid n+1$ then $p^3\mid n+1$. | |
| #375 | FALS | Is it true that for any $n,k\geq 1$, if $n+1,\ldots,n+k$ are all composite then there are distinct primes $p_1,\ldots,p_k$ such that $p_i\mid n+i$ for $1\leq i\leq k$? | |
| #398 | FALS | Are the only solutions to\[n!=x^2-1\]when $n=4,5,7$? | |
| #458 | FALS | Let $[1,\ldots,n]$ denote the least common multiple of $\{1,\ldots,n\}$. Is it true that, for all $k\geq 1$,\[[1,\ldots,p_{k+1}-1]< p_k[1,\ldots,p_k]?\] | |
| #475 | DECI | Let $p$ be a prime. Given any finite set $A\subseteq \mathbb{F}_p\backslash \{0\}$, is there always a rearrangement $A=\{a_1,\ldots,a_t\}$ such that all partial sums $\sum_{1\leq k\leq m}a_{ | |
| #488 | FALS | Let $A$ be a finite set and\[B=\{ n \geq 1 : a\mid n\textrm{ for some }a\in A\}.\]Is it true that, for every $m>n\geq \max(A)$,\[\frac{\lvert B\cap [1,m]\rvert }{m}< 2\frac{\lvert B\cap [1,n | |
| #506 | DECI | What is the minimum number of circles determined by any $n$ points in $\mathbb{R}^2$, not all on a circle? | |
| #547 | DECI | If $T$ is a tree on $n$ vertices then\[R(T) \leq 2n-2.\] | |
| #548 | FALS | Let $n\geq k+1$. Every graph on $n$ vertices with at least $\frac{k-1}{2}n+1$ edges contains every tree on $k+1$ vertices. | |
| #551 | DECI | Prove that\[R(C_k,K_n)=(k-1)(n-1)+1\]for $k\geq n\geq 3$ (except when $n=k=3$). | |
| #556 | DECI | Let $R_3(G)$ denote the minimal $m$ such that if the edges of $K_m$ are $3$-coloured then there must be a monochromatic copy of $G$. Show that\[R_3(C_n) \leq 4n-3.\] | |
| #580 | DECI | Let $G$ be a graph on $n$ vertices such that at least $n/2$ vertices have degree at least $n/2$. Must $G$ contain every tree on at most $n/2$ vertices? | |
| #583 | FALS | Every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint paths. | |
| #617 | FALS | Let $r\geq 3$. If the edges of $K_{r^2+1}$ are $r$-coloured then there exist $r+1$ vertices with at least one colour missing on the edges of the induced $K_{r+1}$. | |
| #628 | FALS | Let $G$ be a graph with chromatic number $k$ containing no $K_k$. If $a,b\geq 2$ and $a+b=k+1$ then must there exist two disjoint subgraphs of $G$ with chromatic numbers $\geq a$ and $\geq b | |
| #647 | VERI | £25 | Let $\tau(n)$ count the number of divisors of $n$. Is there some $n>24$ such that\[\max_{m<n}(m+\tau(m))\leq n+2?\] |
| #672 | VERI | Can the product of an arithmetic progression of positive integers $n,n+d,\ldots,n+(k-1)d$ of length $k\geq 4$ (with $(n,d)=1$) be a perfect power? | |
| #699 | FALS | Is it true that for every $1\leq i<j\leq n/2$ there exists some prime $p\geq i$ such that\[p\mid \textrm{gcd}\left(\binom{n}{i}, \binom{n}{j}\right)?\] | |
| #723 | FALS | If there is a finite projective plane of order $n$ then must $n$ be a prime power? A finite projective plane of order $n$ is a collection of subsets of $\{1,\ldots,n^2+n+1\}$ of size $n+1$ s | |
| #742 | DECI | Let $G$ be a graph on $n$ vertices with diameter $2$, such that deleting any edge increases the diameter of $G$. Is it true that $G$ has at most $n^2/4$ edges? | |
| #743 | FALS | Let $T_2,\ldots,T_n$ be a collection of trees such that $T_k$ has $k$ vertices. Can we always write $K_n$ as the edge disjoint union of the $T_k$? | |
| #779 | FALS | Let $n> 1$ and $p_1<\cdots<p_n$ denote the first $n$ primes. Let $P=\prod_{1\leq i\leq n}p_i$. Does there always exist some prime $p$ with $p_n<p<P$ such that $P+p$ is prime? | |
| #848 | DECI | Is the maximum size of a set $A\subseteq \{1,\ldots,N\}$ such that $ab+1$ is never squarefree (for all $a,b\in A$) achieved by taking those $n\equiv 7\pmod{25}$? | |
| #982 | FALS | If $n$ distinct points in $\mathbb{R}^2$ form a convex polygon then some vertex has at least $\lfloor \frac{n}{2}\rfloor$ different distances to other vertices. | |
| #993 | FALS | The independent set sequence of any tree or forest is unimodal. In other words, if $i_k(G)$ counts the number of independent sets of vertices of size $k$ in a graph $G$, and $T$ is any tree | |
| #1020 | FALS | Let $f(n;r,k)$ be the maximal number of edges in an $r$-uniform hypergraph which contains no set of $k$ many independent edges. For all $r\geq 3$,\[f(n;r,k)=\max\left(\binom{rk-1}{r}, \binom | |
| #1041 | FALS | Let $f(z)=\prod_{i=1}^n(z-z_i)\in \mathbb{C}[z]$ with $\lvert z_i\rvert < 1$ for all $i$. Must there always exist a path of length less than $2$ in\[\{z: \lvert f(z)\rvert < 1\}\]which conne | |
| #1082 | FALS | Let $A\subset \mathbb{R}^2$ be a set of $n$ points with no three on a line. Does $A$ determine at least $\lfloor n/2\rfloor$ distinct distances? In fact, must there exist a single point from |