Schubert positivity has a positive rule under two conjectures
If GRH and a derandomization assumption hold, every positive Schubert coefficient gets a poly-time verifiable certificate.
cs.DM
Discrete Mathematics
Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
sort pith recommended most recent
Noisy quantum sampler plus repair yields polynomial-time guarantee
Guarantee holds when the ideal circuit gives optimal strings inverse-polynomial weight; noise costs one extra power of n.
· “Polynomial Time Quantum Approximation Schemes for Constrained Optimisation”
Uniform distribution maximizes independent-set sampling probability
When a matroid's automorphisms act transitively, the chance of drawing K distinct independent elements peaks at equal probabilities and is a
· “Maximum Probability of Independence in Transitive Matroids”
Explicit graphs settle a Ramsey saturation conjecture
For odd t≥17 the new graphs pin DS(3,t) between 2t−1 and 5t−10.
· “An infinite family of doubly saturated R(3,t)-good graphs”
Every dense hypergraph hides a short even cover
A sharp density threshold now guarantees a small subfamily of edges with every vertex appearing evenly.
Hypergraph matching finally has sharp stability tests
Assign each arrival a type on the spot; three equivalent criteria decide when the system stays finite
· “Stability in stochastic hypergraph matching I: necessary and sufficient criteria”
Projection of flags complex gives sub-polynomial expander
A combinatorial construction from subspace chains achieves spectral and coboundary expansion at once, yielding near-linear PCPs and hypergr
Contradiction graph decides VC dimension threshold for any m
Vertices are realizable label sequences of length m; edges mark label disagreements on shared points, fixing whether dimension meets or tops
Gallai vertex decision is Θ₂^p-complete
The problem requires a logarithmic number of parallel NP queries and rules out constant-factor approximations for the longest-path hitting-1
Boxicity of zero divisor graphs equals n or n−1
A new integral covering graph settles the exact answers for reduced rings and PID quotients, including two open questions.
Weighted multilayer hubs need no graph flattening
For sum aggregation it's exact; for max, an upper-bound heuristic plus top-k candidates recovers most hubs.
· “Degree Centrality Algorithms for Weighted Multilayer Networks (or w-MLNs)”
Open-world AI agents set five new math records
The discoveries include a 604-point kissing configuration, a new Kakeya family, and an improved Erdős bound.
· “Autonomous Mathematical Discovery in an Open-World Multi-Agent Environment”
Exact boxicity found for compressed zero-divisor graphs
For Z_N, boxicity is 0, a−1, or a depending only on prime exponents, settling two open questions.
· “The boxicity of the compressed zero divisor graph of the ring of integers modulo N”
Smallest 4-chromatic girth-6 graph: 29 to 64 vertices
A 64-vertex witness and a computer exhaustion narrow the known range from 26-66.
· “Improved bounds for the smallest 4-chromatic graph of girth six”
This paper proves that every 2-connected apex cubic graph admits a three-edge-coloring
Every 2-connected apex cubic graph is three-edge-colorable, and this completes the proof of Tutte's three-edge-coloring conjecture.
An adversary can force n log^2 n matching moves
The lower bound matches the known upper bound, settling the malicious recourse model and overturning a conjecture.
· “A tight lower bound for malicious online bipartite matching with limited recourse budget”
Degree 7+ regular graphs: domination never exceeds edge domination
A matching-endpoint argument closes degrees 7 and 8, leaving only degrees 3 through 6 open.
· “Domination versus edge domination in regular graphs of degree at least seven”
Induced long S-cycles pack or a small ball hits them all
New proof with fragile-ear frames gives polynomial Erdős-Pósa duality and an O(n^{O(ℓ)}) algorithm.
· “ErdH{o}s-P\'{o}sa property for induced packings of long S-cycles”
Exact bound: two parameterized periods force their gcd
The new length bound scales with gcd(p,q), not min(p,q), and is proven optimal for every alphabet size.
Potts partition recurrence order is a Dyck-path count at finite T
For q>=4 the minimal order matches A007123; at q=3 and q=2 it collapses to A001998 and A001405.
· “Thermal Recurrence Orders of the Potts Model Partition Function in Grid Graphs”
Tree-Robinson spaces are exactly dually chordal at every level
One tree certifies the whole dissimilarity space, and recognition scans only minimum spanning trees.
· “T-Robinson Spaces: Structure, Recognition, and Applications to Real Data”
Honeycomb bound beats best-known binary-code rate limits
First level of a representation hierarchy outdoes both the MRRW-era and quantum-channel curves at every distance.
Huge point sets force 4 in a line or 6 visible points
First open case of the big-line-big-clique conjecture is settled for k=6, ℓ=4.
· “Large Finite Point Sets Have 4 Collinear Points or a 6-Clique”
New proof method raises 25 Ramsey-number bounds
An integer-programming search in distance space improves R(3,n) for 24≤n≤49 and pins down eight circulant Ramsey numbers.
· “An Integer Programming Approach to Compute Lower Bounds for Ramsey Numbers Using Circulant Graphs”
At degree 3, perfect-matching uniqueness stays NP-complete
The last open variant — deleting edges to force a unique perfect matching — is NP-complete even for bipartite max-degree-3 graphs.
· “Hardness of Forcing Unique Perfect Matchings in Bipartite Graphs of Maximum Degree 3”
SAT search certifies exact 2D bandwidths in one hour
Where a 72-hour exact method stalled, it certifies 83 optima and improves three published values.
· “Exact SAT Solving for the Two-Dimensional Bandwidth Minimization Problem”
Modular valuations make Jaccard distance a metric on any lattice
New results drop distributivity and global bounds, opening the metric to quantum logic and open-ended data streams.
· “On the Triangle Inequality for the Jaccard Distance in Arbitrary Lattices”
Reaction-network graphs gain a second sign: the direction of change
A finite causal abstraction of continuous dynamics yields Boolean graphs with fewer spurious transitions.
Separator facets pinned down by graph conditions
Polynomial-time tests for which ILP inequalities define facets, plus a complete path description.
Three axioms capture fuzzy relations with varying truth values
A theorem identifies the exact axioms for the middle level of the fuzzy-relation hierarchy.
· “Arrow Operations in Categories of Lattice-valued Relations”
Bounded VC dimension makes tournament isomorphism polynomial
Two tournaments with VC dimension d are compared in n^{O(d log d)} steps; k-colorable ones in n^{O(k)}.
A 39-vertex graph disproves the 1979 Albertson-Berman conjecture
Largest induced forest has 19 of 39 vertices, below the conjectured n/2 bound.
· “A counterexample to the Albertson-Berman conjecture about induced forests in planar graphs”
Two sliding tokens always reconfigure in at most 4n moves
Every reachable two-token independent set can be transformed with no vertex used more than four times.
Every digraph with out-degree 2k-1 packs k near-directed cycles
A relaxation of the 1981 Bermond–Thomassen conjecture now holds for every k, at the same sharp threshold.
Constant online discrepancy for small-coordinate vectors
A random signer keeps every prefix inside a bounded cube, failing with probability exponential in d/log²(ed).
Worst-case circle treasure hunt solved exactly
The hardest k-treasure layout is a 'double then even' family, giving exact minimax times and sharp search bounds.
· “Going in Circles: Collaborative Multi-Robot Treasure Hunting”
Every non-SNS sign pattern now has a short singular witness
Settles a Handbook conjecture: recognition now yields an explicit singular matrix and null vector.
· “Polynomial-Time Singular Witnesses for Non-SNS Sign Patterns”
Greedy play is optimal for Gold Grabbing on two-center split graphs
On complete split graphs with two clique centers, always taking the heaviest legal move maximizes total gold.
· “Greedy approaches for Gold Grabbing on subclasses of split graphs”
A 15.6-degree cone decides the optimal rescue route
If starting inside the cone, land at a computed checkpoint first; outside it, head straight for the origin.
Symmetric networks are undersampled by MCMC
If correct, existing network samplers misweight symmetric topologies, while orchard networks need no correction.
· “Metropolis-Hastings Sampling of Phylogenetic Networks: Correcting for Symmetries”
Nonisomorphic graphs can share nearly every card
New pairs break the old deck-overlap benchmark and can push the shared fraction close to 1.
· “Nonisomorphic Graphs Can Share an Arbitrarily Large Fraction of Their Vertex-Deleted Cards”
Recognizing CIS graphs is coNP-complete
A 3SAT-to-graph reduction settles the 1990s open question: no quick recognition algorithm unless P equals coNP.
PCF coloring is NP-complete on perfect elimination bipartite graphs
Deciding a proper conflict-free k-coloring stays hard on a narrow bipartite class; approximation is hard too.
· “Complexity and algorithms for proper conflict-free coloring in graphs”
Cross the claw, and co-secure domination becomes NP-complete
Linear-time on claw-free split graphs, NP-complete on the wider K1,4-free class: the boundary sits at the claw.
· “A Fine-Grained Complexity of Co-Secure Domination for Some Subclasses of Chordal Graphs”
Generalized multiway cut is tractable for fixed budget k
One branching search plus posimodular uncrossing solves every oracle-given connectivity function in O(k^{k+2} n^6) time.
Crossing tournaments are polynomially chi-bounded
Tournaments from interval systems colour with O(omega^4) acyclic classes without needing comparability decompositions.
Balancing Brownian paths has a sharp phase transition at H=1/2
At the critical Hurst exponent, n independent paths admit signings with discrepancy O(1) with constant probability.
Sub-Gaussian inputs get O(sqrt n) online discrepancy
A horizon-independent potential method extends the Rademacher guarantee to Gaussians and sparse inputs.
· “Online Discrepancy Minimization for Sub-Gaussian Inputs via Regularization and Restriction”
Square and 3×n rectangle tilings now have exact growth rates
The number of tilings grows like exp((π/√3)n√log n) for the square and exp(π√(11n/3)) for the strip.
Counting constraint solutions now possible at the pD² threshold
A 2-tree expansion gives polynomial-time counting under the local lemma condition, matching known hardness bounds.
K2 is the only tree that blocks generic two-weight edge-colorings
Zero-sum and zero-weight pairs have exact structural obstructions, checkable in linear time.
Only C3 and C5 survive the minimal-matrix classification
The proof completes the list of exceptional blocks, so every te-cone admits a regular Hilbert triangulation.
NP-hardness lands exactly at the maximum-degree threshold
For every fixed k ≥ 3, the rainbow-domination decision problem is hard at k = Δ and trivial at k = Δ + 1.
· “A Degree Threshold for Independent Domination in Generalized Prisms”
Tie-aware ranking method generalizes the feedback arc set problem
Faculty hiring networks get a ranking that allows equivalence classes instead of forcing strict order.
Committee sizes must grow like 1/ε² in the worst case
New construction matches the known upper bound up to a constant, settling the size of approximately dominating sets.
Small vertex cover keeps hill-climbing short
On constraint graphs with a small vertex cover, both greedy and random hill-climbing reach a local peak fast.
· “Vertex cover number of valued constraints is a structural parameter for efficient local search”
Triangle-free MIS: n^1/2 approximation is best possible
New randomized reduction via Moser–Tardos resampling closes the gap between previous n^1/4 hardness and the n^1/2 algorithm.
· “Tight Inapproximability of Max Independent Set in Triangle-Free Graphs”
The first update picks the winner with Gaussian odds
A small initial lead becomes a Gaussian-biased coin flip, and consensus arrives in about log N over log log N rounds.
Most width parameters survive simultaneous representations
The same construction that measures distance to a graph class also decides which invariants stay bounded.
Every graph's quadratic subgraph optimum is convex piecewise affine
As the root a varies, the optimal value is convex piecewise affine; breakpoints are critical roots.
· “Quadratic Degree Sequence Optimization and the Critical Roots of a Graph”
Gap found in 42-queue proof for planar graphs
A 19-vertex counterexample shows a key claimed property fails, leaving only a 48-queue upper bound.
· “A Gap in the 42-Queue Layout Algorithm for Planar Graphs”
The authors introduce a calculus for partitioning the solution space of extremal set…
A new symmetry-aware partitioner for set-family search spaces yields the first machine-checkable proof certificates for Chvátal's…
A/E-design is inapproximable under partition constraints
Partition matroids force exponential-in-bit-length approximation hardness for A- and E-optimal design, unlike D-design.
Maximum edge open packing goes polynomial on three graph families
Permutation, interval, and well-partitioned chordal graphs now solve in O(n^4) or better.
· “Maximum Edge Open Packing in Permutation, Interval, and Well-Partitioned Chordal Graphs”
Grid Slime Trail is PSPACE-complete
The grid game is as hard as QBF, and the eight-directional tournament variant follows by rotation.
Sphere-code bound tightened to (3/2)^n
A local packing inequality removes the missing √2 from the leading constant.
One demand of slack cuts demand matching to 7/6 ratio
New algorithms and matching lower bounds pin the weight-versus-capacity trade-off for demand matching.
Moore bound attained asymptotically for every fixed diameter
Flag-space graphs match the Moore bound, settling a long-standing conjecture for every fixed diameter.
Strong odd coloring of planar graphs now capped at 368
A discharging argument trims the 388-color bound, and a new 20-color example raises the lower side.
· “An Improved Upper Bound for the Strong Odd Chromatic Number of Planar Graphs”
No computable recipe for unbreakability bound in CMSO
A constructive version of the 2018 reduction to unbreakable graphs would put 3-colourability in P.
· “Reducing CMSO to Unbreakable Graphs Cannot be Computable”
Cross-row-free digraphs: every big wall has a flat subwall
Deleting a bounded number of vertices turns any large cylindrical wall in a cross-row-grid-free digraph into a flat wall.
Alon–Saks–Seymour conjecture refuted optimally
New unambiguous DNFs give graphs with biclique partition 2^O(n) and chromatic number 2^Ω(n^2).
Every parity rule yields an induced subgraph of size n/6
Improves the previous 2n/21 bound for graphs without isolated vertices, with sharper results for bipartite graphs.
Minimal rewiring moves grow quadratically with graph max degree
Sampling graphs with fixed curvature needs ever-larger moves; a degree-3 lattice basis keeps it feasible.
· “Markov and lattice bases for Forman-Ricci curvature of graphs”
Discrete curvature converges to the Gauss-Bonnet-Chern integrand
Index expectation on fine triangulations gives the continuum curvature, so finite geometry is not just an analogy.
1
The old deterministic ceiling was 1/2; the same framework now reaches about 0.63 against oblivious adversaries.
· “Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms”
Identical weight lists keep 3D matching hard
The symmetric version is strongly NP-complete, APX-complete, and has no PTAS unless P = NP.
· “Symmetric Numerical Three-Dimensional Matching: Intractability and Inapproximability”
For regular matroids, ear-decompositions stay within a factor of six of joins
Exact equality fails outside graphic matroids, but the two parameters stay comparable through decomposition.
Exact-distance domination density: between 1/(4k) and (k-1)/(3k^2-k-1)
For k=2 the density is exactly 1/9; for larger k, two explicit bounds bracket the limit.
Poisson-tree mixing is near-linear
Glauber dynamics on random-tree neighbourhoods now samples sparse random graphs in O(n^{1+delta}) time, not n^{O(log q)}.
· “Fast Mixing for Low-Temperature Potts Models via Poisson Trees”