Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
- 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…
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
A convex body is in Faber-Krahn position if it minimizes the first Dirichlet eigenvalue within its volume-preserving linear orbit. The paper proves this position is unique up to orthogonal transformations, answering a question of…
Is the depth of the mod-p cohomology ring of every finite group realized as the dimension of one of its associated primes? For G = SmallGroup(128, 859) over overlineF_2 the ring has depth 2 while every associated-prime quotient has…
Does the natural trace estimate hold for kinetic energy spaces in the unrestricted Gaussian velocity model on bounded domains (Question 1.8 of Albritton, Armstrong, Mourrat and Novack)? No: for each 1 ≤ p < 2 there are counterexamples on…
How many pairwise non-overlapping infinite circular cylinders of unit radius can simultaneously touch a unit ball? Kuperberg conjectured in 1990 that the maximum is six.
If a finite graph has girth at least five, must its minimum dual degree satisfy δ^*(G) ≤ -∂_n(G), where ∂_n(G) is the smallest eigenvalue of its distance matrix? The Hoffman-Singleton graph violates it: dual degree 7 against eigenvalue…
Zhu, Gyori, He, Lv, Salia and Xiao conjectured the maximum number of copies of a fixed cycle in an n-vertex graph of bounded circumference, attained by the join of a clique with an independent set. For every fixed s ≥ 3 and L ≥ 2s+2 and…
Erdős and Graham asked whether binomnk with 1 ≤ k ≤ n/2 must always have a divisor ≤ n that is close to n, meaning bigger than a fixed constant times n. Settled in both directions: true when k is large enough as a function of n, but false…
Every finite connected simple graph G satisfies α(G)≥ r(G)+ln(ρ(G)), where α(G) is the independence number, r(G) is the radius, and ρ(G) is the minimum number of pairwise vertex-disjoint paths whose vertices cover V(G).
Monical, Tokcan and Yong conjectured that Schubitopes, the generalized permutahedra arising as Newton polytopes of Schubert polynomials and of Demazure characters of GL_n, are Ehrhart positive. Disproved by an explicit Schubitope whose…
Among all nonconstant monic polynomials f whose roots lie in [-1, 1], determine inf_f |x ∈ R : |f(x)| < 1|.
For a bipartite graph without isolated vertices and with a unique minimum dominating set, does the proposed function m(n, γ) bound the number of edges whenever γ ≥ 2 and n ≥ 3γ? A 13-vertex bipartite graph with 22 edges exceeds the…
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,…
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…
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…
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…