Random linear list size pinned to integer precision at capacity
Theorem determines list size to within one integer for all finite fields, settling a four-decade-old question.
math.CO
Combinatorics
Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
sort pith recommended most recent
New independence number bound uses local clique sizes
Decade-old conjecture confirmed; better estimates on graph bipartiteness for clique-free graphs.
· “Localization of the Caro-Wei bound and its applications to bipartiteness”
A combinatorial formula gives the stabilization index of the v-number for powers of edge…
Stabilization index expessed as minimum cost over admissible pairs, combining a μ* invariant and independent-set size.
· “Stabilization index of V-number of powers of edge ideals of graphs”
Minimum odd-cycle count settles at (k-1)!/2
Every red/blue coloring of K(2k-1) forces (k-1)!/2 monochromatic odd cycles; only two colorings are extremal.
· “Threshold Ramsey multiplicity and extremal colorings for odd cycles”
First deterministic algorithm to beat the Bethe bound
For any nonnegative matrix, the permanent can be approximated within (√2−ε)^n in polynomial time.
· “Structural Corrections to the Bethe Approximation of the Permanent”
Realization graphs are maximally Hamiltonian
Two-decade-old Gray-code problem resolved by classifying the single obstruction
· “Maximal Hamiltonicity of realization graphs of degree sequences”
Exact growth rate for cancellative pairs is 2.25^n
Upper bound from entropy and Sinkhorn matches Tolhuizen’s construction, solving a thirty-year problem.
Boundary classes fix punctured module dimension in product graphs
A rank-sum formula using spectral derivatives gives the size of the punctured adjacency–degree module for Cartesian products with…
· “Punctured adjacency-degree algebras of Cartesian products”
Sparse paving matroids pass the real-rootedness test
Proof that Z-polynomials have only negative real zeros confirms a central conjecture; uniform matroids also show strict interlacing.
Cyclotomic multiple diameter minimized by geometric series
Sharp lower bound (p-1)N/p proven; equality forces a p-term geometric progression.
· “Sharp Diameter Bounds for Nonnegative Cyclotomic Multiples”
One polynomial unifies five classical graph invariants
The loopy polynomial also gives a geometric decomposition of the graph's score polytope via parking complexes.
· “The Loopy Polynomial: from Tutte's Universal V-Function to Bizonotopal Geometry”
A degree formula bounds how far a graph is from a Cayley graph
It is tight for stars and 89% of small graphs; the edit-to-a-cycle version is NP-complete.
Layer-by-layer method solves every semilinear elliptic equation on wide class of…
Using Eidelheit's theorem, arbitrary initial data on one or two layers extend to global solutions for any nonlinearity, including on Z²…
· “Solvability of Semilinear Elliptic Equations on Infinite Graphs”
Every finite graph obeys the clique-cover and coloring bound
For every finite graph, the local clique-cover number plus chromatic number stays within one of the vertex count.
Magnitude of tope graphs equals matroid zeta function
New identity unifies a distance invariant with a combinatorial generating function, defines magnitude for all matroids, and disproves a…
Hamming切片加性能量的误差紧到n^{-3}
通过循环进位自动机证明偏差阶的最优性，并导出三元表示的渐近均匀性
· “Energy Estimation of the Hamming Slice and its Applications”
Residue survivor counts match prime‑admissible block complexity
Exponential equivalence joins two counting families, leaving only the leading constant open.
· “Counting Survivor Sets: Exponential Equivalence with Prime-Admissible Sets”
Hypergraph Hamiltonicity gets a Chvátal-type condition
For $k$-uniform hypergraphs, codegree deficits of small sets can be compensated by large codegrees elsewhere, proving a conjecture of…
· “A Chv\'atal-type codegree condition for Hamiltonian cycles in k-uniform hypergraphs”
Sign-coherent cluster monomials always multiply to a cluster monomial
One invariant computes R-matrix pole orders, unifying cluster, quiver, and quantum-affine categorification.
Gowers norms get a strictly better log-convexity bound
New L^p autocorrelation estimates force the U^d norm below the product of neighboring Gowers norms.
∆-Y moves on K_n build every partial Steiner system
Minimum degree 7 ensures each graph corresponds to a collection of disjoint 3-sets.
This paper gives explicit formulas for stable Segre-Schwartz-MacPherson classes of…
Stable SSM classes for symmetric and skew-symmetric degeneracy loci are expressed in terms of a six-vertex random partition: skew classes…
· “Probability-theoretic interpretation of degeneracy locus formulas”
Eigenvalue gap forces long chordless cycles in pseudorandom graphs
A single spectral parameter λ forces an induced cycle of length c n log(d/λ)/d, and no stronger bound is possible.
Exact count of curve types by word length found
Formula uses a finite sum of totient-like functions plus a small periodic correction, ending a conjecture from 2016.
· “Exact curve counting of given word length on the once-punctured torus”
All 4-total colorings are equitable only up to order 14
The property fails at order 12 and for every even order 16 and above, settling a conjecture by Stemock.
· “Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable”
Unique rook placement on a permutation grid means hook shape
Crossword-inspired rook theory connects to alternating sign matrices and gives a neat test for a class of permutations.
Odd denominators rule the lonely runner spectrum for six speeds
New proof shows that for all but finitely many six-runner configurations, the maximal loneliness takes a special rational form.
· “Odd denominators in the Lonely Runner spectrum for six speeds”
Exact Delsarte bound at half rate is 1/2 − 1/π
Mass concentration and an N-qubit projection pin the asymptotic exponent for binary codes, matching the sphere-packing analogue.
· “The half-rate linear programming bound for binary codes is frac12-frac1π”
Homogeneous universal Schubert polynomials are the canonical ones
A cluster-geometry test settles the homogeneity question for universal Schubert polynomials in every rank.
· “Cluster Geometry of Universal Schubert Polynomials I: Geometric Bases and Schubert Transitions”
Stirling numbers organize subleading collinear gluon data
Even sectors give constraints, odd sectors yield gravitational building blocks that reconstruct all subleading terms.
· “Subleading Collinear Limits of Yang-Mills Amplitudes from Gravity”
Grigorchuk's independent-set problem solved: growth rate 3 impossible in F_2
Using Stallings core graphs, the author prove exct bounds on ranks of subgroups and on the size of independent sets of bounded-length words.
· “Two problems about bases and independent sets in free groups”
Characteristic rigidity persists in folded-algebraic matroids
Each Gordon matroid M(p) forces characteristic p under folded-algebraic representation; a 13-element connected matroid shows FAlg is…
· “Folded-Algebraic Matroids: Characteristic Rigidity and Almost-Entropic Separation”
Local finiteness does not suffice for Borel unfriendly partitions
A counterexample formulates a graph whose every unfriendly colouring is proper, blocking Baire and measurable solutions.
All topological Ramsey subsets are Ramsey in Solovay model
Generalises Mathias's theorem to every closed triple satisfying A1–A4 without ultrafilters or σ-closure.
· “Every subset of a topological Ramsey space is Ramsey in the Solovay model”
Bounded bases exist for most weighted sums of two numbers
New p-adic digit construction shows that unequal coefficients break the Erdős–Turán unboundedness barrier
One rule decides all walk‑count inequalities for every graph
A simple majorization condition perfectly separates true from false products of walk numbers.
Existence of a safe edge guarantees sequential vertex distinction
For all connected graphs except K₂ and even cycles, any proper edge coloring can be ordered to make adjacent vertices distinct.
18-colored Frobenius partitions determined modulo 16
A congruence identity reduces the 18-color case to the pentagonal number theorem, proving a recent conjecture.
Overpartition differences get exact 2-adic valuations at odd squares
Theorem 1.1 identifies the difference for every odd m≥1 and i≥3, with sharp modulus given by 2^{i+1}.
· “Internal congruences modulo powers of 2 for overpartition tuples with odd parts”
Uniform Turán density of tetrahedron is 1/2
A 40-year-old conjecture of Erdős and Sós on 3-uniform hypergraphs is settled by a computer-verified sum-of-squares argument.
Greedy ordering maximizes all circular consecutive-product sums
New proof resolves 2023 conjecture and minimizes speed of cyclic birth-death chains
· “Circular Rearrangement Inequality and Optimal Cyclic Birth and Death Chains”
Every block graph has at least n/3 minimal forts
Zero-forcing obstructions are abundant: block graphs hit the tree bound, and compatible fort sets grow exponentially.
Füredi's conjecture on strong Bollobás t-systems proved
Exterior-algebra proof gives the weighted inequality for any t, completing a generlization of Bollobás's theorem.
Top three σ values found in diameter‑3 generalized odd graphs
Folded 7‑cube, Odd graph O₄, and 7‑cycle C₇ are the only graphs reaching σ ≥ 1/36.
· “Spectral bipartiteness in generalized odd graphs of diameter three”
Even-distance bound yields graph traceability in four settings
Authors show a conjecture on Hamiltonian paths holds for graphs with small diameter, order, or specific connectivity.
· “Conditions for traceability under a bound on the size of even-distance sets”
Type-B Fuss-Catalan numbers computed for large m
Explicit q,t-polynomial and binomial dimension formula proven via equivariant Hilbert scheme and Koszul complex.
Support plus dimension certifies nonnegative tensor uniqueness
A single inequality applied to every component subset guarantees minimality and uniqueness in nonnegative rank decompositions.
· “Identifiability of Nonnegative Tensor Decompositions via Positive Scattering”
89% lower bound on rotation-system non-planar 4-subsets
Combinatorial analog of Hill's crossing number conjecture verified up to order 10 and asymptotically via semidefinite programming.
· “Some results on Archdeacon's conjecture for rotation systems”
Hadamard product keeps log-concave numerator polynomials log-concave
New theorem answers a question in generating-function combinatorics, with consequences for Ehrhart theory of lattice polytopes.
Infinite Kriesell conjecture reduces to finite case
New topological and limit tools show that Kriesell's conjecture for infinite graphs is equivalent to the finite version.
Gamma-Theta conjecture disproved by 243-vertex graph
A computer-verified counterexample shows that equal domination and eternal domination numbers do not force equality with the clique cover…
Near-perfect rainbow 2-connectivity for graphs at the Dirac threshold
Graphs with minimum degree at least (n-1)/2 can be 2-colored to rainbow-connect all but a vanishing fraction of vertex pairs.
Divisibility rule decides edge geography on stacked prisms
A simple gcd condition fully determines the winner for two families of prism graphs, with explicit strategies.
Homogeneous polynomial yields non-formal Milnor fiber at connectivity bound
For any n≥3 and s≥2, a fixed-degree polynomial gives a 2s-connected Milnor fiber with a nontrivial n-fold Massey product.
· “Homogeneous Milnor fibers and Kato--Matsumoto bounds via simplicial multiwedges”
Sharp bound for large sets in union-closed families
Proving the Leck–Roberts–Simpson weighted conjecture for many parameter ranges
· “On union-closed families with prescribed number of k-sets”
TWKHM walk-count conjecture proved for all finite trees
Proof combines Coxeter root theory with preprojective algebra to settle the decade-old open problem.
· “Polynomial positivity cones for Coxeter roots and walks in trees”
5x5-grid induced minor keeps MIS NP-hard
Refutes long-standing conjectures about polynomial and quasipolynomial algorithms for this hereditary graph class.
· “Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor”
For m≥15, the four-column Zarankiewicz value is floor((5m+6)/2)
All boards with at least 15 rows hit one exact count; only the 14-row case stays open between 37 and 38.
Catalan truncation polynomials are always irreducible over Q
Proof combines root bounds, modular reduction, and divisibility by a custom prime product to rule out any factorization.
· “Irreducibility of truncations of the Catalan generating function”
Subexponential approximation of permanent in deterministic polynomial time
First algorithm to break exponential barrier for arbitrary nonnegative matrices
· “Subexponential Approximation of the Permanent in Deterministic Polynomial Time”
Lattice polytopes break a four-decade-old unimodality conjecture
A Cayley sum of rectangular prisms gives IDP polytopes whose h*-polynomials dip and rise instead of climbing smoothly.
Nine axioms pin down expression tree categories
Every free non‑symmetric operad's matching category is captured by a short list of conditions, and gains a noetherian form akin to group…
Catalan permutations' double deficiencies approach Bin(n-2
Exact mean, variance, and total-variation bound show the statistic is nearly binomial with explicit rate.
· “The Distribution of Double Deficiencies in Pattern-Avoiding Permutations”
Nilspace structure groups meet simplicial homotopy
A functor translates cubespaces to Kan complexes, preserving towers and groups.
Every ergodic cubeset is a tower of abelian bundles
A categorical proof of the weak structure theorem that also covers condensed cubesets and compact nilspaces.
Forest induced minor controls path independence
In K1,t-free graphs, excluding a forest induced minor forces bounded path independence number, resolving a conjecture for forests.
· “Induced Forest Minor Theorem for Graphs Without an Induced Star”
Chordality settles hyperbolic distance completion
Local clique data suffice globally exactly when the graph is chordal, with explicit product formulas and a determinant-maximizing…
exp(Ω(√d)) vertices needed for RP^d triangulation
New topological inequality determines growth exponent of vertex numbers as 1/2
Periodic exclusion process has an explicit n-step limit shape
For every degree of asymmetry, the density converges to an explicit n-step fan, and a second-class particle picks one of those speeds.
For large strongly regular graphs
A Ramsey argument shows that beyond 6400 vertices, the only SRGs with VC-dimension 2 are complements of geodetic graphs.
Every level-one quasi-modular form is a symmetric q-shuffle
Symmetrized shuffles of q/(1-q)² generate all rational level-one quasi-modular forms, plus finite-level analogues.
Jack operators generate affine Yangian
Deriving cut-and-join and 3-cycle operators from Heckman–Polychronakos spectra via Hall duality.
· “Jack Content Operators and the Deformed {mathcal W}_(1+infty) Algebra”
Boros-Moll ratios: one conjecture proved
Ratio sequences from a quartic integral obey reverse ultra log-concavity exactly and strict log-concavity eventually.
A finite poset cut builds an equivalent 'negative' twin
The admissible cuts of a poset yield derived-equivalent partner posets, and the transformation reverses cleanly.
· “Derived equivalences between diagram categories of finite posets”
S-packing total coloring: exact numbers for paths and cycles
A new generalization of packing total coloring yields exact S-packing total chromatic numbers for several graph families.
Transitive groups settle eight open directed strongly regular graphs
A uniform construction also yields a full census of quasi-strongly regular digraphs on up to 110 vertices
· “Quasi-strongly regular digraphs constructed from transitive groups of degree nleq 110”
Irredundant card covers top out at half the grid squares
New defect framework proves that overlapping 2×2 cards on an m×m grid cannot exceed density 1/2, up to a linear error.
· “Irredundant Covers of Square Grids by 2 x 2 Cards: A Defect Framework”
Umbral calculus goes basis-free over any vector space
Binomial and Sheffer sequences gain basis-free characterizations; the Sheffer group becomes the Riordan group.
Overlap theorem unifies Helly and selection lemmas
A single combinatorial-topological condition forces a continuous map to pierce an entire color class, recovering several classical results.
New upper bound for hexagon-free graphs: 0.6144 n^{4/3}
Narrows the gap to the known lower bound, improving the earlier constant by about 2%.
· “An Improved Upper Bound for the Tur\'an Number of the Hexagon”