Discrete Mathematics

Authors and titles for recent submissions

• Thu, 21 May 2020
• Wed, 20 May 2020
• Tue, 19 May 2020
• Mon, 18 May 2020
• Fri, 15 May 2020

Thu, 21 May 2020

[1]  arXiv:2005.10182 [pdf, other]

Title: The Iteration Number of Colour Refinement

Authors: Sandra Kiefer, Brendan D. McKay

Comments: 22 pages, 3 figures, full version of a paper accepted at ICALP 2020

Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Combinatorics (math.CO)

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

Title: Improved bounds for some facially constrained colorings

Authors: Kenny Štorgel

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

[3]  arXiv:2005.09922 (cross-list from math.CO) [pdf, ps, other]

Title: On Limit Constants in Last Passage Percolation in Transitive Tournaments

Authors: Kunal Dutta

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

[4]  arXiv:2005.09762 (cross-list from eess.SP) [pdf, other]

Title: Digraph Signal Processing with Generalized Boundary Conditions

Authors: Bastian Seifert, Markus Püschel

Comments: 13 pages, 22 figures

Subjects: Signal Processing (eess.SP); Discrete Mathematics (cs.DM)

Wed, 20 May 2020

[5]  arXiv:2005.09540 [pdf, other]

Title: Growth of bilinear maps

Authors: Vuong Bui

Comments: 10 pages, 1 figure

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

[6]  arXiv:2005.09447 [pdf, ps, other]

Title: Graphs with no induced house nor induced hole have the de Bruijn-Erdős property

Authors: Pierre Aboulker, Laurent Beaudou, Martín Matamala, José Zamora

Comments: 16 pages

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

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

Title: A Frameless 2-Coloring of the Plane Lattice

Authors: Craig S. Kaplan, Jeffrey Shallit

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

[8]  arXiv:2005.09524 (cross-list from cs.DS) [pdf, other]

Title: On repetitiveness measures of Thue-Morse words

Authors: Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

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

[9]  arXiv:2005.09507 (cross-list from cs.FL) [pdf, ps, other]

Title: Decidability and k-Regular Sequences

Authors: Daniel Krenn, Jeffrey Shallit

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

Tue, 19 May 2020

[10]  arXiv:2005.08058 [pdf, other]

Title: A Linear Time Algorithm for Computing the Eternal Vertex Cover Number of Cactus Graphs

Authors: Jasine Babu, Veena Prabhakaran, Arko Sharma

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

[11]  arXiv:2005.08636 (cross-list from math.OC) [pdf, other]

Title: A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks

Authors: Divyam Aggarwal, Dhish Kumar Saxena, Thomas Bäck, Michael Emmerich

Comments: 22 pages, 6 figures, Manuscript to be submitted to a refereed journal

Subjects: Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM)

[12]  arXiv:2005.08584 (cross-list from cs.GT) [pdf, ps, other]

Title: Two-Sided Random Matching Markets: Ex-Ante Equivalence of the Deferred Acceptance Procedures

Authors: Simon Mauras

Comments: Accepted for publication in the 21st ACM Conference on Economics and Computation (EC'20)

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

[13]  arXiv:2005.08263 (cross-list from cs.DS) [pdf, other]

Title: Matching in Stochastically Evolving Graphs

Authors: Eleni C. Akrida, Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, Viktor Zamaraev

Comments: 12 pages, 3 figures

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

[14]  arXiv:2005.07959 (cross-list from cs.LG) [pdf, other]

Title: Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models

Authors: Benedek Rozemberczki, Rik Sarkar

Subjects: Machine Learning (cs.LG); Discrete Mathematics (cs.DM); Social and Information Networks (cs.SI); Machine Learning (stat.ML)

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

Title: Circulant almost cross intersecting families

Authors: Michal Parnas

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

Mon, 18 May 2020

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

Title: Propagation time for weighted zero forcing

Authors: P.A. CrowdMath

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

[17]  arXiv:2005.07311 (cross-list from math.CO) [pdf, ps, other]

Title: Broadcast Dimension of Graphs

Authors: Jesse Geneson, Eunjeong Yi

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

Fri, 15 May 2020

[18]  arXiv:2005.06751 [pdf, ps, other]

Title: The Interval function, Ptolemaic, distance hereditary, bridged graphs and axiomatic characterizations

Authors: Manoj Changat, Lekshmi Kamal K. Sheela, Prasanth G. Narasimha-Shenoi

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

• Thu, 21 May 2020
• Wed, 20 May 2020
• Tue, 19 May 2020
• Mon, 18 May 2020
• Fri, 15 May 2020