Imported from VibeMathed under CC BY 4.0. Each record links to its registry entry and named primary source. Registry verification is preserved verbatim.
The manuscript claims a polynomial-time reduction from 3-SAT proving (2,1)-C1P NP-hard; together with membership in NP, this establishes NP-completeness and closes the sole unresolved (k,δ) case from the earlier classification. It also implies NP-completeness of the equivalent completion problem.
The proof package further shows that, within its specific nested-prefix/internal-local gadget architecture, no…
One conjecture each way: the second proved, the first disproved. Two further Chen-Lawrencenko conjectures remain open and are flagged as such in the paper.
Among classes of tournaments for which neither hardness nor polynomial-time solvability of isomorphism was known, bounded VC dimension stood out as an open problem of Neuen and Grohe. Resolved: isomorphism of tournaments of VC dimension d is decidable in time nO(dlogd), so automorphism groups of bounded-VC tournaments are computable in polynomial time; isomorphism of tournaments of bounded chromatic number…
Question 6.1 of Chalmoukis, Tsikalas and Yakubovich asks how far the Power boundedness constant P(T) of a matrix can exceed its ordinary Kreiss constant K(T). Answered more strongly: for every K>1 there are matrices whose Cayley transforms satisfy K(Ch(An,h))≤K while the strong Kreiss constant satisfies Ks(Ch(An,h))≥21CnαK with αK=(K−1)/(C+K−1). Since…
For a positive projection P on a Dedekind complete Banach lattice whose largest central operator below P is αid, Wickstead conjectured α must be 0 or 1/n for some natural n, and proved the finite-dimensional case. The paper proves the conjecture in general and settles the representation problem for Banach lattice algebras as a consequence.
A polynomial-time algorithm for computing an optimal committee under any Thiele voting rule on the Voter Interval domain, resolving a ten-year-old open problem posed for Proportional Approval Voting by Elkind and Lackner and later extended to every Thiele rule.
Ekhad and Zeilberger's second computational Chomp challenge asks for a Chomp position with three winning opening moves. Answered by exhibiting a bar with three winning opening moves.
Subbarao and Verma asked in 1999 (Problem 5.7, first part) whether the complementary Bell numbers f(n)=Bn(−1) take any given value only finitely many times. Campbell proves they do: for every fixed integer the fiber is finite, a result whose techniques connect to Wilf's conjecture on the vanishing of f(n).
Klopp and Zadik gave an exponential-time node-private algorithm for exact community recovery in stochastic block models and asked whether a polynomial-time algorithm could match it. One can: a Lipschitz surrogate for the penalized likelihood plus an accept-reject sampler gives a high-probability polynomial-time node-private algorithm that nearly matches the exponential-time guarantee.
The multivariate independence polynomial is the partition function of the hard-core model with per-vertex fugacities. The paper proves a lower bound extending to the multivariate setting a result Tao proved in the univariate case, and settles a conjectured generalization for a multiaffine version of the semiproper colouring partition function with two proper colours.
New theorems, not a formalisation of previously known results. For every base b≥2 the Erdős–Kac law is established for the λ-digit base-b palindromes and for the base-b reversals of the λ-digit primes, for ω and Ω and for ωS,ΩS with any regular set S of primes; with normal order loglogn on both families, and, for ω, all moments of order up to…
For every integer-valued strongly b-additive g with gcd(g(1),…,g(b−1))=1 and digit mean μg≥0: g(p) is prime for infinitely many primes p. For μg>0, ∑1/p over p<X with g(p) prime is (dg/φ(dg))log3X+Cg,1+O(1/loglogX), likewise for the first j iterates. Also #{p≤x:g(p) prime}≪π(x)/loglogx, of that exact order on a large set of x, and…
Akbari, Alikhani, Oboudi and Peng conjectured in 2010 that 0 and -2 are the only integer roots of the domination polynomial D(G,x), proven for trees and unicyclic graphs and verified exhaustively for small orders. The paper gives a counterexample of order 33 with an integer domination root at x=−4, built from an S-unit branch cancellation mechanism.
If f(n) is the maximum total side length of n interior-disjoint squares packed in the unit square, is f(k2+1)=k? An exact rational configuration packs 17 squares with total side length greater than 4, refuting the identity at k=4.
For Pn(z)=∑k=0nεkzk with independent uniform signs, does the number Rn of roots in ∣z∣≤1 satisfy Rn/(n/2)→1 almost surely? The manuscript proves the strong law with Rn=n/2+Oω(n149/150).
For a sequence of n distinct reals, determine the largest constant c such that some monotonic subsequence always has sum exceeding (c−o(1))⋅(1/n) times the total sum. Resolved as c=1.
Gao, Huo and Ma asked whether for every fixed k≥3 there is a function fk(n)→∞ such that every n-vertex (k+1)-critical graph contains fk(n) consecutive cycle lengths. The paper settles this and two related problems on cycle lengths and cycles with chords under chromatic and degree constraints.