Problems

Assuming the Unique Games Conjecture, it is NP-hard to approximate MAX-3-CUT better than the Frieze-Jerrum semidefinite program does, and similarly for Quantum MAX-CUT: the sharpness question in the Khot-Kindler-Mossel-O'Donnell line,…

VibeMathed records no statement for this problem. See erdosproblems.com for the original.

Let A(n) be the least positive integer not dividing binom2nn. Erdos asked for the behaviour of A(n) for reasonable n. Under an explicit dyadic-regularity formalization of reasonable, the distribution is determined on dyadic intervals…

Krauth and Mezard predicted in 1989 that the storage capacity of the Ising perceptron at zero margin is an explicit constant α_⋆ ≈ 0.8330786. Ding and Sun proved the matching lower bound and Huang the upper bound, but each was conditional…

Under smoothness, positivity, decay and score assumptions, are all steady solutions of the Coulomb Vlasov-Maxwell-Landau system on T^3 × R^3 necessarily spatially uniform Maxwellians?

Huybrechts conjectured that for every Brauer class alpha on a hyperkahler variety X, the index divides the period raised to the power dim(X)/2, strengthening the usual period-index conjecture. Disproved on certain hyperkahler fourfolds, in…

For p ≥ 2, does Carbery's proposed many-function almost-orthogonality inequality hold with the pairwise overlap coefficients raised to the power 2 - and if not, what is the largest possible exponent?

Lassak conjectured that a reduced planar convex body of thickness Δ has area at most (π/4)Δ^2, the value for the disc. False: an explicit reduced body of thickness 1 has area 0.786215… > π/4 = 0.785398…, given by a closed-form support…

Is computing a Kemeny-optimal aggregate ranking NP-hard when the input consists of exactly three complete rankings? Hardness was known for every even n ≥ 4; three voters was the minimal open case, and n = 2 is polynomial-time solvable.

Talagrand's convexity problem asks whether a universal number of Minkowski sum operations turns any set of large Gaussian measure into one containing a convex body of comparable measure. It is equivalent to a question about subgaussian…

For a perfect field k and a representation-infinite finite-dimensional k-algebra A, the Auslander–Reiten quiver of A has infinitely many connected components. This establishes a conjecture of Auslander, Reiten and Smalø, for…

Mihail and Vazirani conjectured that the graph of every 0/1-polytope has edge expansion at least one. Disproved by a family of 0/1-polytopes whose edge expansion decreases exponentially in the dimension.

Friedland and coauthors proposed a quantum analogue of the p-Wasserstein distance and conjectured that, though only a semidistance in general, it is a true distance for a particular quantum cost matrix and for cost matrices near it. The…

Sabok asked whether the compact convex set S'(X) attached to a separable metric space of diameter at most one is always a simplex, and whether S'(U_1) is the Poulsen simplex. Both answers are negative, with obstructions already visible for…

Wu and Santhanam asked whether one can determine, from an increasing i.i.d. sample of binary random matrices, whether the unknown mean matrix is diagonalizable, while making only finitely many errors almost surely. Answered affirmatively…

VibeMathed records no statement for this problem. See erdosproblems.com for the original.

For the switch-walk-switch lamplighter walk on Z_2 wr T_d, prove the sharp asymptotic p_2n(e,e) = ρ_d^2n exp[-(π^2 (log(d-1))^2 + o(1)) n/log^2 n] with ρ_d = frac2√d-1d.

For a continuous bounded-variation path with signature g, logarithmic signature l and increment v, the modified Lyons–Sidorova conjecture predicts the structure of g when R(l)=∞. The paper proves it: g=1 when v=0, and otherwise a prefix α…

Kusner conjectured in 1983 that the maximum number of points in R^n that are pairwise at ℓ_p-distance one is exactly n+1 for every 2 < p < ∞, as in the Euclidean case. False: an explicit configuration of n+2 equilateral points exists for…

Are ICC property (T) groups remembered by their von Neumann algebras - if L(Γ) ≅ L(Λ) for such groups, must Γ ≅ Λ? A counterexample refutes Connes' conjecture that these groups are uniquely determined by their group von Neumann algebras.