Skip to main content
archive Search
Submit Donate Log in

Press Enter to search · Advanced search

Discrete Mathematics

Authors and titles for recent submissions

  • Mon, 16 Nov 2026
  • Fri, 13 Nov 2026
  • Wed, 11 Nov 2026
  • Tue, 10 Nov 2026
  • Mon, 9 Nov 2026

See today's new changes

Total of 58 entries : 1-50 51-58
Showing up to 50 entries per page: fewer | more | all

Mon, 16 Nov 2026 (showing 5 of 5 entries )

[1] arXiv:2611.18391 [pdf, other]
Title: Color Refinement Distinguishes Connected Rooted Outerplanar Graphs
Louann Coste (DI-ENS), M{ó}nika Csik{ó}s (IRIF (UMR\_8243)), Laurent Viennot (DI-ENS, ARGO)
Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[2] arXiv:2611.17386 [pdf, html, other]
Title: TSP instances that require exponentially many subtour elimination constraints
Eleonora Vercesi, Austin Buchanan
Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[3] arXiv:2611.17999 (cross-list from math.CO) [pdf, html, other]
Title: Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$
Damien Jamet, Matthieu Rosenfeld
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Formal Languages and Automata Theory (cs.FL)
[4] arXiv:2611.17489 (cross-list from math.CO) [pdf, html, other]
Title: Isolation of $k$-cliques in uniform hypergraphs
Mattea Baluci, Peter Borg
Comments: 13 pages
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[5] arXiv:2610.40863 (cross-list from math.CO) [pdf, html, other]
Title: The Cranston--Li--Su--Wang--Xu (2026) conjecture is true
Dave Goel
Comments: 15 pages, 5 figures, 1 table. Lean 4 proof: this https URL
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

Fri, 13 Nov 2026 (showing 17 of 17 entries )

[6] arXiv:2611.16849 [pdf, html, other]
Title: Constrained intersection representations and forbidden patterns
Laurent Feuilloley, Michel Habib, Amalia Sorondo
Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[7] arXiv:2611.14909 [pdf, html, other]
Title: Explicit Subspace Evasive Sets via Subspace Designs
Joshua Brakensiek, Yeyuan Chen, Mahdi Cheraghchi, Rohan Goyal, Venkatesan Guruswami, Aaron Putterman, Zihan Zhang
Comments: 27 pages
Subjects: Discrete Mathematics (cs.DM); Information Theory (cs.IT); Combinatorics (math.CO)
[8] arXiv:2611.14817 [pdf, html, other]
Title: Tripod Reordering: A 33-Queue Layout of Planar Graphs
Sergey Pupyrev
Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[9] arXiv:2611.17259 (cross-list from math.CO) [pdf, html, other]
Title: Triameter, distance packings, and vertex connectivity
Artem Hak, Sergiy Kozerenko
Comments: Preliminary version, any comments are welcome
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[10] arXiv:2611.17183 (cross-list from math.CO) [pdf, html, other]
Title: New bounds on the boxicity of Kneser graphs
L. Sunil Chandran, Suraj Kumar Sahoo
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[11] arXiv:2611.17022 (cross-list from math.CO) [pdf, html, other]
Title: Large diameter for $(Δ+2)$-colouring reconfiguration
Wouter Cames van Batenburg
Comments: 15 pages, 2 figures
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[12] arXiv:2611.16883 (cross-list from math.CO) [pdf, html, other]
Title: Optimal Polyomino Fences
Alexis Langlois-Rémillard, Mia N. Müßig, Helmut Podhaisky, Erika Roldan, Günter Rote, Maximilian Brömme, Matthes Norden, Maximilian Prietzel, Daniel Yu, Mykhailo Lyader
Comments: 56 pages, 38 figures
Subjects: Combinatorics (math.CO); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM)
[13] arXiv:2611.16839 (cross-list from math.CO) [pdf, html, other]
Title: An upper bound on the number of edges of a Gomory corner polyhedron
A.Yu. Chirkov, S.I. Veselov, D.V. Gribanov, D.S. Malyshev, N.Yu. Zolotykh
Subjects: Combinatorics (math.CO); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Optimization and Control (math.OC)
[14] arXiv:2611.16835 (cross-list from cs.IT) [pdf, html, other]
Title: Explicit Edit Codes via Multicoloring
Huiling Xie, Zitan Chen
Subjects: Information Theory (cs.IT); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[15] arXiv:2611.16333 (cross-list from cs.DS) [pdf, html, other]
Title: When Elements Fail: Weighted Fault-Tolerant Matroid Bases
Madhumita Kundu, Soumi Nandi, Saket Saurabh
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[16] arXiv:2611.16299 (cross-list from math.CO) [pdf, html, other]
Title: Improved Lower Bounds for Mutually Orthogonal Latin Squares (MOLS) at 33 Orders
Christopher D. Rosin
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[17] arXiv:2611.15755 (cross-list from math.CO) [pdf, html, other]
Title: Asymptotically Optimal Bounds for Counting Near-Minimum Circuits in Regular Matroids
Robert P. Streit
Comments: 28 pages
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[18] arXiv:2611.15392 (cross-list from cs.DS) [pdf, html, other]
Title: Integrality Gap of 3.4 for Santa Claus: A Topology-based Analysis
Kimon Boehmer, Chien-Chung Huang
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[19] arXiv:2611.15299 (cross-list from math.CO) [pdf, html, other]
Title: Small classes have linear neighbourhood complexity
John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
Comments: 31 pages, 6 figures
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[20] arXiv:2611.14827 (cross-list from cs.DS) [pdf, html, other]
Title: Sublogarithmic Online Graph Exploration
Julia Baligacs
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[21] arXiv:2611.14738 (cross-list from cs.LO) [pdf, html, other]
Title: Exploring 3-CNF Formulas Generated From Partial Steiner Triple Systems
Wyatt Olson, Jared Soundy, J. Z. Schroeder
Comments: Revised manuscript of work presented at the Pragmatics of SAT (PoS) Workshop, FLoC 2026, July 19, 2026, Lisbon, Portugal. Not published in the workshop proceedings. Minor wording and notation corrections
Subjects: Logic in Computer Science (cs.LO); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[22] arXiv:2610.10233 (cross-list from math.CO) [pdf, html, other]
Title: Nonlinear lower-tail large deviations at criticality
Matthew Kwan, Huy Tuan Pham
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Probability (math.PR)

Wed, 11 Nov 2026 (showing 13 of 13 entries )

[23] arXiv:2611.14471 [pdf, other]
Title: A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression
Oscar Defrain, Corentin Jazeron, Kazuhisa Makino
Comments: 6 pages
Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[24] arXiv:2611.14513 (cross-list from cs.DS) [pdf, other]
Title: Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[25] arXiv:2611.14342 (cross-list from cs.DS) [pdf, html, other]
Title: Directed Singular-Value Sparsifiers with $O(n \log n/ε^2)$ Arcs
Emile Anand
Comments: 44 pages
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[26] arXiv:2611.14327 (cross-list from math.CO) [pdf, html, other]
Title: Characterizing Fixed-Treewidth Planar Graphs
Laura Merker, Samuel Schneider, Torsten Ueckerdt
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[27] arXiv:2611.14194 (cross-list from math.CO) [pdf, html, other]
Title: You Can Have It All: Small sparse induced-universal graphs for minor-closed classes
Vida Dujmović, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin, David R. Wood
Comments: Extends the results in arXiv:2605.06616 to produce induced-universal graphs with $n^{1+o(1)}$ edges and vertices
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[28] arXiv:2611.13917 (cross-list from cs.CC) [pdf, html, other]
Title: Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path
Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider, Torsten Ueckerdt
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[29] arXiv:2611.13813 (cross-list from math.CO) [pdf, html, other]
Title: Optimal radio labelings for the Cartesian product of a path and the Heawood graph
Payal Vasoya, Miral Doshi, Devsi Bantva
Comments: 24 pages, 1 figures
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[30] arXiv:2611.13787 (cross-list from cs.CC) [pdf, html, other]
Title: Local Modifications of Nearest-Neighbor and Min-Plus Representations
Liliia Redina
Comments: 19 pages, 2 figures
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
[31] arXiv:2611.13693 (cross-list from math.CO) [pdf, html, other]
Title: Rotating Walks, Derandomized Squares, and Permutation Conjugated Walks
Vedat Levi Alev, Shravas Rao
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Probability (math.PR)
[32] arXiv:2611.13585 (cross-list from cs.DS) [pdf, html, other]
Title: Approximating graphic TSP by b-matchings
Swati Gupta, Mehrdad Sohrabi, Levent Tunçel
Comments: 72 pages, 30 figures
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Optimization and Control (math.OC)
[33] arXiv:2611.13575 (cross-list from cs.DS) [pdf, html, other]
Title: Greedy+Singleton for knapsack-constrained monotone submodular maximization has approximation ratio exactly $β^\star \approx 0.42944$
Kundan Baliga, Aiden Xie, Aditya Byju
Comments: 26 pages, 4 figures. Code and certificates: this https URL
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[34] arXiv:2611.13224 (cross-list from cs.DS) [pdf, html, other]
Title: An Improved $(1+2e)$-Approximation Algorithm for Metric Data Placement
S. Rasoul Etesami
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Computer Science and Game Theory (cs.GT); Networking and Internet Architecture (cs.NI); Optimization and Control (math.OC)
[35] arXiv:2611.13065 (cross-list from cs.DS) [pdf, html, other]
Title: Combinatorial optimization with bounded subdeterminants
Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon, Sang-il Oum, Roohani Sharma, Stefan Weltge
Comments: 25 pages
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Optimization and Control (math.OC)

Tue, 10 Nov 2026 (showing first 15 of 17 entries )

[36] arXiv:2611.12642 [pdf, html, other]
Title: Non-Uniqueness in the Coordinate-Based Normalization of Tetrahedral Similarity Classes
Miguel Ángel Padrón, Agustín Trujillo-Pino, Jose Pablo Suárez
Subjects: Discrete Mathematics (cs.DM)
[37] arXiv:2611.11376 [pdf, html, other]
Title: Fractional distance-edge-monitoring in lexicographic products
Xiumin Wang, Minglei Mao, Yaping Mao, Ralf Klasing
Subjects: Discrete Mathematics (cs.DM)
[38] arXiv:2611.10920 [pdf, html, other]
Title: Positivity Proofs for Third-Order Holonomic Sequences via Differences Scaled by Rational Functions
Fugen Hagihara
Comments: 23 pages, 1 figure
Subjects: Discrete Mathematics (cs.DM); Symbolic Computation (cs.SC); Dynamical Systems (math.DS)
[39] arXiv:2611.10701 [pdf, html, other]
Title: Weighted Matroid Intersection under Minimum Rank Oracle
Taihei Oki
Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO); Optimization and Control (math.OC)
[40] arXiv:2611.10624 [pdf, html, other]
Title: A Simple Computer-Assisted Proof of the 5/6-Bound for Real-Period Pinwheel Scheduling
Hiroshi Fujiwara, Grzegorz Gutowski, Katsuhisa Ouchi, Alexander Wolff
Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[41] arXiv:2611.12619 (cross-list from cs.DS) [pdf, html, other]
Title: Better Bounds For Graph Reconstruction
Antoni Buraczewski, Paweł Gawrychowski
Comments: in FOCS 2026
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[42] arXiv:2611.12358 (cross-list from math.CO) [pdf, html, other]
Title: Induced packing treewidth III. Branch decompositions
Amir Nikabadi, Paweł Rzążewski
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[43] arXiv:2611.12330 (cross-list from math.CO) [pdf, html, other]
Title: Cut Conditions, Integrality, and Obstructions for Directed Multiflows
Srinwanti Debgupta, Martin Skutella, Philipp Warode
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[44] arXiv:2611.12034 (cross-list from cs.DS) [pdf, html, other]
Title: The Power of Migration on Identical Machines is Two
Nicole Megow, Bart Zondervan
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[45] arXiv:2611.11444 (cross-list from cs.DS) [pdf, html, other]
Title: Tight B-Trees for Adjacency Labeling
Noy Rotbart
Comments: 8 pages, 2 figures
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[46] arXiv:2611.11375 (cross-list from cs.CC) [pdf, html, other]
Title: Linear Objective Problems: A Complexity Framework for Bilevel Optimization
Christoph Grüne, James B. Orlin, Lasse Wulf
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Optimization and Control (math.OC)
[47] arXiv:2611.11280 (cross-list from math.CO) [pdf, html, other]
Title: Impropriety and resilience of the chromatic number
Ross J. Kang, Colin McDiarmid
Comments: 22 pages
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Probability (math.PR)
[48] arXiv:2611.11126 (cross-list from math.CO) [pdf, html, other]
Title: Lower bound on the size of splitting systems
Fan Chung, Namiko Matsumoto, Arya Mazumdar
Comments: 13 pages
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
[49] arXiv:2611.11093 (cross-list from cs.CV) [pdf, html, other]
Title: Does Pose Encoding Matter? Analyzing Geometric Representations for Discrete Motion Vocabulary Learning
Amir Kimiyaie, Nahal Mafi, Hamed Tabkhi
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM)
[50] arXiv:2611.10311 (cross-list from math.DS) [pdf, html, other]
Title: Up or down by half: a family of Collatz-type maps
Oleg Vasilyev
Subjects: Dynamical Systems (math.DS); Discrete Mathematics (cs.DM)
Total of 58 entries : 1-50 51-58
Showing up to 50 entries per page: fewer | more | all
We gratefully acknowledge support from our major funders, member institutions, , and all contributors.
About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab)