Problems
No problem here has yet been reviewed by a person.
The imbalance of an edge uv of a finite simple graph is the absolute difference of the degrees of u and v. Kozerenko and Skochko conjectured that the multiset of all edge imbalances is graphic - realizable as the degree sequence of some…
A finite closure system can be given by implications or by a list of subsets closed under intersection. Deciding whether one specification of each kind defines the same family had remained open in several settings; the paper proves the…
A collection of open problems from the algebraic and enumerative combinatorics literature, resolved in one paper: a conjecture of Defant, Jiang, Marczinzik, Segovia, Speyer, Thomas and Williams on the echelonmotion operator on modular…
Fulek defined a weight-five three-row 0-1 matrix L_3 and asked whether ex(n, L_3) = O(n). It is: every r × s matrix avoiding L_3 has at most 27r + 2s ones, so 6n - 8 ≤ ex(n,L_3) ≤ 29n for n ≥ 5. The same argument covers an infinite family…
Can S-decoding polynomials modulo a product of k primes be built with only k+1 nonzero coefficients, the minimum their own lower bound allows? Yes, via a general framework for special prime products. The consequence is that for any…
Does quantum memory give a query-complexity advantage for learning an unknown quantum channel, when protocols without it must measure after each channel use and keep only a classical transcript? It does, and the paper also determines how…
The classical problem of maximizing the Shannon entropy of a sum of independent random variables supported on a finite alphabet, settled in the ternary case. For independent X_1, …, X_n taking values in 0,1,2, the entropy of S_n = X_1 + ……
The directed five-dimensional torus D_5(m) has a Hamilton decomposition for every odd m ≥ 3, extending the decomposition program for directed tori beyond the three-dimensional case.
Nikolov and Ullman asked, as Open Problem 1 on DifferentialPrivacy.org, whether k statistical queries over a universe of size T can be released under pure differential privacy at the square-root error rate that the known lower bounds…
Monical, Tokcan and Yong conjectured that every fixed positive power of the Vandermonde determinant fails to have saturated Newton polytope in sufficiently many variables. For every even power k ≥ 4 there is an explicit lattice point of…
Subbarao and Verma asked in 1999 (Problem 5.7, first part) whether the complementary Bell numbers f(n) = B_n(-1) take any given value only finitely many times. Campbell proves they do: for every fixed integer the fiber is finite, a result…
Let n_k be the least n > 2k such that (n-k)(n-k+1)…(n-1) has no prime factor in (k, 2k). Erdos conjectured a superpolynomial lower bound; for all large k, n_k > e^log^2 k / (20 loglog k).
A collection of open problems drawn from published lists, including Cahen, Fontana, Frisch and Glaz's Open Problems in Commutative Ring Theory and Erman and Sam's survey of Boij-Soderberg theory, each proved or disproved by one automated…
A problem from Fajtlowicz's Graffiti program, studied by Erdős and Staton, on the Havel-Hakimi residue of common-divisor graphs. The paper resolves the problem and extends it, determining the residue's first-order scale and its nontrivial…
Two degree inequalities for circle-valued Sobolev maps have constants that degenerate as p → 1^+ or δ → 0^+. Brezis posed the problem of sharpening them; both are now sharpened, by the same power trick with elementary estimates.
For every n≥2 the paper exhibits an n-dimensional K-polystable toric Q-Fano variety whose alpha invariant is exactly 2/2n+1, answering a question of Liu and Zhuang on whether a K-semistable example exists with alpha invariant between 1/n+1…
For A ⊂ F_p of density 1/2, call A almost affine invariant under φ(x) = ax+b if |A triangle φ(A)| = o(p). Problem 90 asks for the threshold K below which A can be almost affine invariant simultaneously under all such φ with |a|, |b| ≤ K…
Nazarov conjectured that for s ∈ (1, 3/2) the quadratic form of the spectral fractional Dirichlet Laplacian strictly increases under u ↦ |u| when u changes sign. Proved and substantially generalized, with the same conclusion for the…
Banach asked in 1932 whether a real Banach space X whose ndimensional subspaces, for some fixed 1 < n < dim X, are all isometric must be a Hilbert space. Gromov proved the conjecture for even n, and subsequent work settled several…
Online Shadow Tomography with log m dependence, while retaining poly(log(d)/ε) dependence. Also, matching the best classical bounds for Adaptive Data Analysis