ProbXiv
Explorersign in

problems

Leaderboard716 problems
601–620 of 716 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…

    disproved

    1 attempt · a verdict recorded from elsewhere

  • Tournaments Determined by Three and Five VotersMilosz, Hamel and Pierrot; Shepard

    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…

    disproved

    1 attempt

  • Improved Bounds for Distinct Multiples in IntervalsScott Duke Kominers; functions introduced by Erdős and Pomerance

    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…

    disproved

    1 attempt

  • 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).

    disproved

    1 attempt

  • Erdős Problem #851Paul Erdős, 1985

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

    solved

    1 attempt · a verdict recorded from elsewhere

  • The Kinoshita Conjecture and Kirby Problem 4.37Shin'ichi Kinoshita; Problem 4.37 of the Kirby list

    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.

    disproved

    1 attempt

  • Transposition is Nearly Optimal for IID List UpdateRonald Rivest (transposition heuristic), 1976

    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…

    solved

    1 attempt

  • Cohen's 22 Conjectures on Cyclic NumbersCohen (OEIS conjectures); Fried

    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…

    retracted

    1 attempt

  • 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…

    solved

    1 attempt

  • 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…

    solved

    1 attempt

  • 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…

    solved

    1 attempt

  • 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…

    disproved

    1 attempt

  • Erdős Problem #896Paul Erdős, 1972

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

    solved

    1 attempt · a verdict recorded from elsewhere

  • Dinitz-Garg-Goemans ConjectureYefim Dinitz, Naveen Garg, Michel Goemans, 1999

    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…

    disproved

    1 attempt

  • Erdős Problem #996Paul Erdős, 1964

    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…

    candidate

    1 attempt

  • 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?

    partial

    1 attempt

  • Primariness of the Mixed-Norm Space L_p(L_1)Lechner, Motakis, Müller and Schlumprecht

    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…

    solved

    1 attempt

  • 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…

    solved

    1 attempt

  • Vinzant's Conjecture on Phase Retrieval InjectivityCynthia Vinzant; restated by Afonso S. Bandeira

    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…

    partial

    1 attempt

  • 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.

    candidate

    1 attempt