Discrete Mathematics

Authors and titles for cs.DM in Aug 2021

[1]  arXiv:2108.00405 [pdf, ps, other]

Title: Computation of the Activity-on-Node Binary-State Reliability with Uncertainty Components

Authors: Wei-Chang Yeh

Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO); Optimization and Control (math.OC); Probability (math.PR)

[2]  arXiv:2108.02367 [pdf, other]

Title: Evacuating from ell_p Unit Disks in the Wireless Model

Authors: Konstantinos Georgiou, Sean Leizerovich, Jesse Lucier, Somnath Kundu

Comments: 21 pages, 9 figures

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

[3]  arXiv:2108.02480 [pdf, ps, other]

Title: Bifactor Approximation for Location Routing with Vehicle and Facility Capacities

Authors: Felipe Carrasco Heine, Antonia Demleitner, Jannik Matuschke

Subjects: Discrete Mathematics (cs.DM)

[4]  arXiv:2108.02729 [pdf, ps, other]

Title: Counting scattered palindromes in a finite word

Authors: Kalpana Mahalingam, Palak Pandoh

Subjects: Discrete Mathematics (cs.DM)

[5]  arXiv:2108.02997 [pdf, ps, other]

Title: Adjusting PageRank parameters and Comparing results

Authors: Subhajit Sahu, Kishore Kothapalli, Dip Sankar Banerjee

Comments: 13 pages, 10 figures, 2 tables

Subjects: Discrete Mathematics (cs.DM)

[6]  arXiv:2108.03018 [pdf, other]

Title: Conditional Separation as a Binary Relation. A Coq Assisted Proof

Authors: Jean-Philippe Chancelier (CERMICS), Michel de Lara (CERMICS), Benjamin Heymann

Subjects: Discrete Mathematics (cs.DM)

[7]  arXiv:2108.03096 [pdf, ps, other]

Title: Topological Conditional Separation

Authors: Michel de Lara, Jean-Philippe Chancelier (CERMICS), Benjamin Heymann

Subjects: Discrete Mathematics (cs.DM); General Topology (math.GN)

[8]  arXiv:2108.03099 [pdf, other]

Title: Causal Inference Theory with Information Dependency Models

Authors: Benjamin Heymann, Michel de Lara (CERMICS), Jean-Philippe Chancelier (CERMICS)

Subjects: Discrete Mathematics (cs.DM); Information Theory (cs.IT); General Topology (math.GN)

[9]  arXiv:2108.03335 [pdf, other]

Title: On the complexity of the generalized Q2R automaton

Authors: Eric Goles (Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile), Marco Montalva-Medel (Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile), Pedro Montealegre (Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile), Martín Ríos-Wilson (Departamento de Ingeniería Matemática, FCFM, Universidad de Chile, Santiago, Chile and Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France)

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

[10]  arXiv:2108.04150 [pdf, ps, other]

Title: Effect of stepwise adjustment of Damping factor upon PageRank

Authors: Subhajit Sahu, Kishore Kothapalli, Dip Sankar Banerjee

Comments: 4 pages, 1 figure

Subjects: Discrete Mathematics (cs.DM)

[11]  arXiv:2108.05231 [pdf, ps, other]

Title: Nonexistence of a Universal Algorithm for Traveling Salesman Problems in Constructive Mathematics

Authors: Linglong Dai

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

[12]  arXiv:2108.05569 [pdf, ps, other]

Title: Agnostic Online Learning and Excellent Sets

Authors: Maryanthe Malliaris, Shay Moran

Subjects: Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Logic in Computer Science (cs.LO); Combinatorics (math.CO); Logic (math.LO)

[13]  arXiv:2108.07671 [pdf, other]

Title: Implementation of Sprouts: a graph drawing game

Authors: Tomáš Čížek, Martin Balko

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

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

[14]  arXiv:2108.10458 [pdf, other]

Title: Supernodes

Authors: Su Yuan Chan, Kerri Morgan, Nick Parsons, Julien Ugon

Subjects: Discrete Mathematics (cs.DM)

[15]  arXiv:2108.10554 [pdf, ps, other]

Title: A proof of the Multiplicative 1-2-3 Conjecture

Authors: Julien Bensmail (COATI), Hervé Hocquard (LaBRI), Dimitri Lajou (LaBRI), Éric Sopena (LaBRI)

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

[16]  arXiv:2108.11443 [pdf, other]

Title: Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics

Authors: Markus Chimani, Max Ilsen, Tilo Wiedera

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021); 22 pages with 12 figures; v2: legend in Fig. 5 fixed; v3: higher contrast colors & better plot readability

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

[17]  arXiv:2108.11496 [pdf, other]

Title: A Class of Trees Having Near-Best Balance

Authors: Laura Monroe

Comments: 60 pages, 10 figures

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

[18]  arXiv:2108.12327 [pdf, other]

Title: On the Upward Book Thickness Problem: Combinatorial and Complexity Results

Authors: Sujoy Bhore, Giordano Da Lozzo, Fabrizio Montecchiani, Martin Nöllenburg

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

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

[19]  arXiv:2108.00059 (cross-list from cs.DC) [pdf, other]

Title: Local certification of graph decompositions and applications to minor-free classes

Authors: Nicolas Bousquet, Laurent Feuilloley, Théo Pierron

Comments: New version with expanded introduction and various fixes

Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)

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

Title: Recognizing and Embedding Simple Optimal 2-Planar Graphs

Authors: Henry Förster, Michael Kaufmann, Chrysanthi N. Raftopoulou

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

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

[21]  arXiv:2108.00938 (cross-list from cs.AI) [pdf, other]

Title: Machine Learning Constructives and Local Searches for the Travelling Salesman Problem

Authors: Tommaso Vitali, Umberto Junior Mele, Luca Maria Gambardella, Roberto Montemanni

Subjects: Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM); Machine Learning (cs.LG)

[22]  arXiv:2108.01417 (cross-list from cs.IT) [pdf, ps, other]

Title: On the Structure of the Binary LCD Codes having an Automorphism of Odd Prime Order

Authors: Stefka Bouyuklieva, Javier de la Cruz

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

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

Title: Geometric Embeddability of Complexes is $\exists \mathbb R$-complete

Authors: Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow

Comments: 26 pages, 18 figures

Subjects: Computational Complexity (cs.CC); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Combinatorics (math.CO); General Topology (math.GN)

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

Title: EPTAS for load balancing problem on parallel machines with a non-renewable resource

Authors: G. Jaykrishnan, Asaf Levin

Comments: An earlier extended abstract version appears in proceedings of WAOA'21

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Optimization and Control (math.OC)

[25]  arXiv:2108.04342 (cross-list from cs.IT) [pdf, ps, other]

Title: Near optimal efficient decoding from pooled data

Authors: Max Hahn-Klimroth, Noela Müller

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

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

Title: Automatic Sequences of Rank Two

Authors: Jason Bell, Jeffrey Shallit

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

[27]  arXiv:2108.05911 (cross-list from eess.SY) [pdf, other]

Title: Synthesis of Static Test Environments for Observing Sequence-like Behaviors in Autonomous Systems

Authors: Apurva Badithela, Richard M. Murray

Comments: Technical Report

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

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

Title: A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method

Authors: Miriam Schlöter, Martin Skutella, Khai Van Tran

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

[29]  arXiv:2108.06650 (cross-list from cs.DC) [pdf, other]

Title: Vertical, Temporal, and Horizontal Scaling of Hierarchical Hypersparse GraphBLAS Matrices

Authors: Jeremy Kepner, Tim Davis, Chansup Byun, William Arcand, David Bestor, William Bergeron, Vijay Gadepally, Matthew Hubbell, Michael Houle, Michael Jones, Anna Klein, Lauren Milechin, Julie Mullen, Andrew Prout, Albert Reuther, Antonio Rosa, Siddharth Samsi, Charles Yee, Peter Michaleas

Comments: 6 pages, 5 figures, 32 references, accepted to IEEE HPEC 2021. arXiv admin note: text overlap with arXiv:2001.06935

Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Discrete Mathematics (cs.DM); Mathematical Software (cs.MS); Networking and Internet Architecture (cs.NI); Performance (cs.PF)

[30]  arXiv:2108.06832 (cross-list from cs.AI) [pdf, other]

Title: A Fast Algorithm for Computing the Deficiency Number of a Mahjong Hand

Authors: Xueqing Yan, Yongming Li, Sanjiang Li

Comments: 32 pages, 3 figures

Subjects: Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM); Multiagent Systems (cs.MA)

[31]  arXiv:2108.07318 (cross-list from cs.IT) [pdf, ps, other]

Title: Peak Sidelobe Level and Peak Crosscorrelation of Golay-Rudin-Shapiro Sequences

Authors: Daniel J. Katz, Courtney M. van der Linden

Comments: 39 pages

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

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

Title: Uniformity Testing in the Shuffle Model: Simpler, Better, Faster

Authors: Clément L. Canonne, Hongyi Lyu

Comments: Accepted to the SIAM Symposium on Simplicity in Algorithms (SOSA 2022). Added some details and discussions

Subjects: Data Structures and Algorithms (cs.DS); Cryptography and Security (cs.CR); Discrete Mathematics (cs.DM); Machine Learning (stat.ML)

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

Title: A Pivot Gray Code Listing for the Spanning Trees of the Fan Graph

Authors: Ben Cameron, Aaron Grubb, Joe Sawada

Comments: Accepted for publication in International Computing and Combinatorics Conference (COCOON 2021)

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

[34]  arXiv:2108.09483 (cross-list from cs.CG) [pdf, other]

Title: From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs

Authors: Giuseppe Di Battista, Fabrizio Frati

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

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

[35]  arXiv:2108.09832 (cross-list from cs.CG) [pdf, ps, other]

Title: On universal covers for carpenter's rule folding

Authors: Rain Jiang, Kai Jiang, Minghui Jiang

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

[36]  arXiv:2108.09851 (cross-list from cs.DS) [pdf, ps, other]

Title: A Framework for Computing Greedy Clique Cover

Authors: Ahammed Ullah

Comments: 28 Pages, 6 Figures

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

[37]  arXiv:2108.10224 (cross-list from cs.AI) [pdf, other]

Title: A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem

Authors: Umberto Junior Mele, Luca Maria Gambardella, Roberto Montemanni

Journal-ref: Algorithms 2021

Subjects: Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM); Machine Learning (cs.LG)

[38]  arXiv:2108.10398 (cross-list from cs.DS) [pdf, ps, other]

Title: Approximation and parameterized algorithms to find balanced connected partitions of graphs

Authors: Phablo F. S. Moura, Matheus J. Ota, Yoshiko Wakabayashi

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

[39]  arXiv:2108.10606 (cross-list from cs.CV) [pdf, other]

Title: Making Higher Order MOT Scalable: An Efficient Approximate Solver for Lifted Disjoint Paths

Authors: Andrea Hornakova, Timo Kaiser, Paul Swoboda, Michal Rolinek, Bodo Rosenhahn, Roberto Henschel

Comments: ICCV 2021. Short version published at CVPR 2021 RVSU workshop this https URL . Implementation available at this https URL and this https URL

Subjects: Computer Vision and Pattern Recognition (cs.CV); Discrete Mathematics (cs.DM)

[40]  arXiv:2108.11280 (cross-list from cs.IT) [pdf, ps, other]

Title: Encoding Scheme for Infinite Set of Symbols: The Percolation Process on Infinite Perfect Binary Trees

Authors: Yousof Mardoukhi

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

[41]  arXiv:2108.11646 (cross-list from cs.IT) [pdf, ps, other]

Title: A promotion for odd symmetric discrete Fourier transform

Authors: Rui Li

Comments: 12 pages, 5 figures, regular article

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

[42]  arXiv:2108.12303 (cross-list from cs.DS) [pdf, ps, other]

Title: The Stochastic Bilevel Continuous Knapsack Problem with Uncertain Follower's Objective

Authors: Christoph Buchheim, Dorothee Henke, Jannik Irmai

Comments: A preliminary version of parts of this article can be found in Section 8 of arXiv:1903.02810v2

Journal-ref: Journal of Optimization Theory and Applications 194(2), 521-542 (2022)

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Optimization and Control (math.OC)

[43]  arXiv:2108.12464 (cross-list from cs.CG) [pdf, other]

Title: Bottleneck Convex Subsets: Finding $k$ Large Convex Sets in a Point Set

Authors: Stephane Durocher, J. Mark Keil, Saeed Mehrabi, Debajyoti Mondal

Comments: Preliminary results appeared at the 27th International Computing and Combinatorics Conference (COCOON 2021)

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

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

Title: Positive Planar Satisfiability Problems under 3-Connectivity Constraints

Authors: Md. Manzurul Hasan, Debajyoti Mondal, Md. Saidur Rahman

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

[45]  arXiv:2108.12658 (cross-list from math.NA) [pdf, other]

Title: Clusters in Markov Chains via Singular Vectors of Laplacian Matrices

Authors: Sam Cole, Steve Kirkland

Comments: 41 pages, 10 figures

Subjects: Numerical Analysis (math.NA); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)

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

Title: Extending Partial Representations of Circular-Arc Graphs

Authors: Jiří Fiala, Ignaz Rutter, Peter Stumpf, Peter Zeman

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

[47]  arXiv:2108.13280 (cross-list from cs.IT) [pdf, other]

Title: Trims and Extensions of Quadratic APN Functions

Authors: Christof Beierle, Gregor Leander, Léo Perrin

Journal-ref: Des. Codes Cryptogr. 90(4): 1009-1036 (2022)

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

[48]  arXiv:2108.13338 (cross-list from cs.DS) [pdf, ps, other]

Title: Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees

Authors: Zhuan Khye Koh, Georg Loho

Comments: 33 pages, 8 figures

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO)

[49]  arXiv:2108.13659 (cross-list from cs.CL) [pdf, ps, other]

Title: Gray Cycles of Maximum Length Related to k-Character Substitutions

Authors: Jean Néraud (LITIS, UNIROUEN)

Subjects: Computation and Language (cs.CL); Discrete Mathematics (cs.DM)

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

Title: Mixing colourings in $2K_2$-free graphs

Authors: Carl Feghali, Owen Merkel

Comments: 4 pages, 2 figures

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

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

Title: The Pyro game: a slow intelligent fire

Authors: Margaret-Ellen Messinger, Spencer Yarnell

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

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

Title: An improved planar graph product structure theorem

Authors: Torsten Ueckerdt, David R. Wood, Wendy Yi

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

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

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

Title: Bipartite Graft III: General Case

Authors: Nanao Kita

Comments: Sequel of arXiv:2101.06678

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

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

Title: On the maximum number of distinct intersections in an intersecting family

Authors: Peter Frankl, Sergei Kiselev, Andrey Kupavskii

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

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

Title: Choice number of Kneser graphs

Authors: Vera Bulankina, Andrey Kupavskii

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

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

Title: The tripartite-circle crossing number of graphs with two small partition classes

Authors: Charles Camacho, Silvia Fernández-Merchant, Marija Jelić Milutinović, Rachel Kirsch, Linda Kleist, Elizabeth Bailey Matson, Jennifer White

Comments: 22 pages, 11 figures. Added new results and revised throughout. Originally appeared in arXiv:1910.06963v1, now removed from arXiv:1910.06963v2

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

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

Title: Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs

Authors: Michelle Delcourt, Luke Postle

Comments: 25 pages. In this version, some minor typos fixed. Previously updated in response to referee comments. This and the three previous versions add the necessary results from arXiv:2006.11798 in order to create a self-contained standalone paper. arXiv admin note: text overlap with arXiv:2006.11798, arXiv:2010.05999

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

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

Title: Combinatorial Algorithms for Multidimensional Necklaces

Authors: Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, Igor Potapov

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

[59]  arXiv:2108.02873 (cross-list from math.GT) [pdf, ps, other]

Title: Circle graphs (chord interlacement graphs) of Gauss diagrams: Descriptions of realizable Gauss diagrams, algorithms, enumeration

Authors: Abdullah Khan, Alexei Lisitsa, Viktor Lopatkin, Alexei Vernitski

Comments: 25 pages

Subjects: Geometric Topology (math.GT); Discrete Mathematics (cs.DM)

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

Title: Complexity of Restricted Star Colouring

Authors: Shalu M. A., Cyriac Antony

Comments: Discrete Applied Mathematics (2021)

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

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

Title: Circuit imbalance measures and linear programming

Authors: Farbod Ekbatani, Bento Natura, László A. Végh

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

[62]  arXiv:2108.04077 (cross-list from q-bio.MN) [pdf, other]

Title: Cayley Graphs of Semigroups Applied to Atom Tracking in Chemistry

Authors: Nikolai Nøjgaard, Walter Fontana, Marc Hellmuth, Daniel Merkle

Subjects: Molecular Networks (q-bio.MN); Discrete Mathematics (cs.DM)

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

Title: A Note on Squares in Binary Words

Authors: Tero Harju

Comments: 6 pages

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

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

Title: Tangled Paths: A Random Graph Model from Mallows Permutations

Authors: Jessica Enright, Kitty Meeks, William Pettersson, John Sylvester

Comments: 36 pages, 7 figures. Strengthened Theorems 1.1 & 1.4

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

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

Title: Linear Layouts of Complete Graphs

Authors: Stefan Felsner, Laura Merker, Torsten Ueckerdt, Pavel Valtr

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

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

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

Title: Linear Bounds for Cycle-free Saturation Games

Authors: Sean English, Tomáš Masařík, Grace McCourt, Erin Meger, Michael S. Ross, Sam Spiro

Comments: 18 pages, 2 figures

Journal-ref: The Electronic Journal of Combinatorics 29(3), 5:1-5:21, 2022

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

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

Title: Some Results on $k$-Critical $P_5$-Free Graphs

Authors: Qingqiong Cai, Jan Goedgebeur, Shenwei Huang

Comments: 15 pages, 4 figures. arXiv admin note: substantial text overlap with arXiv:2005.03441

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

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

Title: Grounded L-graphs are polynomially $χ$-bounded

Authors: James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak

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

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

Title: Subcubic planar graphs of girth 7 are class I

Authors: Sebastien Bonduelle, František Kardoš

Comments: 7 pages plus 6 pages of annex; 11 figures

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

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

Title: A scaleable projection-based branch-and-cut algorithm for the $p$-center problem

Authors: Elisabeth Gaar, Markus Sinnl

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

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

Title: Star transposition Gray codes for multiset permutations

Authors: Petr Gregor, Arturo Merino, Torsten Mütze

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

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

Title: Minimum degree conditions for containing an $r$-regular $r$-connected subgraph

Authors: Max Hahn-Klimroth, Olaf Parczyk, Yury Person

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

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

Title: Arbitrary-length analogs to de Bruijn sequences

Authors: Abhinav Nellore, Rachel Ward

Comments: 18 pages, 3 algorithms, 1 table; v2 refines language and fixes references

Journal-ref: CPM 2022

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

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

Title: Exact enumeration of satisfiable 2-SAT formulae

Authors: Sergey Dovgal, Élie de Panafieu, Vlady Ravelomanana

Comments: 29 pages, 6 tables, 10 figures. For associated python code, see this https URL

Subjects: Combinatorics (math.CO); Statistical Mechanics (cond-mat.stat-mech); Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO)

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

Title: Efficient Algorithms for Stochastic Ridepooling Assignment with Mixed Fleets

Authors: Qi Luo, Viswanath Nagarajan, Alexander Sundt, Yafeng Yin, John Vincent, Mehrdad Shahabi

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

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

Title: On the Queue-Number of Partial Orders

Authors: Stefan Felsner, Torsten Ueckerdt, Kaja Wille

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

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

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

Title: Primal and Dual Combinatorial Dimensions

Authors: Pieter Kleer, Hans Simon

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

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

Title: Another simple reformulation of the four color theorem

Authors: Ajit Diwan

Comments: 3 pages

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

[79]  arXiv:2108.11003 (cross-list from math.PR) [pdf, other]

Title: Matchings on Random Regular Hypergraphs

Authors: Zhongyang Li

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

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

Title: On the extremal values of the cyclic continuants of Motzkin and Straus

Authors: Alessandro De Luca (1), Luca Q. Zamboni (2) ((1) DIETI, Università di Napoli Federico II, Italy, (2) Institut Camille Jordan, CNRS UMR 5208, Université Lyon 1, France)

Comments: Preliminary version, 21 pages

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

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

Title: Optimal Radio Labellings of Block Graphs and Line Graphs of Trees

Authors: Devsi Bantva, Daphne Der-Fen Liu

Comments: 21 pages, 4 figures. This is the final version accepted in Theoretical Computer Science(TCS) Journal

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

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

Title: Well-mixing vertices and almost expanders

Authors: Debsoumya Chakraborti, Jaehoon Kim, Jinha Kim, Minki Kim, Hong Liu

Comments: accepted in PAMS

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