Hypergraph Alon-Tarsi Bounds Track Edge Density
Permuting nonconstant edge coefficients gives an arbitrary-field bound of $2\lceil\mathrm{ed}(H)\rceil+1$, connecting polynomial structure to hypergraph density.
Aug 21, 20264 min2501.00157
Combinatorics
math.CODiscrete mathematics, graph theory, enumeration, and optimization.
Sort:
Two Rainbow Cycles Extend Lehel’s Partition Theorem
Under proper edge colouring, an existence proof partitions every sufficiently large complete graph into two vertex-disjoint rainbow cycles.
Aug 19, 20264 min2608.17996
Universal Density Parameter Determines Graph Percolation Thresholds
Unfolding and refolding witness graphs lets the authors characterize critical activation density for every fixed graph H, including witnesses larger than the host graph.
Aug 14, 20264 min2605.15066
Non-Backtracking Walks Reach Collisions Near the Square-Root Scale
Expected self-intersection time is O(√n log n) on bounded-degree graphs and O(√n) for regular graphs with a uniform spectral gap.
Aug 11, 20263 min2608.09729
Comparability-Graph Unions Can Have Chromatic Number k^d
For every positive d and k, the authors construct a union of d comparability graphs with clique number k and chromatic number k^d, extending the separation to fractional coloring and the independence ratio.
Aug 9, 20262 min2606.09415
Reflection Labels Establish Shellability for Shifted Lower Bruhat Intervals
An explicit reflection labeling gives every shifted lower interval a controlled chain structure across arbitrary Coxeter groups.
Aug 6, 20264 min2608.04417
Spectral Certificates Separate Accuracy From Inference
An explicit Matrix-Bernstein and gap protocol gives finite-sample network certificates, then declines when valid sets are still vacuous.
Jul 30, 20265 min2602.10566
Rainbow Cycles Reach The Half-Vertex Bound
A minimal-counterexample proof settles Aharoni’s r=2 case and shows the ceiling n/2 bound cannot be improved.
Jul 29, 20264 min1806.00825
Triangle Counts Extend Sullivan’s Second Neighbourhood Conjecture
A transitive-triangle condition proves Sullivan’s inequality for two broad graph classes and gives partial split-graph proofs.
Jul 29, 20264 min2306.03493
Resistance Curvature Separates Toughness From Traceability
Polytope arguments and explicit graph families disprove a 1-toughness conjecture, certify a 34-vertex nontraceable RP graph, and classify path products.
Jul 29, 20263 min2607.13169 Code available