Problems
No problem here has yet been reviewed by a person.
Erdos and Hajnal asked whether h_r(G) = maxχ(H) : H ⊆ G, girth(H) ≥ r tends to infinity as χ(G) does, for every fixed r ≥ 4. It does in every fixed polynomial edge-density regime.
A subset A of the pointwise-ordered cube [0,1]^n is a k-antichain when it meets every chain in at most k points. The conjecture concerns the largest possible (n-1)-dimensional Hausdorff measure of such a set; it is settled here, following…
The Huneke–Wiegand Conjecture: Let R be a one-dimensional Gorenstein local domain, and let M be a finitely generated, non-zero, torsion-free R-module. If the tensor product M ⊗_R M^* is torsion-free, then M is a projective (hence free)…
For an arrangement of n hyperplanes in P^3_C with ℓ intersection lines and p intersection points where at least three hyperplanes meet, the refined form of Purdy's inequality expects p - ℓ + n + 2 ≥ 0. An explicit arrangement built from…
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
How many nondegenerate equilibrium points can the potential of three positive point charges have? Gabrielov, Novikov and Shapiro had proved at most 12, and observed that their method would give 6 if an auxiliary polynomial system had at…
Does every instance of indivisible goods with additive valuations admit a balanced allocation (any two bundles differing in size by at most one) that is simultaneously envy-free up to one good (EF1) and fractionally Pareto optimal (fPO)?…
Aldroubi, Cabrelli, Krishtal and Molter conjectured that for a bounded normal operator T and any vector g, the normalized orbit T^k g / |T^k g| : k ≥ 0 is never a frame. It can be: an explicit construction produces a normalized orbit that…
Kotzig conjectured that for every even n ≥ 4 the complete graph K_n decomposes into n-1 perfect matchings such that every pair of them forms a Hamilton cycle. An asymptotic version holds: K_n decomposes into n-1 perfect matchings of which…
Simon conjectured that every skeleton of a simplex is extendably shellable. False: for every d ≥ 3 there is a pure d-dimensional shellable simplicial complex that is not shelling completable.
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
Englert and Rehacek conjectured which measurement is globally information-optimal for an ensemble of equiangular equiprobable pure states. Their conjecture holds, via the remaining entropy inequalities of Holevo and Utkin.
Can an S-decoding polynomial modulo a suitable product of k primes attain the lower-bound minimum of k + 1 nonzero coefficients? A construction matches the bound for special products of k primes, yielding exponentially fewer-server PIR.
Is the closest vector problem NP-hard to approximate within polynomial factors n^c? Yes for some c > 0: hardness of approximation reaches polynomial factors, with consequences for decoding and related lattice problems - a foundational…
In the circle of Kummer's regular primes and Vandiver's conjecture, the paper proves that almost all primes are partially regular, yielding a partial Vandiver theorem for a density-one set of primes, with consequences for Kubota-Leopoldt…
Dittert's conjecture asserts that among nonnegative n× n matrices whose entries sum to n, the functional φ(A)=∏_i r_i+∏_j c_j-per(A) is uniquely maximized by J_n/n. The paper proves the case n=16 which, with Pang's result for n≥17,…
Does there exist a good pairwise-coprime sequence u_n with ∑ 1/u_n < ∞ and polynomial growth? What if one only requires u_n ≤ e^o(n)?
Anari, Charikar and Ramakrishnan asked whether every fractional perfect matching admits a perfect matching that is α-thin with respect to it, meaning it crosses every cut at most α times the fractional amount. Resolved up to…
For every connected graph, is the deviation of its adjacency eigenvalues at most its order divided by its average distance? Exact lollipop-graph certificates refute the inequality when deviation means population standard deviation, under…
An ℓ-Oddtown is a family of subsets of an n-element set whose set sizes are not divisible by ℓ while all pairwise intersection sizes are. Berlekamp and Graver showed the maximum size is n for prime ℓ, Babai and Frankl extended this to…