Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Teschner conjectured that every finite simple graph G with at least one edge satisfies b(G) ≤ 3/2Δ(G), where b(G) is the bondage number and Δ(G) is the maximum degree. Yavari gives a connected cubic bipartite graph on 18 vertices with…
Around the Kemeny median problem, which stays open for m=3 and m=5 voters, the paper refutes three conjectures on tournament inducibility: both conjectures of Milosz, Hamel and Pierrot (the 3-cycle extension for odd m≥5, and FAS=HS_3 at…
For the Erdős–Pomerance functions F(n) and h_P(n) counting how many consecutive integers are needed to contain a distinct multiple of each integer, respectively prime, up to n, the paper proves F(n) ≥ h_P(n) ≥ nexp((log 2/2 - o(1))log…
Is the chromatic symmetric function X_G Schur positive for every claw-free graph G? Two explicit 12-vertex line graphs have Schur coefficients -64 and -40 at s_(3,3,3,3).
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
Kinoshita conjectured that every embedded projective plane in S^4 is reducible. False: an irreducible embedded projective plane exists in S^4. The construction also answers both parts of Problem 4.37 of the Kirby problem list.
In the list update problem, is the simple transposition rule optimal under IID requests? The question traces to Rivest's 1976 study of self-organizing lists. The paper proves transposition is within a small constant factor of the optimal…
22 conjectures of Cohen about cyclic numbers (integers with gcd(n, φ(n)) = 1) settled at once - 16 proved, 6 disproved - together with a complete resolution of a related OEIS problem on sequences whose running averages are Fibonacci…
Erdos Problem #593 asks which finite triple systems occur in every uncountably chromatic triple system. The answer is exactly the class generated from private-vertex expansions of finite bipartite graphs by finite disjoint unions and…
Treglown conjectured, in a complementary form, that for every positive integer k every digraph D with mind^+(v), d^-(v) ≤ k-1 for all v has an equitable acyclic k-colouring. This implies the acyclic colouring versions of the…
Whether perfectly complete quantum key agreement can be built from quantumly secure one-way functions in a black-box way. It cannot: for any protocol where Alice and Bob exchange only classical messages, make at most q_A and q_B quantum…
Can a Cohn-Elkies auxiliary function certify the best known sphere packing in dimension 36 as optimal? No. An explicit dual-feasible point for the Cohn-Elkies linear program, built from weight-18 modular forms for Γ_0(24), shows the…
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
For single-source unsplittable flow, every fractional flow can be rounded to an unsplittable flow whose cost is no higher than the fractional cost, while each arc's load is exceeded by at most the maximum demand. (The cost version of…
Let n_1<n_2<… be a lacunary sequence of integers and f∈ L^2([0,1]) with nth Fourier partial sum f_n. Is there an absolute constant C>0 such that if | f-f_n|_2 ≪ (logloglog n)^-C then 1/N∑_k≤ Nf(α n_k)→∫_0^1 f for almost every α? A preprint…
Let n_k be the least integer greater than 2k for which ∏_i=1^k (n_k - i) has no prime factor in (k, 2k). How rapidly must n_k grow?
A Banach space is primary if in every decomposition into two complemented subspaces one summand is isomorphic to the whole. Lechner, Motakis, Müller and Schlumprecht identified the primariness of L_p(L_1) as a prominent remaining open…
The realisation problem asks which unital Banach algebras arise as the Calkin algebra B(X)/K(X) of some Banach space. Recorded in Tarbard's thesis and studied by Horváth and Kania. The paper exhibits a unital Banach algebra that cannot be…
Vinzant conjectured, in a form later restated by Bandeira, that the 4M-4 threshold for injective complex phase retrieval is sharp. Part (1) holds: for A ∈ C^N × M with N = 4M-5 and i.i.d. standard complex Gaussian entries, the phase…
Must every sufficiently large node set admit bounded labels that force any polynomial fitting almost all labels at degree below (1+ε)n to have arbitrarily large uniform norm? Claimed via Beurling density for Bernstein spaces.