Combinatorics

<!DOCTYPE html> <html lang="en"> <head> <title>Combinatorics </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> <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"> <div class="flex-wrap-footer"> <header> <a href="#content" class="is-sr-only">Skip to main content</a>  <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><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/math.CO/recent">math.CO</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> <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> </header> <main> <div id="content"> <div id='content-inner'> <div id='dlpage'> <h1>Combinatorics</h1> <ul> <li><a href="#item0">New submissions</a></li> <li><a href="#item18">Cross-lists</a></li> <li><a href="#item21">Replacements</a></li> </ul> <p>See <a id="recent-math.CO" aria-labelledby="recent-math.CO" href="/list/math.CO/recent">recent</a> articles</p> <h3>Showing new listings for Thursday, 3 April 2025</h3> <div class='paging'>Total of 34 entries </div> <div class='morefewer'>Showing up to 2000 entries per page: <a href=/list/math.CO/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 17 of 17 entries)</h3> <dt> <a name='item1'>[1]</a> <a href ="/abs/2504.01116" title="Abstract" id="2504.01116"> arXiv:2504.01116 </a> [<a href="/pdf/2504.01116" title="Download PDF" id="pdf-2504.01116" aria-labelledby="pdf-2504.01116">pdf</a>, <a href="https://arxiv.org/html/2504.01116v1" title="View HTML" id="html-2504.01116" aria-labelledby="html-2504.01116" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01116" title="Other formats" id="oth-2504.01116" aria-labelledby="oth-2504.01116">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Higher dimensional floorplans and Baxter d-permutations </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Bonichon,+N">Nicolas Bonichon</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Muller,+T">Thomas Muller</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Tanasa,+A">Adrian Tanasa</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 34 pages, 24 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> A $2-$dimensional mosaic floorplan is a partition of a rectangle by other rectangles with no empty rooms. These partitions (considered up to some deformations) are known to be in bijection with Baxter permutations. A $d$-floorplan is the generalisation of mosaic floorplans in higher dimensions, and a $d$-permutation is a $(d-1)$-tuple of permutations. Recently, in N. Bonichon and P.-J. Morel, {\it J. Integer Sequences} 25 (2022), Baxter $d$-permutations generalising the usual Baxter permutations were introduced. <br>In this paper, we consider mosaic floorplans in arbitrary dimensions, and we construct a generating tree for $d$-floorplans, which generalises the known generating tree structure for $2$-floorplans. The corresponding labels and rewriting rules appear to be significantly more involved in higher dimensions. <br>Moreover we give a bijection between the $2^{d-1}$-floorplans and $d$-permutations characterized by forbidden vincular patterns. Surprisingly, this set of $d$-permutations is strictly contained within the set of Baxter $d$-permutations. </p> </div> </dd> <dt> <a name='item2'>[2]</a> <a href ="/abs/2504.01158" title="Abstract" id="2504.01158"> arXiv:2504.01158 </a> [<a href="/pdf/2504.01158" title="Download PDF" id="pdf-2504.01158" aria-labelledby="pdf-2504.01158">pdf</a>, <a href="https://arxiv.org/html/2504.01158v1" title="View HTML" id="html-2504.01158" aria-labelledby="html-2504.01158" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01158" title="Other formats" id="oth-2504.01158" aria-labelledby="oth-2504.01158">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the Number of Disconnected Character Degree Graphs Satisfying P谩lfy's Inequality </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Lewis,+M+L">Mark L. Lewis</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Summers,+A">Andrew Summers</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 6 pages, 2 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Group Theory (math.GR) </div> <p class='mathjax'> Let $G$ be a finite solvable group with disconnected character degree graph $\Delta(G)$. Under these conditions, it follows from a result of P谩lfy that $\Delta(G)$ consists of two connected components. Another result of P谩lfy's gives an inequality relating the sizes of these two connected components. In this paper, we calculate the number of possible component size pairs that satisfy P谩lfy's inequality. Additionally, for a fixed positive integer $n$, the number of distinct graph orders for which exactly $n$ component size pairs satisfy P谩lfy's inequality is shown. </p> </div> </dd> <dt> <a name='item3'>[3]</a> <a href ="/abs/2504.01180" title="Abstract" id="2504.01180"> arXiv:2504.01180 </a> [<a href="/pdf/2504.01180" title="Download PDF" id="pdf-2504.01180" aria-labelledby="pdf-2504.01180">pdf</a>, <a href="https://arxiv.org/html/2504.01180v1" title="View HTML" id="html-2504.01180" aria-labelledby="html-2504.01180" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01180" title="Other formats" id="oth-2504.01180" aria-labelledby="oth-2504.01180">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Homotopy equivalence of Grassmannians and MacPhersonians in rank 3 </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Dobbins,+M+G">Michael Gene Dobbins</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> We confirm a long standing conjecture in the case of rank 3 that MacPhersonians are homotopy equivalent to Grassmannians. </p> </div> </dd> <dt> <a name='item4'>[4]</a> <a href ="/abs/2504.01181" title="Abstract" id="2504.01181"> arXiv:2504.01181 </a> [<a href="/pdf/2504.01181" title="Download PDF" id="pdf-2504.01181" aria-labelledby="pdf-2504.01181">pdf</a>, <a href="https://arxiv.org/html/2504.01181v1" title="View HTML" id="html-2504.01181" aria-labelledby="html-2504.01181" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01181" title="Other formats" id="oth-2504.01181" aria-labelledby="oth-2504.01181">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Stiffness matrices of graph blow-ups and the $d$-dimensional algebraic connectivity of complete bipartite graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Jung,+Y">Yunseong Jung</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Lew,+A">Alan Lew</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> The $d$-dimensional algebraic connectivity $a_d(G)$ of a graph $G=(V,E)$ is a quantitative measure of its $d$-dimensional rigidity, defined in terms of the eigenvalues of stiffness matrices associated with different embeddings of the graph into $\mathbb{R}^d$. For a function $a:V\to \mathbb{N}$, we denote by $G^{(a)}$ the $a$-blow-up of $G$, that is, the graph obtained from $G$ by replacing every vertex $v\in V$ with an independent set of size $a(v)$. We determine a relation between the stiffness matrix eigenvalues of $G^{(a)}$ and the eigenvalues of certain weighted stiffness matrices associated with the original graph $G$. This resolves, as a special case, a conjecture of Lew, Nevo, Peled and Raz on the stiffness eigenvalues of balanced blow-ups of the complete graph. <br>As an application, we obtain a lower bound on the $d$-dimensional algebraic connectivity of complete bipartite graphs. More precisely, we prove the following: Let $K_{n,m}$ be the complete bipartite graph with sides of size $n$ and $m$ respectively. Then, for every $d\ge 1$ there exists $c_d>0$ such that, for all $n,m\ge d+1$ with $n+m\ge \binom{d+2}{2}$, $a_d(K_{n,m})\ge c_d\cdot \min\{n,m\}$. This bound is tight up to the multiplicative constant. In the special case $d=2$, $n=m=3$, we obtain the improved bound $a_2(K_{3,3})\ge 2(1-\lambda)$, where $\lambda\approx 0.6903845$ is the unique positive real root of the polynomial $176 x^4-200 x^3+47 x^2+18 x-9$, which we conjecture to be tight. </p> </div> </dd> <dt> <a name='item5'>[5]</a> <a href ="/abs/2504.01217" title="Abstract" id="2504.01217"> arXiv:2504.01217 </a> [<a href="/pdf/2504.01217" title="Download PDF" id="pdf-2504.01217" aria-labelledby="pdf-2504.01217">pdf</a>, <a href="https://arxiv.org/html/2504.01217v1" title="View HTML" id="html-2504.01217" aria-labelledby="html-2504.01217" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01217" title="Other formats" id="oth-2504.01217" aria-labelledby="oth-2504.01217">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> BCFW tilings and cluster adjacency for the amplituhedron </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Even-Zohar,+C">Chaim Even-Zohar</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Lakrec,+T">Tsviqa Lakrec</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Parisi,+M">Matteo Parisi</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Sherman-Bennett,+M">Melissa Sherman-Bennett</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Tessler,+R">Ran Tessler</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Williams,+L">Lauren Williams</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> This article was published on PNAS (<a href="http://doi.org/10.1073/pnas.2408572122" rel="external noopener nofollow" class="link-external link-http">this http URL</a>) as a research announcement of a full-length paper by the same authors (<a href="http://doi.org/10.48550/arXiv.2310.17727" rel="external noopener nofollow" class="link-external link-http">this http URL</a>) </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Proceedings of the National Academy of Sciences, Vol. 122, No. 12, March 25, 2025 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> In 2005, Britto, Cachazo, Feng and Witten gave a recurrence (now known as the BCFW recurrence) for computing scattering amplitudes in N=4 super Yang Mills theory. Arkani-Hamed and Trnka subsequently introduced the amplituhedron to give a geometric interpretation of the BCFW recurrence. Arkani-Hamed and Trnka conjectured that each way of iterating the BCFW recurrence gives a "triangulation" or "tiling" of the m=4 amplituhedron. In this article we prove the BCFW tiling conjecture of Arkani-Hamed and Trnka. We also prove the cluster adjacency conjecture for BCFW tiles of the amplituhedron, which says that facets of tiles are cut out by collections of compatible cluster variables for the Grassmannian Gr(4,n). Moreover we show that each BCFW tile is the subset of the Grassmannian where certain cluster variables have particular signs. </p> </div> </dd> <dt> <a name='item6'>[6]</a> <a href ="/abs/2504.01233" title="Abstract" id="2504.01233"> arXiv:2504.01233 </a> [<a href="/pdf/2504.01233" title="Download PDF" id="pdf-2504.01233" aria-labelledby="pdf-2504.01233">pdf</a>, <a href="https://arxiv.org/html/2504.01233v1" title="View HTML" id="html-2504.01233" aria-labelledby="html-2504.01233" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01233" title="Other formats" id="oth-2504.01233" aria-labelledby="oth-2504.01233">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Borsuk Problem for Subsets of the Vertices of the 10-Dimensional Boolean Cube </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Batmanov,+I">Igor Batmanov</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Voronov,+V">Vsevolod Voronov</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> In the papers Ziegler(2001) and Goldstein(2012) it was previously shown that any subset of the Boolean cube $ S \subset \{0,1\}^n $ for $ n \leq 9 $ can be partitioned into $n+1$ parts of smaller diameter, i.e., the Borsuk conjecture holds for such subsets. In this paper, it is shown that this is also true for $ n=10 $; however, the complexity of the computational verification increases significantly. In order to perform the computations in a reasonable time, several heuristics were developed to reduce the search tree. The SAT solver $\textbf{kissat}$ was used to cut off the search branches. </p> </div> </dd> <dt> <a name='item7'>[7]</a> <a href ="/abs/2504.01295" title="Abstract" id="2504.01295"> arXiv:2504.01295 </a> [<a href="/pdf/2504.01295" title="Download PDF" id="pdf-2504.01295" aria-labelledby="pdf-2504.01295">pdf</a>, <a href="https://arxiv.org/html/2504.01295v1" title="View HTML" id="html-2504.01295" aria-labelledby="html-2504.01295" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01295" title="Other formats" id="oth-2504.01295" aria-labelledby="oth-2504.01295">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A Spectral Lower Bound on the Chromatic Number using $p$-Energy </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Tang,+Q">Quanyu Tang</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Elphick,+C">Clive Elphick</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 11 pages, 1 figure. Feedback and suggestions are welcome </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> Let $ A(G) $ be the adjacency matrix of a simple graph $ G $, and let $\chi(G)$ denote its chromatic number. For $ p > 0 $, we define the positive and negative $ p $-energies of $ G $ as $$ \mathcal{E}_p^+(G) = \sum_{\lambda_i > 0} \lambda_i^p(A(G)), \quad \mathcal{E}_p^-(G) = \sum_{\lambda_i < 0} |\lambda_i(A(G))|^p, $$ where $ \lambda_1(A(G)) \geq \cdots \geq \lambda_n(A(G)) $ are the eigenvalues of $ A(G) $. We first prove that $$ \chi(G) \geq 1 + \max \left\{ \frac{\mathcal{E}_p^+(G)}{\mathcal{E}_p^-(G)}, \frac{\mathcal{E}_p^-(G)}{\mathcal{E}_p^+(G)} \right\} $$ holds for all $ 0 < p < 1 $. This result has already been established for $ p = 0 $ and $ p = 2 $, and it holds trivially for $ p = 1 $. Furthermore, we demonstrate that for certain graphs, non-integer values of $p$ yield sharper lower bounds on $\chi(G)$ than existing spectral bounds. Finally, we conjecture that the same inequality continues to hold for all $ 1 < p < 2 $. </p> </div> </dd> <dt> <a name='item8'>[8]</a> <a href ="/abs/2504.01364" title="Abstract" id="2504.01364"> arXiv:2504.01364 </a> [<a href="/pdf/2504.01364" title="Download PDF" id="pdf-2504.01364" aria-labelledby="pdf-2504.01364">pdf</a>, <a href="https://arxiv.org/html/2504.01364v1" title="View HTML" id="html-2504.01364" aria-labelledby="html-2504.01364" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01364" title="Other formats" id="oth-2504.01364" aria-labelledby="oth-2504.01364">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Maximizing the number of stars in graphs with forbidden properties </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Berikkyzy,+Z">Zhanar Berikkyzy</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Hogenson,+K">Kirsten Hogenson</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Kirsch,+R">Rachel Kirsch</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=McDonald,+J">Jessica McDonald</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 19 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> Erd艖s proved an upper bound on the number of edges in an $n$-vertex non-Hamiltonian graph with given minimum degree and showed sharpness via two members of a particular graph family. F眉redi, Kostochka and Luo showed that these two graphs play the same role when ``number of edges'' is replaced by ``number of t-stars,'' and that two members of a more general graph family maximize the number of edges among non-$k$-edge-Hamiltonian graphs. In this paper we generalize their former result from Hamiltonicity to related properties (traceability, Hamiltonian-connectedness, $k$-edge Hamiltonicity, $k$-Hamiltonicity) and their latter result from edges to $t$-stars. We identify a family of extremal graphs for each property that is forbidden. This problem without the minimum degree condition was also open; here we conjecture a complete description of the extremal family for each property, and prove the characterization in some cases. Finally, using a different family of extremal graphs, we find the maximum number of $t$-stars in non-$k$-connected graphs. </p> </div> </dd> <dt> <a name='item9'>[9]</a> <a href ="/abs/2504.01484" title="Abstract" id="2504.01484"> arXiv:2504.01484 </a> [<a href="/pdf/2504.01484" title="Download PDF" id="pdf-2504.01484" aria-labelledby="pdf-2504.01484">pdf</a>, <a href="/format/2504.01484" title="Other formats" id="oth-2504.01484" aria-labelledby="oth-2504.01484">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Characteristic polynomial of generalized Ewens random permutations </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Fran%C3%A7ois,+Q">Quentin Fran莽ois</a> (CEREMADE, DMA)</div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Probability (math.PR); Spectral Theory (math.SP) </div> <p class='mathjax'> We show the convergence of the characteristic polynomial for random permutation matrices sampled from the generalized Ewens distribution. Under this distribution, the measure of a given permutation depends only on its cycle structure, according to certain weights assigned to each cycle length. The proof is based on uniform control of the characteristic polynomial using results from the singularity analysis of generating functions, together with the convergence of traces to explicit random variables expressed via a Poisson family. The limit function is the exponential of a Poisson series which has already appeared in the case of uniform permutation matrices. It is the Poisson analog of the Gaussian Holomorphic Chaos, related to the limit of characteristic polynomials for other matrix models such as Circular Ensembles, i.i.d. matrices, and Gaussian elliptic matrices. </p> </div> </dd> <dt> <a name='item10'>[10]</a> <a href ="/abs/2504.01501" title="Abstract" id="2504.01501"> arXiv:2504.01501 </a> [<a href="/pdf/2504.01501" title="Download PDF" id="pdf-2504.01501" aria-labelledby="pdf-2504.01501">pdf</a>, <a href="https://arxiv.org/html/2504.01501v1" title="View HTML" id="html-2504.01501" aria-labelledby="html-2504.01501" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01501" title="Other formats" id="oth-2504.01501" aria-labelledby="oth-2504.01501">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Vertex-Based Localization of Erd艖s-Gallai Theorems for Paths and Cycles </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Adak,+R">Rajat Adak</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Chandran,+L+S">L. Sunil Chandran</a> (Indian Institute of Science, Bangalore)</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'> For a simple graph $G$, let $n$ and $m$ denote the number of vertices and edges in $G$, respectively. The Erd艖s-Gallai theorem for paths states that in a simple $P_k$-free graph, $m \leq \frac{n(k-1)}{2}$, where $P_k$ denotes a path with length $k$ (that is, with $k$ edges). In this paper, we generalize this result as follows: For each $v \in V(G)$, let $p(v)$ be the length of the longest path that contains $v$. We show that \[m \leq \sum_{v \in V(G)} \frac{p(v)}{2}\] The Erd艖s-Gallai theorem for cycles states that in a simple graph $G$ with circumference (that is, the length of the longest cycle) at most $k$, we have $m \leq \frac{k(n-1)}{2}$. We strengthen this result as follows: For each $v \in V(G)$, let $c(v)$ be the length of the longest cycle that contains $v$, or $2$ if $v$ is not part of any cycle. We prove that \[m \leq \left( \sum_{v \in V(G)} \frac{c(v)}{2} \right) - \frac{c(u)}{2}\] where $c(u)$ denotes the circumference of $G$. \newline Furthermore, we characterize the class of extremal graphs that attain equality in these bounds. </p> </div> </dd> <dt> <a name='item11'>[11]</a> <a href ="/abs/2504.01548" title="Abstract" id="2504.01548"> arXiv:2504.01548 </a> [<a href="/pdf/2504.01548" title="Download PDF" id="pdf-2504.01548" aria-labelledby="pdf-2504.01548">pdf</a>, <a href="https://arxiv.org/html/2504.01548v1" title="View HTML" id="html-2504.01548" aria-labelledby="html-2504.01548" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01548" title="Other formats" id="oth-2504.01548" aria-labelledby="oth-2504.01548">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Defective coloring of blowups </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Norin,+S">Sergey Norin</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Steiner,+R">Raphael Steiner</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> Given a graph $G$ and an integer $d\ge 0$, its $d$-defective chromatic number $\chi^d(G)$ is the smallest size of a partition of the vertices into parts inducing subgraphs with maximum degree at most $d$. Guo, Kang and Zwaneveld recently studied the relationship between the $d$-defective chromatic number of the $(d+1)$-fold (clique) blowup $G\boxtimes K_{d+1}$ of a graph $G$ and its ordinary chromatic number, and conjectured that $\chi(G)=\chi^d(G\boxtimes K_{d+1})$ for every graph $G$ and $d\ge 0$. In this note we disprove this conjecture by constructing graphs $G$ of arbitrarily large chromatic number such that $\chi(G)\ge \frac{30}{29}\chi^d(G\boxtimes K_{d+1})$ for infinitely many $d$. On the positive side, we show that the conjecture holds with a constant factor correction, namely $\chi^d(G\boxtimes K_{d+1})\le \chi(G)\le 2\chi^d(G\boxtimes K_{d+1})$ for every graph $G$ and $d\ge 0$. </p> </div> </dd> <dt> <a name='item12'>[12]</a> <a href ="/abs/2504.01642" title="Abstract" id="2504.01642"> arXiv:2504.01642 </a> [<a href="/pdf/2504.01642" title="Download PDF" id="pdf-2504.01642" aria-labelledby="pdf-2504.01642">pdf</a>, <a href="https://arxiv.org/html/2504.01642v1" title="View HTML" id="html-2504.01642" aria-labelledby="html-2504.01642" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01642" title="Other formats" id="oth-2504.01642" aria-labelledby="oth-2504.01642">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Spanning clique subdivisions in pseudorandom graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Lee,+H">Hyunwoo Lee</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Pavez-Sign%C3%A9,+M">Mat铆as Pavez-Sign茅</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Petrov,+T">Teo Petrov</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 16 pages, 1 figure </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> In this paper, we study the appearance of a spanning subdivision of a clique in graphs satisfying certain pseudorandom conditions. Specifically, we show the following three results. Firstly, that there are constants $C>0$ and $c\in (0,1]$ such that, whenever $d/\lambda\ge C$, every $(n,d,\lambda)$-graph contains a spanning subdivision of $K_t$ for all $2\le t \le \min\{cd,c\sqrt{\frac{n}{\log n}}\}$. Secondly, that there are constants $C>0$ and $c\in (0,1]$ such that, whenever $d/\lambda\ge C\log^3n$, every $(n,d,\lambda)$-graph contains a spanning nearly-balanced subdivision of $K_t$ for all $2\le t \le \min\{cd,c\sqrt{\frac{n}{\log^3n}}\}$. Finally, we show that for every $\mu>0$, there are constants $c,\varepsilon\in (0,1]$ and $n_0\in \mathbb N$ such that, whenever $n\ge n_0$, every $n$-vertex graph with minimum degree at least $\mu n$ and no bipartite holes of size $\varepsilon n$ contains a spanning nearly-balanced subdivision of $K_t$ for all $2\le t \le c\sqrt{n}$. </p> </div> </dd> <dt> <a name='item13'>[13]</a> <a href ="/abs/2504.01693" title="Abstract" id="2504.01693"> arXiv:2504.01693 </a> [<a href="/pdf/2504.01693" title="Download PDF" id="pdf-2504.01693" aria-labelledby="pdf-2504.01693">pdf</a>, <a href="https://arxiv.org/html/2504.01693v1" title="View HTML" id="html-2504.01693" aria-labelledby="html-2504.01693" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01693" title="Other formats" id="oth-2504.01693" aria-labelledby="oth-2504.01693">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> $SL_k$-Tilings and Paths in $\mathbb{Z}^k$ </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Peterson,+Z">Zachery Peterson</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Serhiyenko,+K">Khrystyna Serhiyenko</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> comments welcome </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Rings and Algebras (math.RA); Representation Theory (math.RT) </div> <p class='mathjax'> An $SL_k$-tiling is a bi-infinite array of integers having all adjacent $k\times k$ minors equal to one and all adjacent $(k+1)\times (k+1)$ minors equal to zero. Introduced and studied by Bergeron and Reutenauer, $SL_k$-tilings generalize the notion of Conway-Coxeter frieze patterns in the case $k=2$. In a recent paper, Short showed a bijection between bi-infinite paths of reduced rationals in the Farey graph and $SL_2$-tilings. We extend this result to higher $k$ by constructing a bijection between $SL_k$-tilings and certain pairs of bi-infinite strips of vectors in $\mathbb{Z}^k$ called paths. The key ingredient in the proof is the connection to Pl眉cker friezes and Grassmannian cluster algebras. As an application, we obtain results about periodicity, duality, and positivity for tilings. </p> </div> </dd> <dt> <a name='item14'>[14]</a> <a href ="/abs/2504.01713" title="Abstract" id="2504.01713"> arXiv:2504.01713 </a> [<a href="/pdf/2504.01713" title="Download PDF" id="pdf-2504.01713" aria-labelledby="pdf-2504.01713">pdf</a>, <a href="https://arxiv.org/html/2504.01713v1" title="View HTML" id="html-2504.01713" aria-labelledby="html-2504.01713" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01713" title="Other formats" id="oth-2504.01713" aria-labelledby="oth-2504.01713">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A two-player voting game in Euclidean space </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Stylianou,+S">Stelios Stylianou</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 14 pages, 3 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Optimization and Control (math.OC) </div> <p class='mathjax'> Given a finite set $S$ of points in $\mathbb{R}^d$, which we regard as the locations of voters on a $d$-dimensional political `spectrum', two candidates (Alice and Bob) select one point in $\mathbb{R}^d$ each, in an attempt to get as many votes as possible. Alice goes first and Bob goes second, and then each voter simply votes for the candidate closer to them in terms of Euclidean distance. If a voter's distance from the two candidates is the same, they vote for nobody. We give a geometric characterization of the sets $S$ for which each candidate wins, assuming that Alice wins if they get an equal number of votes. We also show that, if not all the voters lie on a single line, then, whenever Alice has a winning strategy, there is a unique winning point for her. We also provide an algorithm which decides whether Alice has a winning point, and determines the location of that point, both in finite (in fact polynomial) time. </p> </div> </dd> <dt> <a name='item15'>[15]</a> <a href ="/abs/2504.01808" title="Abstract" id="2504.01808"> arXiv:2504.01808 </a> [<a href="/pdf/2504.01808" title="Download PDF" id="pdf-2504.01808" aria-labelledby="pdf-2504.01808">pdf</a>, <a href="https://arxiv.org/html/2504.01808v1" title="View HTML" id="html-2504.01808" aria-labelledby="html-2504.01808" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01808" title="Other formats" id="oth-2504.01808" aria-labelledby="oth-2504.01808">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Coloring of graphs without long odd holes </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Chen,+R">Ran Chen</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Xu,+B">Baogang Xu</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> A {\em hole} is an induced cycle of length at least 4, a $k$-hole is a hole of length $k$, and an {\em odd hole} is a hole of odd length. Let $\ell\ge 2$ be an integer. Let ${\cal A}_{\ell}$ be the family of graphs of girth at least $2\ell$ and having no odd holes of length at least $2\ell+3$, let ${\cal B}_{\ell}$ be the triangle-free graphs which have no 5-holes and no odd holes of length at least $2\ell+3$, and let ${\cal G}_{\ell}$ be the family of graphs of girth $2\ell+1$ and have no odd hole of length at least $2\ell+5$. Chudnovsky {\em et al.} \cite{CSS2016} proved that every graph in ${\cal A}_{2}$ is 58000-colorable, and every graph in ${\cal B}_{\ell}$ is $(\ell+1)4^{\ell-1}$-colorable. Lan and liu \cite{LL2023} showed that for $\ell\geq3$, every graph in ${\cal G}_{\ell}$ is 4-colorable. It is not known whether there exists a small constant $c$ such that graphs of ${\cal G}_2$ are $c$-colorable. In this paper, we show that every graph in ${\cal G}_2$ is 1456-colorable, and every graph in ${\cal A}_{3}$ is 4-colorable. We also show that every 7-hole free graph in ${\cal B}_{\ell}$ is $(12\ell+8)$-colorable. </p> </div> </dd> <dt> <a name='item16'>[16]</a> <a href ="/abs/2504.01918" title="Abstract" id="2504.01918"> arXiv:2504.01918 </a> [<a href="/pdf/2504.01918" title="Download PDF" id="pdf-2504.01918" aria-labelledby="pdf-2504.01918">pdf</a>, <a href="https://arxiv.org/html/2504.01918v1" title="View HTML" id="html-2504.01918" aria-labelledby="html-2504.01918" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01918" title="Other formats" id="oth-2504.01918" aria-labelledby="oth-2504.01918">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Long-eared digraphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Ben%C3%ADtez-Bobadilla,+G">Germ谩n Ben铆tez-Bobadilla</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Galeana-S%C3%A1nchez,+H">Hortensia Galeana-S谩nchez</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Hern%C3%A1ndez-Cruz,+C">C茅sar Hern谩ndez-Cruz</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> Let $H$ be a subdigraph of a digraph $D$. An ear of $H$ in $D$ is a path or a cycle in $D$ whose ends lie in $H$ but whose internal vertices do not. An \emph{ear decomposition} of a strong digraph $D$ is a nested sequence $(D_0,D_1,\ldots , D_k)$ of strong subdigraphs of $D$ such that: 1) $D_0$ is a cycle, 2) $D_{i+1} = D_i\cup P_i$, where $P_i$ is an ear of $D_i$ in $D$, for every $i\in \{0,1,\ldots,k-1\}$, and 3) $D_k=D$. <br>In this work, the $\mathcal{LE}_i$ is defined as the family of strong digraphs, with an ear decomposition such that every ear has a length of at least $i\geq 1$. It is proved that Seymour's second Neighborhood Conjecture and the Laborde, Payan, and Soung conjecture, are true in the family $\mathcal{LE}_2$, and the Small quasi-kernel conjecture is true for digraphs in $\mathcal{LE}_3$. Also, some sufficient conditions for a strong nonseparable digraph in $\mathcal{LE}_2$ with a kernel to imply that the previous (following) subdigraph in the ear decomposition has a kernel too, are presented. It is proved that digraphs in $\mathcal{LE}_2$ have a chromatic number at most 3, and a dichromatic number 2 or 3. Finally, the oriented chromatic number of asymmetrical digraphs in $\mathcal{LE}_3$ is bounded by 6, and it is shown that the oriented chromatic number of asymmetrical digraphs in $\mathcal{LE}_2$ is not bounded. </p> </div> </dd> <dt> <a name='item17'>[17]</a> <a href ="/abs/2504.01932" title="Abstract" id="2504.01932"> arXiv:2504.01932 </a> [<a href="/pdf/2504.01932" title="Download PDF" id="pdf-2504.01932" aria-labelledby="pdf-2504.01932">pdf</a>, <a href="https://arxiv.org/html/2504.01932v1" title="View HTML" id="html-2504.01932" aria-labelledby="html-2504.01932" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01932" title="Other formats" id="oth-2504.01932" aria-labelledby="oth-2504.01932">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Semidefinite lower bounds for covering codes </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Gijswijt,+D">Dion Gijswijt</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Polak,+S">Sven Polak</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Information Theory (cs.IT); Optimization and Control (math.OC) </div> <p class='mathjax'> Let $K_q(n,r)$ denote the minimum size of a $q$-ary covering code of word length $n$ and covering radius $r$. In other words, $K_q(n,r)$ is the minimum size of a set of $q$-ary codewords of length $n$ such that the Hamming balls of radius $r$ around the codewords cover the Hamming space $\{0,\ldots,q-1\}^n$. The special case $K_3(n,1)$ is often referred to as the football pool problem, as it is equivalent to finding a set of forecasts on $n$ football matches that is guaranteed to contain a forecast with at most one wrong outcome. <br>In this paper, we build and expand upon the work of Gijswijt (2005), who introduced a semidefinite programming lower bound on $K_q(n,r)$ via matrix cuts. We develop techniques that strengthen this bound, by introducing new semidefinite constraints inspired by Lasserre's hierarchy for 0-1 programs and symmetry reduction methods, and a more powerful objective function. The techniques lead to sharper lower bounds, setting new records across a broad range of values of $q$, $n$, and $r$. </p> </div> </dd> </dl> <dl id='articles'> <h3>Cross submissions (showing 3 of 3 entries)</h3> <dt> <a name='item18'>[18]</a> <a href ="/abs/2504.01254" title="Abstract" id="2504.01254"> arXiv:2504.01254 </a> (cross-list from math.GT) [<a href="/pdf/2504.01254" title="Download PDF" id="pdf-2504.01254" aria-labelledby="pdf-2504.01254">pdf</a>, <a href="https://arxiv.org/html/2504.01254v1" title="View HTML" id="html-2504.01254" aria-labelledby="html-2504.01254" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01254" title="Other formats" id="oth-2504.01254" aria-labelledby="oth-2504.01254">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A robot that unknots knots </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Hui,+C+O+Y">Connie On Yu Hui</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Ibarra,+D">Dionne Ibarra</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Kauffman,+L+H">Louis H. Kauffman</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=McQuire,+E+N">Emma N. McQuire</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Montoya-Vega,+G">Gabriel Montoya-Vega</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Mukherjee,+S">Sujoy Mukherjee</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Reid,+C">Corbin Reid</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 30 pages, 28 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Geometric Topology (math.GT)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> Consider a robot that walks along a knot once on a knot diagram and switches every undercrossing it meets, stopping when it comes back to the starting position. We show that such a robot always unknots the knot. In fact, we prove that the robot produces an ascending diagram, and we provide a purely combinatorial proof that every ascending or descending knot diagram with C crossings can be transformed into the zero-crossing unknot diagram using at most (7C+1)C Reidemeister moves. Moreover, we show that an ascending or descending knot diagram can always be transformed into a zero-crossing unknot diagram using Reidemeister moves that do not increase the number of crossings. </p> </div> </dd> <dt> <a name='item19'>[19]</a> <a href ="/abs/2504.01623" title="Abstract" id="2504.01623"> arXiv:2504.01623 </a> (cross-list from math.RT) [<a href="/pdf/2504.01623" title="Download PDF" id="pdf-2504.01623" aria-labelledby="pdf-2504.01623">pdf</a>, <a href="https://arxiv.org/html/2504.01623v1" title="View HTML" id="html-2504.01623" aria-labelledby="html-2504.01623" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01623" title="Other formats" id="oth-2504.01623" aria-labelledby="oth-2504.01623">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Log-concavity of characters of parabolic Verma modules, and of restricted Kostant partition functions </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Khare,+A">Apoorva Khare</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Matherne,+J+P">Jacob P. Matherne</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Dizier,+A+S">Avery St. Dizier</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 22 pages, no figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Representation Theory (math.RT)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> In 2022, Huh-Matherne-Meszaros-St. Dizier showed that normalized Schur polynomials are Lorentzian, thereby yielding their continuous (resp. discrete) log-concavity on the positive orthant (resp. on their support, in type-$A$ root directions). A reinterpretation of this result is that the characters of finite-dimensional simple representations of $\mathfrak{sl}_{n+1}(\mathbb{C})$ are denormalized Lorentzian. In the same paper, these authors also showed that shifted characters of Verma modules over $\mathfrak{sl}_{n+1}(\mathbb{C})$ are denormalized Lorentzian. <br>In this work we extend these results to a larger family of modules that subsumes both of the above: we show that shifted characters of all parabolic Verma modules over $\mathfrak{sl}_{n+1}(\mathbb{C})$ are denormalized Lorentzian. The proof involves certain graphs on $[n+1]$; more strongly, we explain why the character (i.e., generating function) of the Kostant partition function of any loopless multigraph on $[n+1]$ is Lorentzian after shifting and normalizing. In contrast, we show that a larger universal family of highest weight modules, the higher order Verma modules, do not have discretely log-concave characters. Finally, we extend all of these results to parabolic (i.e. "first order") and higher order Verma modules over the semisimple Lie algebras $\oplus_{t=1}^T \mathfrak{sl}_{n_t+1}(\mathbb{C})$. </p> </div> </dd> <dt> <a name='item20'>[20]</a> <a href ="/abs/2504.01628" title="Abstract" id="2504.01628"> arXiv:2504.01628 </a> (cross-list from math.OC) [<a href="/pdf/2504.01628" title="Download PDF" id="pdf-2504.01628" aria-labelledby="pdf-2504.01628">pdf</a>, <a href="https://arxiv.org/html/2504.01628v1" title="View HTML" id="html-2504.01628" aria-labelledby="html-2504.01628" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2504.01628" title="Other formats" id="oth-2504.01628" aria-labelledby="oth-2504.01628">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Copositive geometry of Feynman integrals </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Sturmfels,+B">Bernd Sturmfels</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Telek,+M+L">M谩t茅 L. Telek</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Optimization and Control (math.OC)</span>; High Energy Physics - Theory (hep-th); Mathematical Physics (math-ph); Combinatorics (math.CO) </div> <p class='mathjax'> Copositive matrices and copositive polynomials are objects from optimization. We connect these to the geometry of Feynman integrals in physics. The integral is guaranteed to converge if its kinematic parameters lie in the copositive cone. P贸lya's method makes this manifest. We study the copositive cone for the second Symanzik polynomial of any Feynman graph. Its algebraic boundary is described by Landau discriminants. </p> </div> </dd> </dl> <dl id='articles'> <h3>Replacement submissions (showing 14 of 14 entries)</h3> <dt> <a name='item21'>[21]</a> <a href ="/abs/2405.11556" title="Abstract" id="2405.11556"> arXiv:2405.11556 </a> (replaced) [<a href="/pdf/2405.11556" title="Download PDF" id="pdf-2405.11556" aria-labelledby="pdf-2405.11556">pdf</a>, <a href="https://arxiv.org/html/2405.11556v2" title="View HTML" id="html-2405.11556" aria-labelledby="html-2405.11556" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2405.11556" title="Other formats" id="oth-2405.11556" aria-labelledby="oth-2405.11556">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Factor Width Rank of a Matrix </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Johnston,+N">Nathaniel Johnston</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Moein,+S">Shirin Moein</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Plosker,+S">Sarah Plosker</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 23 pages, newly added Theorem 2 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> A matrix is said to have factor width at most $k$ if it can be written as a sum of positive semidefinite matrices that are non-zero only in a single $k \times k$ principal submatrix. We explore the ``factor-width-$k$ rank'' of a matrix, which is the minimum number of rank-$1$ matrices that can be used in such a factor-width-at-most-$k$ decomposition. We show that the factor width rank of a banded or arrowhead matrix equals its usual rank, but for other matrices they can differ. We also establish several bounds on the factor width rank of a matrix, including a tight connection between factor-width-$k$ rank and the $k$-clique covering number of a graph, and we discuss how the factor width and factor width rank change when taking Hadamard products and Hadamard powers. </p> </div> </dd> <dt> <a name='item22'>[22]</a> <a href ="/abs/2409.03903" title="Abstract" id="2409.03903"> arXiv:2409.03903 </a> (replaced) [<a href="/pdf/2409.03903" title="Download PDF" id="pdf-2409.03903" aria-labelledby="pdf-2409.03903">pdf</a>, <a href="https://arxiv.org/html/2409.03903v2" title="View HTML" id="html-2409.03903" aria-labelledby="html-2409.03903" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2409.03903" title="Other formats" id="oth-2409.03903" aria-labelledby="oth-2409.03903">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Deriving differential approximation results for $k\,$CSPs from combinatorial designs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Culus,+J">Jean-Fran莽ois Culus</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Toulouse,+S">Sophie Toulouse</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Preliminary versions of this work have been presented or published at the ISCO 2012, ISCO 2018 and IWOCA 2018 conferences </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Computational Complexity (cs.CC) </div> <p class='mathjax'> Inapproximability results for $\mathsf{Max\,k\,CSP\!-\!q}$ have been traditionally established using balanced $t$-wise independent distributions, which are closely related to orthogonal arrays, a famous family of combinatorial designs. In this work, we investigate the role of these combinatorial structures in the context of the differential approximability of $\mathsf{k\,CSP\!-\!q}$, providing new structural insights and approximation bounds. We first establish a direct connection between the average differential ratio on $\mathsf{k\,CSP\!-\!q}$ instances and orthogonal arrays. This allows us to derive the new differential approximability bounds of $1/q^k$ for $(k +1)$-partite instances, $\Omega(1/n^{\lfloor k/2\rfloor})$ for Boolean instances, $\Omega(1/n)$ when $k =2$, and $\Omega(1/n^{k -\lceil\log_{\Theta(q)}k\rceil})$ when $k, q\geq 3$. We then introduce families of array pairs, called {\em alphabet reduction pairs of arrays}, that are still related to balanced $k$-wise independence. Using these pairs of arrays, we establish a reduction from $\mathsf{k\,CSP\!-\!q}$ to $\mathsf{k\,CSP\!-\!k}$ (where $q >k$), with an expansion factor of $1/(q -k/2)^k$ on the differential approximation guarantee. Combining this with a 1998 result by Yuri Nesterov, we conclude that $\mathsf{2\,CSP\!-\!q}$ is approximable within a differential factor of $0.429/(q -1)^2$. Finally, using similar Boolean array pairs, {\em called cover pairs of arrays}, we prove that every Hamming ball of radius $k$ provides a $\Omega(1/n^k)$-approximation of the instance diameter. Thus, our work highlights the relevance of combinatorial designs for establishing structural differential approximation guarantees for CSPs. </p> </div> </dd> <dt> <a name='item23'>[23]</a> <a href ="/abs/2409.18250" title="Abstract" id="2409.18250"> arXiv:2409.18250 </a> (replaced) [<a href="/pdf/2409.18250" title="Download PDF" id="pdf-2409.18250" aria-labelledby="pdf-2409.18250">pdf</a>, <a href="https://arxiv.org/html/2409.18250v2" title="View HTML" id="html-2409.18250" aria-labelledby="html-2409.18250" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2409.18250" title="Other formats" id="oth-2409.18250" aria-labelledby="oth-2409.18250">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A bounded diameter strengthening of K艖nig's Theorem </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=DeBiasio,+L">Louis DeBiasio</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Gir%C3%A3o,+A">Ant贸nio Gir茫o</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Haxell,+P">Penny Haxell</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Stein,+M">Maya Stein</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 6 pages, 1 figure, minor revision in response to referee reports </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> K\H onig's theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at most the vertex cover number). An equivalent formulation of K\H onig's theorem is that in every $2$-colouring of the edges of a graph $G$, the number of monochromatic components needed to cover the vertex set of $G$ is at most the independence number of $G$. <br>We prove the following strengthening of K\H onig's theorem: In every $2$-colouring of the edges of a graph $G$, the number of monochromatic subgraphs of bounded diameter needed to cover the vertex set of $G$ is at most the independence number of $G$. </p> </div> </dd> <dt> <a name='item24'>[24]</a> <a href ="/abs/2410.00281" title="Abstract" id="2410.00281"> arXiv:2410.00281 </a> (replaced) [<a href="/pdf/2410.00281" title="Download PDF" id="pdf-2410.00281" aria-labelledby="pdf-2410.00281">pdf</a>, <a href="https://arxiv.org/html/2410.00281v4" title="View HTML" id="html-2410.00281" aria-labelledby="html-2410.00281" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2410.00281" title="Other formats" id="oth-2410.00281" aria-labelledby="oth-2410.00281">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Connected components and non-bipartiteness of generalized Paley graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Podest%C3%A1,+R+A">Ricardo A. Podest谩</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Videla,+D+E">Denis E. Videla</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 22 pages, 3 figures. In Section 4 we use only graph theory and elemetary methods (we don't need to use Artin-Schreier curves anymore) </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> In this work we consider the class of Cayley graphs known as generalized Paley graphs (GP-graphs for short) given by $\Gamma(k,q) = Cay(\mathbb{F}_q, \{x^k : x\in \mathbb{F}_q^* \})$, where $\mathbb{F}_q$ is a finite field with $q$ elements, both in the directed and undirected case. Hence $q=p^m$ with $p$ prime, $m\in \mathbb{N}$ and one can assume that $k\mid q-1$. We first give the connected components of an arbitrary GP-graph. We show that these components are smaller GP-graphs all isomorphic to each other (generalizing a Lim and Praeger's result from 2009 to the directed case). We then characterize those GP-graphs which are disjoint unions of odd cycles. Finally, we show that $\Gamma(k,q)$ is non-bipartite except for the graphs $\Gamma(2^m-1,2^m)$, $m \in \mathbb{N}$, which are isomorphic to $K_2 \sqcup \cdots \sqcup K_2$, the disjoint union of $2^{m-1}$ copies of $K_2$. </p> </div> </dd> <dt> <a name='item25'>[25]</a> <a href ="/abs/2410.09585" title="Abstract" id="2410.09585"> arXiv:2410.09585 </a> (replaced) [<a href="/pdf/2410.09585" title="Download PDF" id="pdf-2410.09585" aria-labelledby="pdf-2410.09585">pdf</a>, <a href="https://arxiv.org/html/2410.09585v2" title="View HTML" id="html-2410.09585" aria-labelledby="html-2410.09585" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2410.09585" title="Other formats" id="oth-2410.09585" aria-labelledby="oth-2410.09585">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Conjugation of reddening sequences and conjugation difference </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Liu,+S">Siyang Liu</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Pan,+J">Jie Pan</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> We describe the conjugation of the reddening sequence according to the formula of $c$-vectors with respect to changing the initial seed. As applications, we extend the Rotation Lemma, the Target before Source Theorem, and the mutation invariant property of the existence of reddening sequences to totally sign-skew-symmetric cluster algebras. Furthermore, this also leads to the construction of conjugation difference which characterizes the number of red mutations a maximal green sequence should admit in any matrix pattern with the initial seed changed via mutations. </p> </div> </dd> <dt> <a name='item26'>[26]</a> <a href ="/abs/2412.02064" title="Abstract" id="2412.02064"> arXiv:2412.02064 </a> (replaced) [<a href="/pdf/2412.02064" title="Download PDF" id="pdf-2412.02064" aria-labelledby="pdf-2412.02064">pdf</a>, <a href="https://arxiv.org/html/2412.02064v3" title="View HTML" id="html-2412.02064" aria-labelledby="html-2412.02064" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2412.02064" title="Other formats" id="oth-2412.02064" aria-labelledby="oth-2412.02064">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Vanishing of Schubert Coefficients </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Pak,+I">Igor Pak</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Robichaux,+C">Colleen Robichaux</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 30 pages, with a joint appendix with David E Speyer. The type D background now appears in Appendix A. The BSS model results are now in Appendix B, with typos fixed. The type D results, joint with Speyer, appear in Appendix C </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); Algebraic Geometry (math.AG) </div> <p class='mathjax'> Schubert coefficients are nonnegative integers $c^w_{u,v}$ that arise in Algebraic Geometry and play a central role in Algebraic Combinatorics. It is a major open problem whether they have a combinatorial interpretation, i.e, whether $c^w_{u,v} \in \#{\sf P}$. We study the closely related vanishing problem of Schubert coefficients: $\{c^w_{u,v}=^? 0\}$. Until this work it was open whether this problem is in the polynomial hierarchy ${\sf PH}$. We prove that $\{c^w_{u,v}=^? 0\}$ in ${\sf coAM}$ assuming the GRH. In particular, the vanishing problem is in ${\Sigma_2^{\text{p}}}$. Our approach is based on constructions lifted formulations, which give polynomial systems of equations for the problem. The result follows from a reduction to Parametric Hilbert's Nullstellensatz, recently studied in <a href="https://arxiv.org/abs/2408.13027" data-arxiv-id="2408.13027" class="link-https">arXiv:2408.13027</a>. We extend our results to all classical types. Type $D$ is resolved in the appendix (joint with David Speyer). </p> </div> </dd> <dt> <a name='item27'>[27]</a> <a href ="/abs/2501.00440" title="Abstract" id="2501.00440"> arXiv:2501.00440 </a> (replaced) [<a href="/pdf/2501.00440" title="Download PDF" id="pdf-2501.00440" aria-labelledby="pdf-2501.00440">pdf</a>, <a href="https://arxiv.org/html/2501.00440v2" title="View HTML" id="html-2501.00440" aria-labelledby="html-2501.00440" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2501.00440" title="Other formats" id="oth-2501.00440" aria-labelledby="oth-2501.00440">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Substitution dynamical systems are loosely Kronecker </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Best,+A">Andrew Best</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Peres,+Y">Yuval Peres</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 25 pages, 4 figures; updated introduction </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Dynamical Systems (math.DS) </div> <p class='mathjax'> Let $\sigma$ be a primitive substitution on an alphabet $\mathcal{A}$, and let $\mathcal{W}_n$ be the set of words of length $n$ determined by $\sigma$ (i.e., $w \in \mathcal{W}_n$ if $w$ is a subword of $\sigma^k(a)$ for some $a \in \mathcal{A}$ and $k \geq 1$). We show that the diameter of $\mathcal{W}_n$ in the edit distance is $o(n)$. Thus, any two words in $\mathcal{W}_n$ have a common subsequence of length $n-o(n)$, which implies that the corresponding substitution dynamical system is loosely Kronecker (also known as zero-entropy loosely Bernoulli). The main challenge is handling the case where $\sigma$ is non-uniform. Finally, we show that for the Thue--Morse substitution, the diameter of $\mathcal{W}_n$ is at least $\sqrt {n/6} - 1$. </p> </div> </dd> <dt> <a name='item28'>[28]</a> <a href ="/abs/2501.07269" title="Abstract" id="2501.07269"> arXiv:2501.07269 </a> (replaced) [<a href="/pdf/2501.07269" title="Download PDF" id="pdf-2501.07269" aria-labelledby="pdf-2501.07269">pdf</a>, <a href="https://arxiv.org/html/2501.07269v2" title="View HTML" id="html-2501.07269" aria-labelledby="html-2501.07269" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2501.07269" title="Other formats" id="oth-2501.07269" aria-labelledby="oth-2501.07269">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The wreath matrix </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Petr,+J">Jan Petr</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Turek,+P">Pavel Turek</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 18 pages, 3 figures v2: discussed case k|n in more detail, added affiliations, fixed typos </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Representation Theory (math.RT) </div> <p class='mathjax'> Let $k\leq n$ be positive integers and $\mathbb{Z}_{n}$ be the set of integers modulo $n$. A conjecture of Baranyai from 1974 asks for a decomposition of $k$-element subsets of $\mathbb{Z}_{n}$ into particular families of sets called "wreaths". We approach this conjecture from a new algebraic angle by introducing the key object of this paper, the wreath matrix $M$. As our first result, we establish that Baranyai's conjecture is equivalent to the existence of a particular vector in the kernel of $M$. We then employ results from representation theory to study $M$ and its spectrum in detail. In particular, we find all eigenvalues of $M$ and their multiplicities, and identify several families of vectors which lie in the kernel of $M$. </p> </div> </dd> <dt> <a name='item29'>[29]</a> <a href ="/abs/2502.20428" title="Abstract" id="2502.20428"> arXiv:2502.20428 </a> (replaced) [<a href="/pdf/2502.20428" title="Download PDF" id="pdf-2502.20428" aria-labelledby="pdf-2502.20428">pdf</a>, <a href="https://arxiv.org/html/2502.20428v2" title="View HTML" id="html-2502.20428" aria-labelledby="html-2502.20428" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2502.20428" title="Other formats" id="oth-2502.20428" aria-labelledby="oth-2502.20428">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Aggregation of evaluations without unanimity </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Filmus,+Y">Yuval Filmus</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 20 pages; a formally verified version can be found at <a href="https://github.com/YuvalFilmus/Polymorphisms/" 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">Combinatorics (math.CO)</span>; Discrete Mathematics (cs.DM); Logic (math.LO) </div> <p class='mathjax'> Dokow and Holzman determined which predicates over $\{0, 1\}$ satisfy an analog of Arrow's theorem: all unanimous aggregators are dictatorial. Szegedy and Xu, extending earlier work of Dokow and Holzman, extended this to predicates over arbitrary finite alphabets. <br>Mossel extended Arrow's theorem in an orthogonal direction, determining all aggregators without the assumption of unanimity. We bring together both threads of research by extending the results of Dokow-Holzman and Szegedy-Xu to the setting of Mossel. As an application, we determine, for each symmetric predicate over $\{0,1\}$, all of its aggregators. </p> </div> </dd> <dt> <a name='item30'>[30]</a> <a href ="/abs/2306.07459" title="Abstract" id="2306.07459"> arXiv:2306.07459 </a> (replaced) [<a href="/pdf/2306.07459" title="Download PDF" id="pdf-2306.07459" aria-labelledby="pdf-2306.07459">pdf</a>, <a href="https://arxiv.org/html/2306.07459v2" title="View HTML" id="html-2306.07459" aria-labelledby="html-2306.07459" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2306.07459" title="Other formats" id="oth-2306.07459" aria-labelledby="oth-2306.07459">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Log-concavity for partitions without sequences </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Mauth,+L">Lukas Mauth</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 31 pages. Gave a new extended proof of the main result. Proof uses help of computer in certain places (see code attached for details) </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Number Theory (math.NT)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> We prove log-concavity for the function counting partitions without sequences. We use an exact formula for a mixed-mock modular form of weight zero, explicit estimates on modified Kloosterman sums and analytic techniques. Finally, we establish the higher Tur谩n inequalities in an asymptotic form of the aforementioned partition function using a well established criterion of Griffin, Ono, Rolen, and Zagier on the zeros of Jensen polynomials. </p> </div> </dd> <dt> <a name='item31'>[31]</a> <a href ="/abs/2307.10441" title="Abstract" id="2307.10441"> arXiv:2307.10441 </a> (replaced) [<a href="/pdf/2307.10441" title="Download PDF" id="pdf-2307.10441" aria-labelledby="pdf-2307.10441">pdf</a>, <a href="https://arxiv.org/html/2307.10441v2" title="View HTML" id="html-2307.10441" aria-labelledby="html-2307.10441" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2307.10441" title="Other formats" id="oth-2307.10441" aria-labelledby="oth-2307.10441">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Exact formula for 1-lower run overpartitions </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Mauth,+L">Lukas Mauth</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 20 pages. Fixed many typos. Added additional references </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Number Theory (math.NT)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> We are going to show an exact formula for lower $1$-run overpartitions. The generating function is of mixed mock-modular type with an overall weight $0.$ We will apply an extended version of the classical Circle Method. The approach requires bounding modified Kloosterman sums and Mordell integrals. </p> </div> </dd> <dt> <a name='item32'>[32]</a> <a href ="/abs/2404.06754" title="Abstract" id="2404.06754"> arXiv:2404.06754 </a> (replaced) [<a href="/pdf/2404.06754" title="Download PDF" id="pdf-2404.06754" aria-labelledby="pdf-2404.06754">pdf</a>, <a href="https://arxiv.org/html/2404.06754v2" title="View HTML" id="html-2404.06754" aria-labelledby="html-2404.06754" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2404.06754" title="Other formats" id="oth-2404.06754" aria-labelledby="oth-2404.06754">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Mutual position of two smooth quadrics over finite fields </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Asgarli,+S">Shamil Asgarli</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Yip,+C+H">Chi Hoi Yip</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 11 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Algebraic Geometry (math.AG)</span>; Combinatorics (math.CO); Number Theory (math.NT) </div> <p class='mathjax'> Given two irreducible conics $C$ and $D$ over a finite field $\mathbb{F}_q$ with $q$ odd, we show that there are $q^2/4+O(q^{3/2})$ points $P$ in $\mathbb{P}^2(\mathbb{F}_q)$ such that $P$ is external to $C$ and internal to $D$. This answers a question of Korchm谩ros. We also prove the analogous result for higher-dimensional smooth quadric hypersurfaces in $\mathbb{P}^{n-1}$ with $n$ odd, where the answer is $q^{n-1}/4+O(q^{n-\frac{3}{2}})$. </p> </div> </dd> <dt> <a name='item33'>[33]</a> <a href ="/abs/2411.11404" title="Abstract" id="2411.11404"> arXiv:2411.11404 </a> (replaced) [<a href="/pdf/2411.11404" title="Download PDF" id="pdf-2411.11404" aria-labelledby="pdf-2411.11404">pdf</a>, <a href="https://arxiv.org/html/2411.11404v2" title="View HTML" id="html-2411.11404" aria-labelledby="html-2411.11404" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2411.11404" title="Other formats" id="oth-2411.11404" aria-labelledby="oth-2411.11404">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Arithmetic properties of MacMahon-type sums of divisors </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Sellers,+J+A">James A. Sellers</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Tauraso,+R">Roberto Tauraso</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> accepted for publication in The Ramanujan Journal </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Number Theory (math.NT)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> In this paper, we prove several new infinite families of Ramanujan--like congruences satisfied by the coefficients of the generating function $U_t(a,q)$ which is an extension of MacMahon's generalized sum-of-divisors function. As a by-product, we also show that, for all $n\geq 0$, $\overline{B}_3(15n+7)\equiv 0 \pmod{5}$ where $\overline{B}_3(n)$ is the number of almost $3$-regular overpartitions of $n$. </p> </div> </dd> <dt> <a name='item34'>[34]</a> <a href ="/abs/2503.22368" title="Abstract" id="2503.22368"> arXiv:2503.22368 </a> (replaced) [<a href="/pdf/2503.22368" title="Download PDF" id="pdf-2503.22368" aria-labelledby="pdf-2503.22368">pdf</a>, <a href="https://arxiv.org/html/2503.22368v2" title="View HTML" id="html-2503.22368" aria-labelledby="html-2503.22368" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.22368" title="Other formats" id="oth-2503.22368" aria-labelledby="oth-2503.22368">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On Finding All Connected Maximum-Sized Common Subgraphs in Multiple Labeled Graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Petersen,+J+B">Johannes B.S. Petersen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Davoodi,+A">Akbar Davoodi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=G%C3%A4rtner,+T">Thomas G盲rtner</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Hellmuth,+M">Marc Hellmuth</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Merkle,+D">Daniel Merkle</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); Combinatorics (math.CO); Molecular Networks (q-bio.MN) </div> <p class='mathjax'> We present an exact algorithm for computing all common subgraphs with the maximum number of vertices across multiple graphs. Our approach is further extended to handle the connected Maximum Common Subgraph (MCS), identifying the largest common subgraph in terms of either vertices or edges across multiple graphs, where edges or vertices may additionally be labeled to account for possible atom types or bond types, a classical labeling used in molecular graphs. Our approach leverages modular product graphs and a modified Bron-Kerbosch algorithm to enumerate maximal cliques, ensuring all intermediate solutions are retained. A pruning heuristic efficiently reduces the modular product size, improving computational feasibility. Additionally, we introduce a graph ordering strategy based on graph-kernel similarity measures to optimize the search process. Our method is particularly relevant for bioinformatics and cheminformatics, where identifying conserved structural motifs in molecular graphs is crucial. Empirical results on molecular datasets demonstrate that our approach is scalable and fast. </p> </div> </dd> </dl> <div class='paging'>Total of 34 entries </div> <div class='morefewer'>Showing up to 2000 entries per page: <a href=/list/math.CO/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">  <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>   <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>   </div> </footer> </div> <script src="/static/base/1.0.1/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Combinatorics