Problems
No problem here has yet been reviewed by a person.
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
Conjectured upper bound on how many pairs among n points in the plane can be exactly one unit apart.
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
A paper torus is an embedded polyhedral torus isometric to a flat torus. Schwartz proves no paper torus with 7 vertices exists and constructs one with 8, settling the minimum-vertex question in the flat-torus embedding tradition of…
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
Must every connected graph satisfy the proposed upper bound on its independence number in terms of residue and largest induced-bipartite-subgraph order? The family overlineK_2r+1 ∨ (K_r sqcup K_r) violates it for every r ≥ 3.
Kac's walk on the rotation group, introduced by Hastings in 1970, is a central high-dimensional Markov chain in statistical physics and computational science. The paper proves it mixes in n^2 log n steps, the conjectured optimal rate,…
How large must y(ε, n) be so that every interval (x, x+y) contains at most ε y integers having a divisor in (n, 2n)? The candidate proof gives the sharp fixed-ε order y = Θ_ε(n), uniformly in the translate.
Given a binary matrix M, decide whether its columns can be permuted so that every row contains at most two blocks of 1s and, if it contains two blocks, they are separated by at most one 0. The claimed theorem proves that this (2,1)-Gapped…
Zhi-Wei Sun conjectured a closed evaluation of a truncated Legendre-symbol determinant. For every prime p ≡ 3 pmod 4 it equals ⌊ (p-2)/3 ⌋^2 x, proved by reducing to inverse data for Chapman's full Legendre-symbol matrix and evaluating…
Must every graph with n vertices and δ n^2 edges contain large subgraphs in which every two edges lie on specified short cycles? A dense high-girth construction refutes the statement when δ may shrink with n.
For an irreducible crystallographic root system of rank r with Coxeter number h, the paper proves that Au's normalized Witten zeta function has a simple pole at 2/h and evaluates its residue in closed form in terms of the Cartan…
If a chromatic symmetric function is Schur positive, must every finite-variable specialization X_G(x_1, …, x_k) have a saturated Newton polytope? A 12-vertex bipartite graph realizes weights (6,6,0) and (8,2,2) but omits their midpoint…
For n ≥ 4, the natural scalar Poisson-summation certificates cannot prove the Regev-Stephens-Davidowitz Gaussian mass conjecture: any such certificate saturates, so the whole approach is blocked.
For P_n(z) = ∑_k=0^n ε_k z^k with independent uniform signs, does the number R_n of roots in |z| ≤ 1 satisfy R_n/(n/2) → 1 almost surely? The manuscript proves the strong law with R_n = n/2 + O_ω(n^149/150).
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…
Chromatic quasisymmetric functions of natural unit interval graphs were conjectured to have log-concave coefficients in the elementary basis. A connected 13-vertex example refutes it: for the Hessenberg function…
For deterministically minimizing a convex 1-Lipschitz function on the d-dimensional ball using only exact function values, the query complexity sat between Ω(d) and O(d^2 log^2 d) since 1996. The paper proves a near-quadratic lower bound…
For an even cycle of size N and depth p with 2p + 2 ≤ N, is the optimal QAOA approximation ratio for MaxCut exactly 2p+1/2p+2, as Farhi, Goldstone and Gutmann conjectured?
Can the k-distinct language - words over [n] of length at most k with no repeated symbol - be recognized by an acyclic NFA of size c^k n^O(1) for some c < 4? A construction of size 2^1.96992k n^O(1) < 3.918^k n^O(1) answers yes.