CINXE.COM
Discrete Mathematics
<!DOCTYPE html> <html lang="en"> <head> <title>Discrete Mathematics </title> <meta name="viewport" content="width=device-width, initial-scale=1"> <link rel="apple-touch-icon" sizes="180x180" href="/static/browse/0.3.4/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="/static/browse/0.3.4/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="/static/browse/0.3.4/images/icons/favicon-16x16.png"> <link rel="manifest" href="/static/browse/0.3.4/images/icons/site.webmanifest"> <link rel="mask-icon" href="/static/browse/0.3.4/images/icons/safari-pinned-tab.svg" color="#5bbad5"> <meta name="msapplication-TileColor" content="#da532c"> <meta name="theme-color" content="#ffffff"> <link rel="stylesheet" type="text/css" media="screen" href="/static/browse/0.3.4/css/arXiv.css?v=20241206" /> <link rel="stylesheet" type="text/css" media="print" href="/static/browse/0.3.4/css/arXiv-print.css?v=20200611" /> <link rel="stylesheet" type="text/css" media="screen" href="/static/browse/0.3.4/css/browse_search.css" /> <script language="javascript" src="/static/browse/0.3.4/js/accordion.js" /></script> <link rel="stylesheet" type="text/css" media="screen" href="/static/browse/0.3.4/css/slider.css?v=20250312" /> <script src="//code.jquery.com/jquery-latest.min.js" type="text/javascript"></script> <script type="text/javascript" src="/static/browse/0.3.4/js/donate.js?v=040725"></script><script src="/static/browse/0.3.4/js/mathjaxToggle.min.js" type="text/javascript"></script> <script type="text/javascript" language="javascript">mathjaxToggle();</script> </head> <body class="with-cu-identity"> <aside class="slider-wrapper bps-banner forum green"> <a class="close-slider do-close-slider bps-banner" href="#"><img src="/static/browse/0.3.4/images/icons/close-slider.png" alt="close this message"></a> <div class="columns"> <img role="presentation" class="bps-banner-image" src="/static/browse/0.3.4/images/icons/smileybones-pixel.png" alt="arXiv smileybones"> <div class="copy-donation bps-banner"> <h2>arXiv Is Hiring Software Developers</h2> <p>Work on one of the world's most important websites and make an impact on open science.</p> </div> <div class="amount-donation bps-banner"> <div class="donate-cta"><a class="banner_link banner-btn-grad" target="_blank" href="https://info.arxiv.org/hiring/index.html"><b>View Jobs</b></a></div> </div> </div> </aside> <div class="flex-wrap-footer"> <header> <a href="#content" class="is-sr-only">Skip to main content</a> <!-- start desktop header --> <div class="columns is-vcentered is-hidden-mobile" id="cu-identity"> <div class="column" id="cu-logo"> <a href="https://www.cornell.edu/"><img src="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg" alt="Cornell University" /></a> </div> <!-- /from April 7 at 1:00 AM to June 9 at 11:30 PM --><div class="column banner-minimal forum"> <p>arXiv Is Hiring Software Devs</p> <a href="https://info.arxiv.org/hiring/index.html" target="_blank">View Jobs</a> </div><div class="column" id="support-ack"> <span id="support-ack-url">We gratefully acknowledge support from the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors.</span> <a href="https://info.arxiv.org/about/donate.html" class="btn-header-donate">Donate</a> </div> </div> <div id="header" class="is-hidden-mobile"> <a aria-hidden="true" tabindex="-1" href="/IgnoreMe"></a> <div class="header-breadcrumbs"> <a href="/"><img src="/static/browse/0.3.4/images/arxiv-logo-one-color-white.svg" alt="arxiv logo" style="height:40px;"/></a> <span>></span> <a href="/list/cs.DM/recent">cs.DM</a> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div><!-- /end desktop header --> <div class="mobile-header"> <div class="columns is-mobile"> <div class="column logo-arxiv"><a href="https://arxiv.org/"><img src="/static/browse/0.3.4/images/arxiv-logomark-small-white.svg" alt="arXiv logo" style="height:60px;" /></a></div> <div class="column logo-cornell"><a href="https://www.cornell.edu/"> <picture> <source media="(min-width: 501px)" srcset="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg 400w" sizes="400w" /> <source srcset="/static/browse/0.3.4/images/icons/cu/cornell_seal_simple_black.svg 2x" /> <img src="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg" alt="Cornell University Logo" /> </picture> </a></div> <div class="column nav" id="toggle-container" role="menubar"> <button class="toggle-control"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-white"><title>open search</title><path d="M505 442.7L405.3 343c-4.5-4.5-10.6-7-17-7H372c27.6-35.3 44-79.7 44-128C416 93.1 322.9 0 208 0S0 93.1 0 208s93.1 208 208 208c48.3 0 92.7-16.4 128-44v16.3c0 6.4 2.5 12.5 7 17l99.7 99.7c9.4 9.4 24.6 9.4 33.9 0l28.3-28.3c9.4-9.4 9.4-24.6.1-34zM208 336c-70.7 0-128-57.2-128-128 0-70.7 57.2-128 128-128 70.7 0 128 57.2 128 128 0 70.7-57.2 128-128 128z"/></svg></button> <div class="mobile-toggle-block toggle-target"> <form class="mobile-search-form" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <input class="input" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <input type="hidden" name="source" value="header"> <input type="hidden" name="searchtype" value="all"> <button class="button">GO</button> </div> </form> </div> <button class="toggle-control"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-white" role="menu"><title>open navigation menu</title><path d="M16 132h416c8.837 0 16-7.163 16-16V76c0-8.837-7.163-16-16-16H16C7.163 60 0 67.163 0 76v40c0 8.837 7.163 16 16 16zm0 160h416c8.837 0 16-7.163 16-16v-40c0-8.837-7.163-16-16-16H16c-8.837 0-16 7.163-16 16v40c0 8.837 7.163 16 16 16zm0 160h416c8.837 0 16-7.163 16-16v-40c0-8.837-7.163-16-16-16H16c-8.837 0-16 7.163-16 16v40c0 8.837 7.163 16 16 16z"/ ></svg></button> <div class="mobile-toggle-block toggle-target"> <nav class="mobile-menu" aria-labelledby="mobilemenulabel"> <h2 id="mobilemenulabel">quick links</h2> <ul> <li><a href="https://arxiv.org/login">Login</a></li> <li><a href="https://info.arxiv.org/help">Help Pages</a></li> <li><a href="https://info.arxiv.org/about">About</a></li> </ul> </nav> </div> </div> </div> </div><!-- /end mobile-header --> </header> <main> <div id="content"> <div id='content-inner'> <div id='dlpage'> <h1>Discrete Mathematics</h1> <ul> <li><a href="#item0">New submissions</a></li> <li><a href="#item3">Cross-lists</a></li> <li><a href="#item11">Replacements</a></li> </ul> <p>See <a id="recent-cs.DM" aria-labelledby="recent-cs.DM" href="/list/cs.DM/recent">recent</a> articles</p> <h3>Showing new listings for Tuesday, 8 April 2025</h3> <div class='paging'>Total of 18 entries </div> <div class='morefewer'>Showing up to 2000 entries per page: <a href=/list/cs.DM/new?skip=0&show=1000 rel="nofollow"> fewer</a> | <span style="color: #454545">more</span> | <span style="color: #454545">all</span> </div> <dl id='articles'> <h3>New submissions (showing 2 of 2 entries)</h3> <dt> <a name='item1'>[1]</a> <a href ="/abs/2504.04821" title="Abstract" id="2504.04821"> arXiv:2504.04821 </a> [<a href="/pdf/2504.04821" title="Download PDF" id="pdf-2504.04821" aria-labelledby="pdf-2504.04821">pdf</a>, <a href="https://arxiv.org/html/2504.04821v1" title="View HTML" id="html-2504.04821" aria-labelledby="html-2504.04821" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.04821" title="Other formats" id="oth-2504.04821" aria-labelledby="oth-2504.04821">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A Customized SAT-based Solver for Graph Coloring </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Brand,+T">Timo Brand</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Faber,+D">Daniel Faber</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Held,+S">Stephan Held</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Mutzel,+P">Petra Mutzel</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 5 figures, 2 tables, source code published at <a href="https://github.com/trewes/ZykovColor" rel="external noopener nofollow" class="link-external link-https">this https URL</a> </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Discrete Mathematics (cs.DM)</span>; Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Logic in Computer Science (cs.LO) </div> <p class='mathjax'> We introduce ZykovColor, a novel SAT-based algorithm to solve the graph coloring problem working on top of an encoding that mimics the Zykov tree. Our method is based on an approach of H茅brard and Katsirelos (2020) that employs a propagator to enforce transitivity constraints, incorporate lower bounds for search tree pruning, and enable inferred propagations. We leverage the recently introduced IPASIR-UP interface for CaDiCal to implement these techniques with a SAT solver. Furthermore, we propose new features that take advantage of the underlying SAT solver. These include modifying the integrated decision strategy with vertex domination hints and using incremental bottom-up search that allows to reuse learned clauses from previous calls. Additionally, we integrate a more efficient clique computation to improve the lower bounds during the search. We validate the effectiveness of each new feature through an experimental analysis. ZykovColor outperforms other state-of-the-art graph coloring implementations on the DIMACS benchmark set. Further experiments on random Erd艖s-R茅nyi graphs show that our new approach dominates state-of-the-art SAT-based methods for both very sparse and highly dense graphs. </p> </div> </dd> <dt> <a name='item2'>[2]</a> <a href ="/abs/2504.04836" title="Abstract" id="2504.04836"> arXiv:2504.04836 </a> [<a href="/pdf/2504.04836" title="Download PDF" id="pdf-2504.04836" aria-labelledby="pdf-2504.04836">pdf</a>, <a href="https://arxiv.org/html/2504.04836v1" title="View HTML" id="html-2504.04836" aria-labelledby="html-2504.04836" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.04836" title="Other formats" id="oth-2504.04836" aria-labelledby="oth-2504.04836">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Strengthening Wilf's lower bound on clique number </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Jadav,+H">Hareshkumar Jadav</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Madyastha,+S">Sreekara Madyastha</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Raut,+R">Rahul Raut</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Singh,+R">Ranveer Singh</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 8 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Discrete Mathematics (cs.DM)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> Given an integer $k$, deciding whether a graph has a clique of size $k$ is an NP-complete problem. Wilf's inequality provides a spectral bound for the clique number of simple graphs. Wilf's inequality is stated as follows: $\frac{n}{n - \lambda_{1}} \leq \omega$, where $\lambda_1$ is the largest eigenvalue of the adjacency matrix $A(G)$, $n$ is the number of vertices in $G$, and $\omega$ is the clique number of $G$. Strengthening this bound, Elphick and Wocjan proposed a conjecture in 2018, which is stated as follows: $\frac{n}{n - \sqrt{s^{+}}} \leq \omega$, where $s^+ = \sum_{\lambda_{i} > 0} \lambda_{i}^2$ and $\lambda_i$ are the eigenvalues of $A(G)$. In this paper, we have settled this conjecture for some classes of graphs, such as conference graphs, strongly regular graphs with $\lambda = \mu$ (i.e., $srg(n, d, \mu, \mu)$) and $n\geq 2d$, the line graph of $K_{n}$, the Cartesian product of strongly regular graphs, and Ramanujan graph with $n\geq 11d$. </p> </div> </dd> </dl> <dl id='articles'> <h3>Cross submissions (showing 8 of 8 entries)</h3> <dt> <a name='item3'>[3]</a> <a href ="/abs/2504.04256" title="Abstract" id="2504.04256"> arXiv:2504.04256 </a> (cross-list from math.CO) [<a href="/pdf/2504.04256" title="Download PDF" id="pdf-2504.04256" aria-labelledby="pdf-2504.04256">pdf</a>, <a href="https://arxiv.org/html/2504.04256v1" title="View HTML" id="html-2504.04256" aria-labelledby="html-2504.04256" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.04256" title="Other formats" id="oth-2504.04256" aria-labelledby="oth-2504.04256">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Word-Representability of Well-Partitioned Chordal Graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Dwary,+T">Tithi Dwary</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Krishna,+K+V">K. V. Krishna</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> In this paper, we study the word-representability of well-partitioned chordal graphs using split decomposition. We show that every component of the minimal split decomposition of a well-partitioned chordal graph is a split graph. Thus we have a characterization for word-representability of well-partitioned chordal graphs. As a consequence, we prove that the recognition of word-representability of well-partitioned chordal graphs can be done in polynomial time. Moreover, we prove that the representation number of a word-representable well-partitioned chordal graph is at most three. Further, we obtain a minimal forbidden induced subgraph characterization of circle graphs restricted to well-partitioned chordal graphs. Accordingly, we determine the class of word-representable well-partitioned chordal graphs having representation number exactly three. </p> </div> </dd> <dt> <a name='item4'>[4]</a> <a href ="/abs/2504.04267" title="Abstract" id="2504.04267"> arXiv:2504.04267 </a> (cross-list from cs.DS) [<a href="/pdf/2504.04267" title="Download PDF" id="pdf-2504.04267" aria-labelledby="pdf-2504.04267">pdf</a>, <a href="https://arxiv.org/html/2504.04267v1" title="View HTML" id="html-2504.04267" aria-labelledby="html-2504.04267" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.04267" title="Other formats" id="oth-2504.04267" aria-labelledby="oth-2504.04267">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Efficient Rejection Sampling in the Entropy-Optimal Range </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Draper,+T+L">Thomas L. Draper</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Saad,+F+A">Feras A. Saad</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 37 pages, 11 figures, 4 tables, 4 algorithms </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Discrete Mathematics (cs.DM); Information Theory (cs.IT); Probability (math.PR); Computation (stat.CO) </div> <p class='mathjax'> The problem of generating a random variate $X$ from a finite discrete probability distribution $P$ using an entropy source of independent unbiased coin flips is considered. The Knuth and Yao complexity theory of nonuniform random number generation furnishes a family of "entropy-optimal" sampling algorithms that consume between $H(P)$ and $H(P)+2$ coin flips per generated output, where $H$ is the Shannon entropy function. However, the space complexity of entropy-optimal samplers scales exponentially with the number of bits required to encode $P$. This article introduces a family of efficient rejection samplers and characterizes their entropy, space, and time complexity. Within this family is a distinguished sampling algorithm that requires linearithmic space and preprocessing time, and whose expected entropy cost always falls in the entropy-optimal range $[H(P), H(P)+2)$. No previous sampler for discrete probability distributions is known to achieve these characteristics. Numerical experiments demonstrate performance improvements in runtime and entropy of the proposed algorithm compared to the celebrated alias method. </p> </div> </dd> <dt> <a name='item5'>[5]</a> <a href ="/abs/2504.04499" title="Abstract" id="2504.04499"> arXiv:2504.04499 </a> (cross-list from math.CO) [<a href="/pdf/2504.04499" title="Download PDF" id="pdf-2504.04499" aria-labelledby="pdf-2504.04499">pdf</a>, <a href="/format/2504.04499" title="Other formats" id="oth-2504.04499" aria-labelledby="oth-2504.04499">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Binary Weight Allocation for Multi-Objective Path Optimization: Efficient Earliest and Latest Path Discovery in Network Systems </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Yeh,+W">Wei-Chang Yeh</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM); Numerical Analysis (math.NA) </div> <p class='mathjax'> This paper proposes earliest and latest path algorithms based on binary weight allocation, assigning weights of 2(i-1) and 2(m-i) to the i-th arc in a network. While traditional shortest path algorithms optimize only distance, our approach leverages Binary-Addition-Tree ordering to efficiently identify lexicographically smallest and largest paths that establish connectivity. These paths partition the solution space into three regions: guaranteed disconnection, transitional connectivity, and guaranteed no simple paths. Our weight allocation enables implicit encoding of multiple objectives directly in binary representations, maintaining the O((|V|+|E|)log|V|) complexity of Dijkstra's algorithm while allowing simultaneous optimization of competing factors like reliability and cost. Experimental validation demonstrates significant computational time reduction compared to traditional multi-objective methods. Applications span telecommunications, transportation networks, and supply chain management, providing efficient tools for network planning and reliability analysis under multiple constraints. </p> </div> </dd> <dt> <a name='item6'>[6]</a> <a href ="/abs/2504.04577" title="Abstract" id="2504.04577"> arXiv:2504.04577 </a> (cross-list from math.OC) [<a href="/pdf/2504.04577" title="Download PDF" id="pdf-2504.04577" aria-labelledby="pdf-2504.04577">pdf</a>, <a href="https://arxiv.org/html/2504.04577v1" title="View HTML" id="html-2504.04577" aria-labelledby="html-2504.04577" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.04577" title="Other formats" id="oth-2504.04577" aria-labelledby="oth-2504.04577">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Minimum Cut Representability of Stable Matching Problems </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Faenza,+Y">Yuri Faenza</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Foussoul,+A">Ayoub Foussoul</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=He,+C">Chengyue He</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Optimization and Control (math.OC)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> We introduce and study Minimum Cut Representability, a framework to solve optimization and feasibility problems over stable matchings by representing them as minimum s-t cut problems on digraphs over rotations. We provide necessary and sufficient conditions on objective functions and feasibility sets for problems to be minimum cut representable. In particular, we define the concepts of first and second order differentials of a function over stable matchings and show that a problem is minimum cut representable if and only if, roughly speaking, the objective function can be expressed solely using these differentials, and the feasibility set is a sublattice of the stable matching lattice. To demonstrate the practical relevance of our framework, we study a range of real-world applications, including problems involving school choice with siblings and a two-stage stochastic stable matching problem. We show how our framework can be used to help solving these problems. </p> </div> </dd> <dt> <a name='item7'>[7]</a> <a href ="/abs/2504.04585" title="Abstract" id="2504.04585"> arXiv:2504.04585 </a> (cross-list from math.CO) [<a href="/pdf/2504.04585" title="Download PDF" id="pdf-2504.04585" aria-labelledby="pdf-2504.04585">pdf</a>, <a href="https://arxiv.org/html/2504.04585v1" title="View HTML" id="html-2504.04585" aria-labelledby="html-2504.04585" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.04585" title="Other formats" id="oth-2504.04585" aria-labelledby="oth-2504.04585">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Balanced colorings of Erd艖s-R茅nyi hypergraphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Dhawan,+A">Abhishek Dhawan</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Wang,+Y">Yuzhou Wang</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 28 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> An $r$-uniform hypergraph $H = (V, E)$ is $r$-partite if there exists a partition of the vertex set into $r$ parts such that each edge contains exactly one vertex from each part. We say an independent set in such a hypergraph is balanced if it contains an equal number of vertices from each partition. The balanced chromatic number of $H$ is the minimum value $q$ such that $H$ admits a proper $q$-coloring where each color class is a balanced independent set. In this note, we determine the asymptotic behavior of the balanced chromatic number for sparse $r$-uniform $r$-partite Erd艖s--R茅nyi hypergraphs. A key step in our proof is to show that any balanced colorable hypergraph of average degree $d$ admits a proper balanced coloring with $r(r-1)d + 1$ colors. This extends a result of Feige and Kogan on bipartite graphs to this more general setting. </p> </div> </dd> <dt> <a name='item8'>[8]</a> <a href ="/abs/2504.04897" title="Abstract" id="2504.04897"> arXiv:2504.04897 </a> (cross-list from math.CO) [<a href="/pdf/2504.04897" title="Download PDF" id="pdf-2504.04897" aria-labelledby="pdf-2504.04897">pdf</a>, <a href="https://arxiv.org/html/2504.04897v1" title="View HTML" id="html-2504.04897" aria-labelledby="html-2504.04897" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.04897" title="Other formats" id="oth-2504.04897" aria-labelledby="oth-2504.04897">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Calamoneri,+T">Tiziana Calamoneri</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Cor%C3%B2,+F">Federico Cor貌</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Paesani,+G">Giacomo Paesani</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Soon to be submitted to a conference. Any constructive comment is welcome </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS) </div> <p class='mathjax'> Eternal vertex cover is the following two-player game between a defender and an attacker on a graph. Initially, the defender positions k guards on k vertices of the graph; the game then proceeds in turns between the defender and the attacker, with the attacker selecting an edge and the defender responding to the attack by moving some of the guards along the edges, including the attacked one. The defender wins a game on a graph G with k guards if they have a strategy such that, in every round of the game, the vertices occupied by the guards form a vertex cover of G, and the attacker wins otherwise. The eternal vertex cover number of a graph G is the smallest number k of guards allowing the defender to win and Eternal Vertex Cover is the problem of computing the eternal vertex cover number of the given graph. <br>We study this problem when restricted to the well-known class of series-parallel graphs. In particular, we prove that Eternal Vertex Cover can be solved in linear time when restricted to melon graphs, a proper subclass of series-parallel graphs. Moreover, we also conjecture that this problem is NP-hard on series-parallel graphs. </p> </div> </dd> <dt> <a name='item9'>[9]</a> <a href ="/abs/2504.05039" title="Abstract" id="2504.05039"> arXiv:2504.05039 </a> (cross-list from math.CO) [<a href="/pdf/2504.05039" title="Download PDF" id="pdf-2504.05039" aria-labelledby="pdf-2504.05039">pdf</a>, <a href="https://arxiv.org/html/2504.05039v1" title="View HTML" id="html-2504.05039" aria-labelledby="html-2504.05039" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.05039" title="Other formats" id="oth-2504.05039" aria-labelledby="oth-2504.05039">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Outerplanar and bounded treewidth support for hypergraphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Raman,+R">Rajiv Raman</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Singh,+K">Karamjeet Singh</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> We study the existence and construction of sparse supports for hypergraphs derived from subgraphs of a graph $G$. For a hypergraph $(X,\mathcal{H})$, a support $Q$ is a graph on $X$ s.t. $Q[H]$, the graph induced on vertices in $H$ is connected for every $H\in\mathcal{H}$. <br>We consider \emph{primal}, \emph{dual}, and \emph{intersection} hypergraphs defined by subgraphs of a graph $G$ that are \emph{non-piercing}, (i.e., each subgraph is connected, their pairwise differences remain connected). <br>If $G$ is outerplanar, we show that the primal, dual and intersection hypergraphs admit supports that are outerplanar. For a bounded treewidth graph $G$, we show that if the subgraphs are non-piercing, then there exist supports for the primal and dual hypergraphs of treewidth $O(2^{tw(G)})$ and $O(2^{4tw(G)})$ respectively, and a support of treewidth $2^{O(2^{tw(G)})}$ for the intersection hypergraph. We also show that for the primal and dual hypergraphs, the exponential blow-up of treewidth is sometimes essential. <br>All our results are algorithmic and yield polynomial-time algorithms (when the treewidth is bounded). The existence and construction of sparse supports is a crucial step in the design and analysis of PTASs and/or sub-exponential time algorithms for several packing and covering problems. </p> </div> </dd> <dt> <a name='item10'>[10]</a> <a href ="/abs/2504.05056" title="Abstract" id="2504.05056"> arXiv:2504.05056 </a> (cross-list from eess.SY) [<a href="/pdf/2504.05056" title="Download PDF" id="pdf-2504.05056" aria-labelledby="pdf-2504.05056">pdf</a>, <a href="/format/2504.05056" title="Other formats" id="oth-2504.05056" aria-labelledby="oth-2504.05056">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Infinite precedence graphs for consistency verification in P-time event graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/eess?searchtype=author&query=Zorzenon,+D">Davide Zorzenon</a>, <a href="https://arxiv.org/search/eess?searchtype=author&query=Raisch,+J">J枚rg Raisch</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 41 pages, 11 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Systems and Control (eess.SY)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> Precedence constraints are inequalities used to model time dependencies. In 1958, Gallai proved that a finite system of precedence constraints admits solutions if and only if the corresponding precedence graph does not contain positive-weight circuits. We show that this result extends naturally to the case of infinitely many constraints. We then analyze two specific classes of infinite precedence graphs -- $\mathbb{N}$-periodic and ultimately periodic graphs -- and prove that the existence of solutions of their related constraints can be verified in strongly polynomial time. The obtained algorithms find applications in P-time event graphs, which are a subclass of P-time Petri nets able to model production systems under cyclic schedules where tasks need to be performed within given time windows. </p> </div> </dd> </dl> <dl id='articles'> <h3>Replacement submissions (showing 8 of 8 entries)</h3> <dt> <a name='item11'>[11]</a> <a href ="/abs/2303.17352" title="Abstract" id="2303.17352"> arXiv:2303.17352 </a> (replaced) [<a href="/pdf/2303.17352" title="Download PDF" id="pdf-2303.17352" aria-labelledby="pdf-2303.17352">pdf</a>, <a href="https://arxiv.org/html/2303.17352v2" title="View HTML" id="html-2303.17352" aria-labelledby="html-2303.17352" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2303.17352" title="Other formats" id="oth-2303.17352" aria-labelledby="oth-2303.17352">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the Parenthesisations of Matrix Chains: All are Useful, Few Are Essential </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=L%C3%B3pez,+F">Francisco L贸pez</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Karlsson,+L">Lars Karlsson</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Bientinesi,+P">Paolo Bientinesi</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 19 pages, 1 figure, 3 tables. Accepted for publication in Springer's Journal of Combinatorial Optimization </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Discrete Mathematics (cs.DM)</span> </div> <p class='mathjax'> The product of a matrix chain consisting of $n$ matrices can be computed in $C_{n-1}$ (Catalan's number) different ways, each identified by a distinct parenthesisation of the chain. The best algorithm to select a parenthesisation that minimises the cost runs in $O(n \log n)$ time. Approximate algorithms run in $O(n)$ time and find solutions that are guaranteed to be within a certain factor from optimal; the best factor is currently $1.155$. In this article, we first prove two results that characterise different parenthesisations, and then use those results to improve on the best known approximation algorithms. Specifically, we show that (a) each parenthesisation is optimal somewhere in the problem domain, and (b) exactly $n + 1$ parenthesisations are essential in the sense that the removal of any one of them causes an unbounded penalty for an infinite number of problem instances. By focusing on essential parenthesisations, we improve on the best known approximation algorithm and show that the approximation factor is at most $1.143$. </p> </div> </dd> <dt> <a name='item12'>[12]</a> <a href ="/abs/2402.11758" title="Abstract" id="2402.11758"> arXiv:2402.11758 </a> (replaced) [<a href="/pdf/2402.11758" title="Download PDF" id="pdf-2402.11758" aria-labelledby="pdf-2402.11758">pdf</a>, <a href="https://arxiv.org/html/2402.11758v2" title="View HTML" id="html-2402.11758" aria-labelledby="html-2402.11758" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2402.11758" title="Other formats" id="oth-2402.11758" aria-labelledby="oth-2402.11758">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Conformally rigid graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Steinerberger,+S">Stefan Steinerberger</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Thomas,+R+R">Rekha R. Thomas</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM); Optimization and Control (math.OC); Spectral Theory (math.SP) </div> <p class='mathjax'> Given a finite, simple, connected graph $G=(V,E)$ with $|V|=n$, we consider the associated graph Laplacian matrix $L = D - A$ with eigenvalues $0 = \lambda_1 < \lambda_2 \leq \dots \leq \lambda_n$. One can also consider the same graph equipped with positive edge weights $w:E \rightarrow \mathbb{R}_{> 0}$ normalized to $\sum_{e \in E} w_e = |E|$ and the associated weighted Laplacian matrix $L_w$. We say that $G$ is conformally rigid if constant edge-weights maximize the second eigenvalue $\lambda_2(w)$ of $L_w$ over all $w$, and minimize $\lambda_n(w')$ of $L_{w'}$ over all $w'$, i.e., for all $w,w'$, $$ \lambda_2(w) \leq \lambda_2(1) \leq \lambda_n(1) \leq \lambda_n(w').$$ Conformal rigidity requires an extraordinary amount of symmetry in $G$. Every edge-transitive graph is conformally rigid. We prove that every distance-regular graph, and hence every strongly-regular graph, is conformally rigid. Certain special graph embeddings can be used to characterize conformal rigidity. Cayley graphs can be conformally rigid but need not be, we prove a sufficient criterion. We also find a small set of conformally rigid graphs that do not belong into any of the above categories; these include the Hoffman graph, the crossing number graph 6B and others. Conformal rigidity can be certified via semidefinite programming, we provide explicit examples. </p> </div> </dd> <dt> <a name='item13'>[13]</a> <a href ="/abs/2403.08977" title="Abstract" id="2403.08977"> arXiv:2403.08977 </a> (replaced) [<a href="/pdf/2403.08977" title="Download PDF" id="pdf-2403.08977" aria-labelledby="pdf-2403.08977">pdf</a>, <a href="https://arxiv.org/html/2403.08977v2" title="View HTML" id="html-2403.08977" aria-labelledby="html-2403.08977" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2403.08977" title="Other formats" id="oth-2403.08977" aria-labelledby="oth-2403.08977">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On maximum-sum matchings of bichromatic points </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chac%C3%B3n-Rivera,+O">Oscar Chac贸n-Rivera</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=P%C3%A9rez-Lantero,+P">Pablo P茅rez-Lantero</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Geometry (cs.CG)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> Huemer et al. (Discrete Math, 2019) proved that for any two finite point sets $R$ and $B$ in the plane with $|R| = |B|$, the perfect matching that matches points of $R$ with points of $B$, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a nonempty common intersection. A pair of matched points induces the disk that has the segment connecting the points as diameter. In this note, we characterize these maximum-sum matchings for some family of continuous (semi-)metrics, focusing on both the Euclidean distance and squared Euclidean distance. Using this characterization, we give a different but simpler proof for the common intersection property proved by Huemer et al.. </p> </div> </dd> <dt> <a name='item14'>[14]</a> <a href ="/abs/2409.03951" title="Abstract" id="2409.03951"> arXiv:2409.03951 </a> (replaced) [<a href="/pdf/2409.03951" title="Download PDF" id="pdf-2409.03951" aria-labelledby="pdf-2409.03951">pdf</a>, <a href="https://arxiv.org/html/2409.03951v2" title="View HTML" id="html-2409.03951" aria-labelledby="html-2409.03951" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2409.03951" title="Other formats" id="oth-2409.03951" aria-labelledby="oth-2409.03951">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Random local access for sampling k-SAT solutions </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Dong,+D">Dingding Dong</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Mani,+N">Nitya Mani</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 30 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> We present a sublinear time algorithm that gives random local access to the uniform distribution over satisfying assignments to an arbitrary k-CNF formula $\Phi$, at exponential clause density. Our algorithm provides memory-less query access to variable assignments, such that the output variable assignments consistently emulate a single global satisfying assignment whose law is close to the uniform distribution over satisfying assignments to $\Phi$. <br>Such models were formally defined (for the more general task of locally sampling from exponentially sized sample spaces) in 2017 by Biswas, Rubinfeld, and Yodpinyanee, who studied the analogous problem for the uniform distribution over proper q-colorings. This model extends a long line of work over multiple decades that studies sublinear time algorithms for problems in theoretical computer science. Random local access and related models have been studied for a wide variety of natural Gibbs distributions and random graphical processes. Here, we establish feasiblity of random local access models for one of the most canonical such sample spaces, the set of satisfying assignments to a k-CNF formula. </p> </div> </dd> <dt> <a name='item15'>[15]</a> <a href ="/abs/2409.06425" title="Abstract" id="2409.06425"> arXiv:2409.06425 </a> (replaced) [<a href="/pdf/2409.06425" title="Download PDF" id="pdf-2409.06425" aria-labelledby="pdf-2409.06425">pdf</a>, <a href="https://arxiv.org/html/2409.06425v2" title="View HTML" id="html-2409.06425" aria-labelledby="html-2409.06425" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2409.06425" title="Other formats" id="oth-2409.06425" aria-labelledby="oth-2409.06425">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> New bounds for the optimal density of covering single-insertion codes via the Tur谩n density </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Pikhurko,+O">Oleg Pikhurko</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Verbitsky,+O">Oleg Verbitsky</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Zhukovskii,+M">Maksim Zhukovskii</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> This article has been accepted for publication in IEEE Transactions on Information Theory. This is the author's version converted to the IEEEtran style </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> We prove that the density of any covering single-insertion code $C\subseteq X^r$ over the $n$-symbol alphabet $X$ cannot be smaller than $1/r+\delta_r$ for some positive real $\delta_r$ not depending on $n$. This improves the volume lower bound of $1/(r+1)$. On the other hand, we observe that, for all sufficiently large $r$, if $n$ tends to infinity then the asymptotic upper bound of $7/(r+1)$ due to Lenz et al (2021) can be improved to $4.911/(r+1)$. <br>Both the lower and the upper bounds are achieved by relating the code density to the Tur谩n density from extremal combinatorics. For the last task, we use the analytic framework of measurable subsets of the real cube $[0,1]^r$. </p> </div> </dd> <dt> <a name='item16'>[16]</a> <a href ="/abs/2410.23225" title="Abstract" id="2410.23225"> arXiv:2410.23225 </a> (replaced) [<a href="/pdf/2410.23225" title="Download PDF" id="pdf-2410.23225" aria-labelledby="pdf-2410.23225">pdf</a>, <a href="https://arxiv.org/html/2410.23225v2" title="View HTML" id="html-2410.23225" aria-labelledby="html-2410.23225" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2410.23225" title="Other formats" id="oth-2410.23225" aria-labelledby="oth-2410.23225">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Deterministic counting from coupling independence </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chen,+X">Xiaoyu Chen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Feng,+W">Weiming Feng</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Guo,+H">Heng Guo</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zhang,+X">Xinyuan Zhang</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zou,+Z">Zongrui Zou</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting algorithm to achieve this. As applications, we give the first FPTASes for $q$-colourings on graphs of bounded maximum degree $\Delta\ge 3$, when $q\ge (11/6-\varepsilon_0)\Delta$ for some small $\varepsilon_0\approx 10^{-5}$, or when $\Delta\ge 125$ and $q\ge 1.809\Delta$, and on graphs with sufficiently large (but constant) girth, when $q\geq\Delta+3$. These bounds match the current best randomised approximate counting algorithms by Chen, Delcourt, Moitra, Perarnau, and Postle (2019), Carlson and Vigoda (2024), and Chen, Liu, Mani, and Moitra (2023), respectively. </p> </div> </dd> <dt> <a name='item17'>[17]</a> <a href ="/abs/2412.14784" title="Abstract" id="2412.14784"> arXiv:2412.14784 </a> (replaced) [<a href="/pdf/2412.14784" title="Download PDF" id="pdf-2412.14784" aria-labelledby="pdf-2412.14784">pdf</a>, <a href="https://arxiv.org/html/2412.14784v3" title="View HTML" id="html-2412.14784" aria-labelledby="html-2412.14784" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2412.14784" title="Other formats" id="oth-2412.14784" aria-labelledby="oth-2412.14784">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Large Induced Subgraphs of Bounded Degree in Outerplanar and Planar Graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=D'Elia,+M">Marco D'Elia</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Frati,+F">Fabrizio Frati</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM) </div> <p class='mathjax'> In this paper, we study the following question. Let $\mathcal G$ be a family of planar graphs and let $k\geq 3$ be an integer. What is the largest value $f_k(n)$ such that every $n$-vertex graph in $\mathcal G$ has an induced subgraph with degree at most $k$ and with $f_k(n)$ vertices? Similar questions, in which one seeks a large induced forest, or a large induced linear forest, or a large induced $d$-degenerate graph, rather than a large induced graph of bounded degree, have been studied for decades and have given rise to some of the most fascinating and elusive conjectures in Graph Theory. We tackle our problem when $\mathcal G$ is the class of the outerplanar graphs or the class of the planar graphs. In both cases, we provide upper and lower bounds on the value of $f_k(n)$. For example, we prove that every $n$-vertex planar graph has an induced subgraph with degree at most $3$ and with $\frac{5n}{13}>0.384n$ vertices, and that there exist $n$-vertex planar graphs whose largest induced subgraph with degree at most $3$ has $\frac{4n}{7}+O(1)<0.572n+O(1)$ vertices. </p> </div> </dd> <dt> <a name='item18'>[18]</a> <a href ="/abs/2501.03788" title="Abstract" id="2501.03788"> arXiv:2501.03788 </a> (replaced) [<a href="/pdf/2501.03788" title="Download PDF" id="pdf-2501.03788" aria-labelledby="pdf-2501.03788">pdf</a>, <a href="https://arxiv.org/html/2501.03788v2" title="View HTML" id="html-2501.03788" aria-labelledby="html-2501.03788" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2501.03788" title="Other formats" id="oth-2501.03788" aria-labelledby="oth-2501.03788">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Young domination on Hamming rectangles </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Gravner,+J">Janko Gravner</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Krnc,+M">Matja啪 Krnc</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Milani%C4%8D,+M">Martin Milani膷</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Raymond,+J">Jean-Florent Raymond</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS) </div> <p class='mathjax'> In the neighborhood growth dynamics on a Hamming rectangle $[0,m-1]\times[0,n-1]\subseteq \mathbb{Z}_+^2$, the decision to add a point is made by counting the currently occupied points on the horizontal and the vertical line through it, and checking whether the pair of counts lies outside a fixed Young diagram. After the initially occupied set is chosen, the synchronous rule is iterated. The Young domination number with a fixed latency $L$ is the smallest cardinality of an initial set that covers the rectangle by $L$ steps, for $L=0,1,\ldots$ We compute this number for some special cases, including $k$-domination for any $k$ when $m=n$, thereby proving a conjecture from 2009 due to Burchett, Lachniet, and Lane, and devise approximation algorithms in the general case. These results have implications in extremal graph theory, via an equivalence between the case $L = 1$ and bipartite Tur谩n numbers for families of double stars. Our approach is based on a variety of techniques including duality between Young diagrams, algebraic formulations, explicit constructions, and dynamic programming. </p> </div> </dd> </dl> <div class='paging'>Total of 18 entries </div> <div class='morefewer'>Showing up to 2000 entries per page: <a href=/list/cs.DM/new?skip=0&show=1000 rel="nofollow"> fewer</a> | <span style="color: #454545">more</span> | <span style="color: #454545">all</span> </div> </div> </div> </div> </main> <footer style="clear: both;"> <div class="columns is-desktop" role="navigation" aria-label="Secondary" style="margin: -0.75em -0.75em 0.75em -0.75em"> <!-- Macro-Column 1 --> <div class="column" style="padding: 0;"> <div class="columns"> <div class="column"> <ul style="list-style: none; line-height: 2;"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul style="list-style: none; line-height: 2;"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div> <!-- End Macro-Column 1 --> <!-- Macro-Column 2 --> <div class="column" style="padding: 0;"> <div class="columns"> <div class="column"> <ul style="list-style: none; line-height: 2;"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul style="list-style: none; line-height: 2;"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div> <!-- end MetaColumn 2 --> <!-- End Macro-Column 2 --> </div> </footer> </div> <script src="/static/base/1.0.1/js/member_acknowledgement.js"></script> </body> </html>