Discrete Mathematics

Authors and titles for recent submissions

• Fri, 21 Jun 2024
• Wed, 19 Jun 2024
• Tue, 18 Jun 2024
• Mon, 17 Jun 2024
• Fri, 14 Jun 2024

See today's new changes

Fri, 21 Jun 2024 (showing 9 of 9 entries )

[1] arXiv:2406.13620 [pdf, html, other]

Title: An Algorithm for the Assignment Game Beyond Additive Valuations

Eric Balkanski, Christopher En, Yuri Faenza

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

[2] arXiv:2406.13529 [pdf, other]

Title: GMSNP and Finite Structures

Santiago Guzmán-Pro

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

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

Title: Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities

Will Ma, Calum MacRury, Pranav Nuti

Journal-ref: In EC 2024

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

[4] arXiv:2406.14402 (cross-list from cs.LO) [pdf, html, other]

Title: Logic-based analogical proportions

Christian Antić

Subjects: Logic in Computer Science (cs.LO); Discrete Mathematics (cs.DM); Logic (math.LO)

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

Title: Multicoloured Hardcore Model: Fast Mixing and Queueing

Sam Olesker-Taylor

Comments: 12 pages. To appear at Analysis of Algorithms (AofA) 2024. Minor typo-correction and improvements to that version

Subjects: Probability (math.PR); Discrete Mathematics (cs.DM)

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

Title: Signed combinatorial interpretations in algebraic combinatorics

Igor Pak, Colleen Robichaux

Comments: 23 pages

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

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

Title: Error-Correcting Graph Codes

Swastik Kopparty, Aditya Potukuchi, Harry Sha

Comments: 27 pages, 3 figures, 1 table

Subjects: Information Theory (cs.IT); Discrete Mathematics (cs.DM)

[8] arXiv:2406.13452 (cross-list from quant-ph) [pdf, html, other]

Title: Quantum Networks: from Multipartite Entanglement to Hypergraph Immersion

Yu Tian, Yuefei Liu, Xiangyi Meng

Comments: 8 pages, 3 figures, 1 table

Subjects: Quantum Physics (quant-ph); Discrete Mathematics (cs.DM); Social and Information Networks (cs.SI); Computational Physics (physics.comp-ph); Physics and Society (physics.soc-ph)

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

Title: Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs

Aditi Dudeja, Rashmika Goswami, Michael Saks

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

Wed, 19 Jun 2024 (showing 2 of 2 entries )

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

Title: Small maximal clusters are very unlikely in critical random graphs

Umberto De Ambroggio

Subjects: Probability (math.PR); Discrete Mathematics (cs.DM)

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

Title: Pushing the Frontier on Approximate EFX Allocations

Georgios Amanatidis, Aris Filos-Ratsikas, Alkmini Sgouritsa

Comments: The conference version of this work has been accepted to the Twenty-Fifth ACM Conference on Economics and Computation (EC 2024)

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

Tue, 18 Jun 2024 (showing 4 of 4 entries )

[12] arXiv:2406.10772 [pdf, html, other]

Title: On the maximal L1 influence of real-valued boolean functions

Andrew J. Young, Henry D. Pfister

Subjects: Discrete Mathematics (cs.DM)

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

Title: Treewidth Inapproximability and Tight ETH Lower Bound

Édouard Bonnet

Comments: 10 pages, 1 figure

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

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

Title: Optimizing alphabet reduction pairs of arrays

Jean-François Culus, Sophie Toulouse

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

[15] arXiv:2406.10423 (cross-list from cs.SI) [pdf, html, other]

Title: A comprehensive generalization of the Friendship Paradox to weights and attributes

Anna Evtushenko, Jon Kleinberg

Comments: 34 pages, 4 figures

Journal-ref: Sci Rep 14, 13730 (2024)

Subjects: Social and Information Networks (cs.SI); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

Mon, 17 Jun 2024 (showing 1 of 1 entries )

[16] arXiv:2406.09868 (cross-list from cs.FL) [pdf, html, other]

Title: Addition in Dumont-Thomas Numeration Systems in Theory and Practice

Olivier Carton, Jean-Michel Couvreur, Martin Delacourt, Nicolas Ollinger

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

Fri, 14 Jun 2024 (showing 3 of 3 entries )

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

Title: On the Expressibility of the Reconstructional Color Refinement

V. Arvind, Johannes Köbler, Oleg Verbitsky

Comments: 9 pages

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

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

Title: The reflection complexity of sequences over finite alphabets

Jean-Paul Allouche, John M. Campbell, Jeffrey Shallit, Manon Stipulanti

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

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

Title: A Sublinear Algorithm for Approximate Shortest Paths in Large Networks

Sabyasachi Basu, Nadia Kōshima, Talya Eden, Omri Ben-Eliezer, C. Seshadhri

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Social and Information Networks (cs.SI)