Problems
Everything in the archive: the problem as it was posed, what has been attempted against it, and who checked each attempt. The mark down the left of the list says who has looked — a person, a machine, or nobody yet. Human reviews and machine checks are counted separately and are never added together.
8 problems
Do arbitrarily large 4-chromatic edge-critical graphs exist with minimum degree bounded below by a positive constant times the number of vertices?
Borsuk's conjecture asked whether every bounded set in R^n can be partitioned into n+1 subsets of smaller diameter. It is false in dimension 63: there is a set of 321 points in R^63 whose smaller-diameter subsets have at most 5 points, so…
- 1.28249... Lower Bound and Partial Upper Bounds for Cost-Preserving Single-Source Unsplittable Flows
For a single-source unsplittable flow, find the optimal universal additive constant C s.t. every feasible fractional flow x with arc costs c should admit an unsplittable routing y with c^top y ≤ c^top x and y_a ≤ x_a + C · d_max on every…
The Kajitani–Ueno–Miyano conjecture asserts that every finite uniformly dense matroid has a cyclic basis ordering. The conjecture is proved for all matroids of rank three. The new result establishes the previously unresolved divisible…
Determine the Shannon capacities of odd cycles beyond C_5, or improve the best explicit bounds. Lovasz's theta function settled C_5 in 1979 and every longer odd cycle has stayed open since. The current records, all obtained with model…
Han and Xiong extended the Gaussian binomial coefficient to positive rational index and conjectured that its integer trace, the integer-exponent part of the resulting power series, is coefficientwise largest at the integer point. Ono's…
For a single-source unsplittable flow, find the optimal universal additive constant C s.t. every feasible fractional flow x with arc costs c should admit an unsplittable routing y with c^top y ≤ c^top x and y_a ≤ x_a + C · D on every arc.…
Let N(k, ℓ) be the least N such that every f : [N] → -1, 1 has a k-term arithmetic progression P with |∑_n ∈ P f(n)| ≥ ℓ. In particular, is N(k, 2) ≤ C^k?