Discrete Mathematics

Authors and titles for recent submissions

• Tue, 30 Jun 2026
• Mon, 29 Jun 2026
• Fri, 26 Jun 2026
• Thu, 25 Jun 2026
• Wed, 24 Jun 2026

See today's new changes

Tue, 30 Jun 2026 (showing 17 of 17 entries )

[1] arXiv:2606.30298 [pdf, other]

Title: Convex Recoloring of General Graphs: Formulations, Polyhedra, and Computational Experiments

Boyue Lin, Phablo F. S. Moura, Roel Leus

Comments: 29 pages,6 figures

Subjects: Discrete Mathematics (cs.DM)

[2] arXiv:2606.30184 [pdf, html, other]

Title: Stable complete coordinates for multisets of points via basic $r$-symmetric tropical polynomials

Susumu Kubo

Comments: 12 pages

Subjects: Discrete Mathematics (cs.DM); Algebraic Geometry (math.AG); Combinatorics (math.CO); Metric Geometry (math.MG)

[3] arXiv:2606.29743 [pdf, html, other]

Title: 3-packings in Triangulations: Algorithms, bounds, and Complexity

Prosenjit Bose, Anil Maheshwari, Bobby Miraftab, Yota Otachi

Comments: Comments are welcome

Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[4] arXiv:2606.29477 [pdf, html, other]

Title: Chamber geometry and specification numbers of Boolean threshold functions

Martin Anthony

Comments: 61 pages, 2 figures, 2 tables

Subjects: Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Combinatorics (math.CO)

[5] arXiv:2606.29153 [pdf, html, other]

Title: The Optimal Knight Exchange Puzzle is NP-Hard

Henry Siegel

Comments: 13 pages, 10 figures and tables

Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC)

[6] arXiv:2606.29075 [pdf, html, other]

Title: Learning Unions of Intersecting Affine Modules in One Dimension with Queries

Eva González, Montserrat Hermo, Anthony Lin

Comments: Accepted at ISSAC 2026

Subjects: Discrete Mathematics (cs.DM)

[7] arXiv:2606.28734 [pdf, html, other]

Title: Local Minima in Quadratic-Penalty Relaxations of Binary Linear Programs

Cheng-Han Huang, Yongliang Sun, Chaoyan Huang, Ismail Alkhouri, Rongrong Wang

Subjects: Discrete Mathematics (cs.DM)

[8] arXiv:2606.30588 (cross-list from math.CO) [pdf, html, other]

Title: A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7

Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

[9] arXiv:2606.30282 (cross-list from math.CO) [pdf, html, other]

Title: List $3$-coloring $C_4$-free graphs of diameter-$2$ in polynomial-time

Yukihiro Murakami

Comments: 15 pages, 3 figures

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

[10] arXiv:2606.30270 (cross-list from cs.CC) [pdf, html, other]

Title: Cyclic Attractor Detection in Boolean Network Dynamics under Local Logical Constraints

Alexander Drobyshev, Grigoriy Bokov

Comments: 20 pages, 3 figures

Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Dynamical Systems (math.DS)

[11] arXiv:2606.30118 (cross-list from cs.GT) [pdf, html, other]

Title: I.i.d. Prophet Inequalities with Discounted Rewards: As Hard as the Non-i.i.d. Case

Jung-hun Kim, Vianney Perchet

Subjects: Computer Science and Game Theory (cs.GT); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Theoretical Economics (econ.TH); Optimization and Control (math.OC)

[12] arXiv:2606.29595 (cross-list from math.PR) [pdf, html, other]

Title: Note on Finite-Automata Bernoulli Factories for Rational Functions

Renato Paes Leme, Jon Schneider

Subjects: Probability (math.PR); Discrete Mathematics (cs.DM); Formal Languages and Automata Theory (cs.FL)

[13] arXiv:2606.29553 (cross-list from math.CO) [pdf, html, other]

Title: An annihilation-number Caro-Wei bound: a TxGraffiti conjecture and an independence-number bracket

Chakshu Gupta

Comments: 5 pages

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

[14] arXiv:2606.29449 (cross-list from math.CO) [pdf, html, other]

Title: Toward a KKL Theorem for any HDX

Max Hopkins

Subjects: Combinatorics (math.CO); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)

[15] arXiv:2606.29199 (cross-list from math.CO) [pdf, html, other]

Title: Improved Domination--Packing Bounds in Claw-Free Cubic Graphs and Unit Disk Graphs

Juan Gutiérrez, Kaustav Paul

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

[16] arXiv:2606.28599 (cross-list from math.CO) [pdf, html, other]

Title: Algorithms for the Maximum Edge Open Packing Problem

Sriram Bhyravarapu, Gautam K. Das, Kamal Santra

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

[17] arXiv:2606.28478 (cross-list from cs.DS) [pdf, html, other]

Title: Maximum Cut Algorithms and Upper Bounds for Planar and Toroidal Graphs

Mark Glass, Meir Feder

Comments: 9 pages, 3 figures

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)

Mon, 29 Jun 2026 (showing 5 of 5 entries )

[18] arXiv:2606.28315 [pdf, other]

Title: Pairwise Reflection Symmetry in Generalized Latin Rectangles

Enrico Iurlano, Günther R. Raidl

Comments: 16 pages, 2 figures

Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[19] arXiv:2606.28147 (cross-list from math.MG) [pdf, other]

Title: Linear-size $\ell_1$ sparsifiers

Victor Reis, Thomas Rothvoss

Comments: 20 pages

Subjects: Metric Geometry (math.MG); Discrete Mathematics (cs.DM)

[20] arXiv:2606.27961 (cross-list from math.NT) [pdf, html, other]

Title: Transversal Difference Numbers in Finite Abelian Quotients

Mugurel Barcau, Vicenţiu Paşol, George C. Ţurcaş

Comments: 27 pages, comments welcome

Subjects: Number Theory (math.NT); Cryptography and Security (cs.CR); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[21] arXiv:2606.27501 (cross-list from cs.CG) [pdf, html, other]

Title: Unbent collections of non-planar $s$-grid-drawing

Therese Biedl

Comments: To appear at CCCG 2026

Subjects: Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[22] arXiv:2606.27451 (cross-list from math.CO) [pdf, html, other]

Title: Totally Disjoint Diametral Paths

Tınaz Ekim, Arthur Farley

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

Fri, 26 Jun 2026 (showing 6 of 6 entries )

[23] arXiv:2606.27104 [pdf, html, other]

Title: Proof of the Density Threshold Conjecture for Pinwheel Scheduling

Akitoshi Kawamura

Comments: 12 pages, 2 figures

Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

[24] arXiv:2606.27179 (cross-list from cs.IT) [pdf, html, other]

Title: Linear Code Conversion in the Merge Regime: General Bounds and Reed-Muller Constructions

Anina Gruica, Benjamin Jany, Stanislav Kruglik

Comments: arXiv admin note: text overlap with arXiv:2601.10341

Subjects: Information Theory (cs.IT); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Number Theory (math.NT)

[25] arXiv:2606.27159 (cross-list from math.CO) [pdf, html, other]

Title: Counting equitable $k$-colorings in graphs of bounded clique-width

Holger Dell, Thore Husfeldt, Amir Nikabadi

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

[26] arXiv:2606.26943 (cross-list from cs.CC) [pdf, other]

Title: Non-Uniform and Weighted Crossing Gates in Two-Dimensional Sandpiles

Pablo Concha-Vega, Antonin Loubière, Kévin Perrot

Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)

[27] arXiv:2606.26677 (cross-list from cs.FL) [pdf, other]

Title: How Long Can the Escaping Ant Be Confined?

Kossi Roland Etse

Subjects: Formal Languages and Automata Theory (cs.FL); Discrete Mathematics (cs.DM)

[28] arXiv:2606.26639 (cross-list from cs.DS) [pdf, html, other]

Title: Fast Enumeration of Minimal Removable Sets in Monotone Systems with Application to Core Collapse Analysis

Kan Shota, Kazuya Haraguchi

Comments: 28 pages, 5 figures

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

Thu, 25 Jun 2026 (showing 1 of 1 entries )

[29] arXiv:2606.25988 (cross-list from math.CO) [pdf, other]

Title: Conflict-Free Coloring Planar Graphs with 4 Colors

Petr Hliněný, Lukáš Málik

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

Wed, 24 Jun 2026 (showing 7 of 7 entries )

[30] arXiv:2606.24675 [pdf, html, other]

Title: A Congestion Parameter for Depth-First Graph Traversals

Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, Shinnosuke Seki

Comments: 13 pages, excluding the 11-page appendix and the bibliography. Accepted to MFCS 2026

Subjects: Discrete Mathematics (cs.DM)

[31] arXiv:2606.24415 [pdf, html, other]

Title: Novel Triple-Based Problems for the Construction of Phylogenetic Networks via Least Common Ancestors

Patricia A. Ebert, Anna Lindeberg, Marc Hellmuth

Subjects: Discrete Mathematics (cs.DM); Populations and Evolution (q-bio.PE)

[32] arXiv:2606.23837 [pdf, html, other]

Title: Flood-It with Jewelry -- Characterizing the Game Complexity for Cograph Generalizations

Martin Darmüntzel, Christian Rosenke, Mark Scheibner

Comments: A short version of this paper will appear in the proceedings of the 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)

[33] arXiv:2606.24822 (cross-list from math.CO) [pdf, html, other]

Title: Graded Betti numbers of generalized split--join graphs and applications

Bilal Ahmad Rather

Comments: 27 pages, 4 Figures

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Commutative Algebra (math.AC)

[34] arXiv:2606.24707 (cross-list from math.CO) [pdf, html, other]

Title: Convex geometries and directed paths on three vertices

Júlio Araújo, Mitre C. Dourado, Marisa Gutierrez, Fabio Protti, Silvia Tondato

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

[35] arXiv:2606.24326 (cross-list from math.CO) [pdf, other]

Title: Obstructions for Minor-Closed Classes of limiting Densities Below 3/2

Antonios Kominatos, Reem Mahmoud, Dimitrios M. Thilikos

Comments: An extended abstract has been presented at WG 2026

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

[36] arXiv:2606.24016 (cross-list from math.CO) [pdf, html, other]

Title: Extremal Spanning Trees in Product Grid Graphs

Jiechen Zhang

Comments: 28 pages

Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Spectral Theory (math.SP)