Discrete Mathematics

Authors and titles for August 2025

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

Title: Computation of Approximately Stable Committees in Approval-based Elections

Drew Gao, Yihang Sun, Jan Vondrák

Comments: 18 pages, 2 figures

Subjects: Computer Science and Game Theory (cs.GT); Discrete Mathematics (cs.DM)

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

Title: Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

Shuichi Hirahara, Naoto Ohsaka

Comments: To appear in Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025)

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

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

Title: On the Equivalence of the Graph-Structural and Optimization-Based Characterizations of Popular Matchings

Yuga Kanaya, Kenjiro Takazawa

Subjects: Computer Science and Game Theory (cs.GT); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

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

Title: Edge open packing: further characterizations

Arti Pandey, Kamal Santra

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

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

Title: An Improved Bound for the Beck-Fiala Conjecture

Nikhil Bansal, Haotian Jiang

Comments: To appear in FOCS 2025. The result in this paper is subsumed by follow-up work by the authors

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

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

Title: Testing Quasiperiodicity

Christine Awofeso, Ben Bals, Oded Lachish, Solon P. Pissis

Comments: To appear at SPIRE 2025

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

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

Title: Thresholds of Queen covers

Tirthankar Adhikari, Harman Agrawal, Anjali Bhagat, Ankita Dargad, Sahana Jahagirdar, Prem Kant, Urban Larsson, Sahil Wagh

Comments: 21 pages, 7 indexed figures

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