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="#item14">Cross-lists</a></li> <li><a href="#item18">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 Friday, 28 March 2025</h3> <div class='paging'>Total of 33 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 13 of 13 entries)</h3> <dt> <a name='item1'>[1]</a> <a href ="/abs/2503.20901" title="Abstract" id="2503.20901"> arXiv:2503.20901 </a> [<a href="/pdf/2503.20901" title="Download PDF" id="pdf-2503.20901" aria-labelledby="pdf-2503.20901">pdf</a>, <a href="https://arxiv.org/html/2503.20901v1" title="View HTML" id="html-2503.20901" aria-labelledby="html-2503.20901" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.20901" title="Other formats" id="oth-2503.20901" aria-labelledby="oth-2503.20901">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Fractional coloring of product signed graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Atangana,+P+D+E">Pie Desire Ebode Atangana</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 11 pages, 0 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 study the fractional chromatic number of signed circulant graphs' direct product is investigated. As previously shown \cite{hedetniemi1966homomorphism}, we prove that the direct product of two signed graphs has a fractional chromatic number that is limited to a value greater than the minimum of their individual fractional chromatic numbers. Hedetniemi (1966) demonstrated that the structure of signed circulant graphs' generating sets determines their fractional chromatic number, and this conclusion is further applied to these graphs. Furthermore, we apply our results to the direct product of two signed circulant graphs and obtain corollaries for situations when one of the graphs in the product has a smaller fractional chromatic number \cite{Zhu2002fractional}. This conclusion generalises earlier work on unsigned graphs and offers a thorough foundation for comprehending the fractional colouring of signed circulant graphs and their products \cite{shitov2019counterexample}. </p> </div> </dd> <dt> <a name='item2'>[2]</a> <a href ="/abs/2503.20954" title="Abstract" id="2503.20954"> arXiv:2503.20954 </a> [<a href="/pdf/2503.20954" title="Download PDF" id="pdf-2503.20954" aria-labelledby="pdf-2503.20954">pdf</a>, <a href="https://arxiv.org/html/2503.20954v1" title="View HTML" id="html-2503.20954" aria-labelledby="html-2503.20954" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.20954" title="Other formats" id="oth-2503.20954" aria-labelledby="oth-2503.20954">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Edge-addition in hereditary classes of graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Singh,+J">Jagdeep Singh</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Sivaraman,+V">Vaidy Sivaraman</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 14 pages, 6 figures, a revised version will be available shortly </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> A class $\mathcal{G}$ of graphs is hereditary if it is closed under taking induced subgraphs. We denote by $\mathcal{G}^\mathrm{add}$ the class of graphs that are at most one edge addition away from being in $\mathcal{G}$, and by $\mathcal{G}^\mathrm{epex}$ the class of graphs that are at most one edge deletion away from being in $\mathcal{G}$. In previous work, we showed that if a hereditary class $\mathcal{G}$ has finitely many forbidden induced subgraphs, then so does the hereditary class $\mathcal{G}^\mathrm{epex}$. In this paper, we prove the corresponding results for $\mathcal{G}^\mathrm{add}$. We also note that if $\mathcal{G}$ is closed under complementation, then the forbidden induced subgraphs of $\mathcal{G}^\mathrm{add}$ and $\mathcal{G}^\mathrm{epex}$ are complements of each other. We provide the list of forbidden induced subgraphs for $\mathcal{G}^\mathrm{add}$, and consequently for $\mathcal{G}^\mathrm{epex}$ when $\mathcal{G}$ is the class of split graphs, cographs, or threshold graphs. Moreover, following Gyarfas's framework, we introduce the class of $(p,q)$-edge split graphs, analogous to his $(p,q)$-split graphs, and prove that they also have a finite number of forbidden induced subgraphs. </p> </div> </dd> <dt> <a name='item3'>[3]</a> <a href ="/abs/2503.21052" title="Abstract" id="2503.21052"> arXiv:2503.21052 </a> [<a href="/pdf/2503.21052" title="Download PDF" id="pdf-2503.21052" aria-labelledby="pdf-2503.21052">pdf</a>, <a href="https://arxiv.org/html/2503.21052v1" title="View HTML" id="html-2503.21052" aria-labelledby="html-2503.21052" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21052" title="Other formats" id="oth-2503.21052" aria-labelledby="oth-2503.21052">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Disperse Hypergraphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Gishboliner,+L">Lior Gishboliner</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Honest,+E">Ethan Honest</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> An $\ell$-uniform hypergraph is disperse if the number of edges induced by any set of $\ell+1$ vertices is 0, 1, $\ell$ or $\ell+1$. We show that every disperse $\ell$-uniform hypergraph on $n$ vertices contains a clique or independent set of size $n^{\Omega_{\ell}(1)}$, answering a question of the first author and Tomon. To this end, we prove several structural properties of disperse hypergraphs. </p> </div> </dd> <dt> <a name='item4'>[4]</a> <a href ="/abs/2503.21077" title="Abstract" id="2503.21077"> arXiv:2503.21077 </a> [<a href="/pdf/2503.21077" title="Download PDF" id="pdf-2503.21077" aria-labelledby="pdf-2503.21077">pdf</a>, <a href="https://arxiv.org/html/2503.21077v1" title="View HTML" id="html-2503.21077" aria-labelledby="html-2503.21077" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21077" title="Other formats" id="oth-2503.21077" aria-labelledby="oth-2503.21077">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Terwilliger algebra of digraphs I -- Hamming digraph $H^*(d,3)$ </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Miezaki,+T">Tsuyoshi Miezaki</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Suzuki,+H">Hiroshi Suzuki</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Uchida,+K">Keisuke Uchida</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 21 pages </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'> In the present paper, we define the Terwilliger algebra of digraphs. Then, we determine the irreducible modules of the Terwilliger algebra of a Hamming digraph $H^*(d,3)$. As is well known, the representation of the Terwilliger algebra of a binary Hamming graph $H(d,2)$ is closely related to that of the Lie algebra $\mathit{sl}_2(\mathbb{C})$. We show that in the case of $H^*(d,3)$, it is related to that of the Lie algebra $\mathit{sl}_3(\mathbb{C})$. We also identify the Terwilliger algebra of $H^*(d,3)$ as the $d$ symmetric tensor algebra of ${\rm Mat}_3(\mathbb{C})$. </p> </div> </dd> <dt> <a name='item5'>[5]</a> <a href ="/abs/2503.21108" title="Abstract" id="2503.21108"> arXiv:2503.21108 </a> [<a href="/pdf/2503.21108" title="Download PDF" id="pdf-2503.21108" aria-labelledby="pdf-2503.21108">pdf</a>, <a href="https://arxiv.org/html/2503.21108v1" title="View HTML" id="html-2503.21108" aria-labelledby="html-2503.21108" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21108" title="Other formats" id="oth-2503.21108" aria-labelledby="oth-2503.21108">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The number of irreducibles in the plethysm $s_位[s_m]$ </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Lim,+M+Y">Ming Yean Lim</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 12 pages, extended abstract accepted to FPSAC 2025 </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'> We give a formula for the number of irreducibles (with multiplicity) in the decomposition of the plethysm $s_\lambda[s_m]$ of Schur functions in terms of the number of lattice points in certain rational polytopes. In the case where $\lambda = n$ consists of a single part, we will give a combinatorial interpretation of this number as the cardinality of a set of matrices modulo permutation equivalence. This is also the setting of Foulkes' conjecture, and our results allow us to state a weaker version that only involves comparing the cardinalities of such sets, rather than the multiplicities of irreducible representations. </p> </div> </dd> <dt> <a name='item6'>[6]</a> <a href ="/abs/2503.21174" title="Abstract" id="2503.21174"> arXiv:2503.21174 </a> [<a href="/pdf/2503.21174" title="Download PDF" id="pdf-2503.21174" aria-labelledby="pdf-2503.21174">pdf</a>, <a href="https://arxiv.org/html/2503.21174v1" title="View HTML" id="html-2503.21174" aria-labelledby="html-2503.21174" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21174" title="Other formats" id="oth-2503.21174" aria-labelledby="oth-2503.21174">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the second-largest modulus among the eigenvalues of a power hypergraph </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Bu,+C">Changjiang Bu</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Chen,+L">Lixiang Chen</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Shi,+Y">Yongtang Shi</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 20 pages,7 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> It is well known that the algebraic multiplicity of an eigenvalue of a graph (or real symmetric matrix) is equal to the dimension of its corresponding linear eigen-subspace, also known as the geometric multiplicity. However, for hypergraphs, the relationship between these two multiplicities remains an open problem. For a graph $G=(V,E)$ and $k \geq 3$, the $k$-power hypergraph $G^{(k)}$ is a $k$-uniform hypergraph obtained by adding $k-2$ new vertices to each edge of $G$, who always has non-real eigenvalues. In this paper, we determine the second-largest modulus $\Lambda$ among the eigenvalues of $G^{(k)}$, which is indeed an eigenvalue of $G^{(k)}$. The projective eigenvariety $\mathbb{V}_{\Lambda}$ associated with $\Lambda$ is the set of the eigenvectors of $G^{(k)}$ corresponding to $\Lambda$ considered in the complex projective space. We show that the dimension of $\mathbb{V}_{\Lambda}$ is zero, i.e, there are finitely many eigenvectors corresponding to $\Lambda$ up to a scalar. We give both the algebraic multiplicity of $\Lambda$ and the total multiplicity of the eigenvector in $\mathbb{V}_{\Lambda}$ in terms of the number of the weakest edges of $G$. Our result show that these two multiplicities are equal. </p> </div> </dd> <dt> <a name='item7'>[7]</a> <a href ="/abs/2503.21194" title="Abstract" id="2503.21194"> arXiv:2503.21194 </a> [<a href="/pdf/2503.21194" title="Download PDF" id="pdf-2503.21194" aria-labelledby="pdf-2503.21194">pdf</a>, <a href="https://arxiv.org/html/2503.21194v1" title="View HTML" id="html-2503.21194" aria-labelledby="html-2503.21194" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21194" title="Other formats" id="oth-2503.21194" aria-labelledby="oth-2503.21194">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Matchgate signatures under variable permutations </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Meng,+B">Boning Meng</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Pan,+Y">Yicheng Pan</a></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'> In this article, we give a sufficient and necessary condition for determining whether a matchgate signature retains its property under a certain variable permutation, which can be checked in polynomial time. We also define the concept of permutable matchgate signatures, and use it to erase the gap between Pl-\#CSP and \#CSP on planar graphs in the previous study. We provide a detailed characterization of permutable matchgate signatures as well, by presenting their relation to symmetric matchgate signatures. In addition, we prove a dichotomy for Pl-$\#R_D$-CSP where $D\ge 3$ is an integer. </p> </div> </dd> <dt> <a name='item8'>[8]</a> <a href ="/abs/2503.21215" title="Abstract" id="2503.21215"> arXiv:2503.21215 </a> [<a href="/pdf/2503.21215" title="Download PDF" id="pdf-2503.21215" aria-labelledby="pdf-2503.21215">pdf</a>, <a href="/format/2503.21215" title="Other formats" id="oth-2503.21215" aria-labelledby="oth-2503.21215">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Cells of Gelfand $S_n$-Graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Zhang,+Y">Yifeng Zhang</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>; Representation Theory (math.RT) </div> <p class='mathjax'> Kazhdan and Lusztig introduced the $W$-graphs, which represent the multiplication action of the standard basis on the canonical bais in the Iwahori-Hecke algebra. In the Hecke algebra module, Marberg defined two generalied $W$-graphs, called the Gelfand $W$-graphs. The classification of the molecules of the type $\A$ Gelfand $S_n$-graphs are determined by two RSK-like insertion algorithms. We finish the classification of cells by proving that every molecule in the $S_n$-graphs is indeed a cell. </p> </div> </dd> <dt> <a name='item9'>[9]</a> <a href ="/abs/2503.21231" title="Abstract" id="2503.21231"> arXiv:2503.21231 </a> [<a href="/pdf/2503.21231" title="Download PDF" id="pdf-2503.21231" aria-labelledby="pdf-2503.21231">pdf</a>, <a href="https://arxiv.org/html/2503.21231v1" title="View HTML" id="html-2503.21231" aria-labelledby="html-2503.21231" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21231" title="Other formats" id="oth-2503.21231" aria-labelledby="oth-2503.21231">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the inverse problem of the $k$-th Davenport constants for groups of rank $2$ </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Zhong,+Q">Qinghai Zhong</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Number Theory (math.NT) </div> <p class='mathjax'> For a finite abelian group $G$ and a positive integer $k$, let $\mathsf{D}_k(G)$ denote the smallest integer $\ell$ such that each sequence over $G$ of length at least $\ell$ has $k$ disjoint nontrivial zero-sum subsequences. It is known that $\mathsf D_k(G)=n_1+kn_2-1$ if $G\cong C_{n_1}\oplus C_{n_2}$ is a rank $2$ group, where $1<n_1\t n_2$. We investigate the associated inverse problem for rank $2$ groups, that is, characterizing the structure of zero-sum sequences of length $\mathsf D_k(G)$ that can not be partitioned into $k+1$ nontrivial zero-sum subsequences. </p> </div> </dd> <dt> <a name='item10'>[10]</a> <a href ="/abs/2503.21287" title="Abstract" id="2503.21287"> arXiv:2503.21287 </a> [<a href="/pdf/2503.21287" title="Download PDF" id="pdf-2503.21287" aria-labelledby="pdf-2503.21287">pdf</a>, <a href="https://arxiv.org/html/2503.21287v1" title="View HTML" id="html-2503.21287" aria-labelledby="html-2503.21287" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21287" title="Other formats" id="oth-2503.21287" aria-labelledby="oth-2503.21287">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On Supports for graphs of bounded genus </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'> Let $(X,\mathcal{E})$ be a hypergraph. A support is a graph $Q$ on $X$ such that for each $E\in\mathcal{E}$, the subgraph of $Q$ induced on the elements in $E$ is connected. We consider the problem of constructing a support for hypergraphs defined by connected subgraphs of a host graph. For a graph $G=(V,E)$, let $\mathcal{H}$ be a set of connected subgraphs of $G$. Let the vertices of $G$ be partitioned into two sets the \emph{terminals} $\mathbf{b}(V)$ and the \emph{non-terminals} $\mathbf{r}(V)$. We define a hypergraph on $\mathbf{b}(V)$, where each $H\in\mathcal{H}$ defines a hyperedge consisting of the vertices of $\mathbf{b}(V)$ in $H$. <br>We also consider the problem of constructing a support for the \emph{dual hypergraph} - a hypergraph on $\mathcal{H}$ where each $v\in \mathbf{b}(V)$ defines a hyperedge consisting of the subgraphs in $\mathcal{H}$ containing $v$. In fact, we construct supports for a common generalization of the primal and dual settings called the \emph{intersection hypergraph}. <br>As our main result, we show that if the host graph $G$ has bounded genus and the subgraphs in $\mathcal{H}$ satisfy a condition of being \emph{cross-free}, then there exists a support that also has bounded genus. Our results are a generalization of the results of Raman and Ray (Rajiv Raman, Saurabh Ray: Constructing Planar Support for Non-Piercing Regions. Discret. Comput. Geom. 64(3): 1098-1122 (2020)). <br>Our techniques imply a unified analysis for packing and covering problems for hypergraphs defined on surfaces of bounded genus. We also describe applications of our results for hypergraph colorings. </p> </div> </dd> <dt> <a name='item11'>[11]</a> <a href ="/abs/2503.21574" title="Abstract" id="2503.21574"> arXiv:2503.21574 </a> [<a href="/pdf/2503.21574" title="Download PDF" id="pdf-2503.21574" aria-labelledby="pdf-2503.21574">pdf</a>, <a href="https://arxiv.org/html/2503.21574v1" title="View HTML" id="html-2503.21574" aria-labelledby="html-2503.21574" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21574" title="Other formats" id="oth-2503.21574" aria-labelledby="oth-2503.21574">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Unavoidable induced subgraphs of large and infinite $2$-edge-connected graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Allred,+S">Sarah Allred</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Ellingham,+M+N">M. N. Ellingham</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 19 pages, 6 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> In 1930, Ramsey proved that every large graph contains either a large clique or a large edgeless graph as an induced subgraph. It is well known that every large connected graph contains a long path, a large clique, or a large star as an induced subgraph. Recently Allred, Ding, and Oporowski presented the unavoidable large induced subgraphs for large $2$-connected graphs and for infinite $2$-connected graphs. In this paper we establish the $2$-edge-connected analogues of these results. As consequences we also obtain results on unavoidable large subgraphs, topological minors, minors, induced topological minors, induced minors, and Eulerian subgraphs in large and infinite $2$-edge-connected graphs. </p> </div> </dd> <dt> <a name='item12'>[12]</a> <a href ="/abs/2503.21672" title="Abstract" id="2503.21672"> arXiv:2503.21672 </a> [<a href="/pdf/2503.21672" title="Download PDF" id="pdf-2503.21672" aria-labelledby="pdf-2503.21672">pdf</a>, <a href="https://arxiv.org/html/2503.21672v1" title="View HTML" id="html-2503.21672" aria-labelledby="html-2503.21672" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21672" title="Other formats" id="oth-2503.21672" aria-labelledby="oth-2503.21672">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Avoider-Enforcer game on hypergraphs of rank 3 </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Galliot,+F">Florian Galliot</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Gledel,+V">Valentin Gledel</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Parreau,+A">Aline Parreau</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 the Avoider-Enforcer convention of positional games, two players, Avoider and Enforcer, take turns selecting vertices from a hypergraph H. Enforcer wins if, by the time all vertices of H have been selected, Avoider has completely filled an edge of H with her vertices; otherwise, Avoider wins. In this paper, we first give some general results, in particular regarding the outcome of the game and disjoint unions of hypergraphs. We then determine which player has a winning strategy for all hypergraphs of rank 2, and for linear hypergraphs of rank 3 when Avoider plays the last move. The structural characterisations we obtain yield polynomial-time algorithms. </p> </div> </dd> <dt> <a name='item13'>[13]</a> <a href ="/abs/2503.21752" title="Abstract" id="2503.21752"> arXiv:2503.21752 </a> [<a href="/pdf/2503.21752" title="Download PDF" id="pdf-2503.21752" aria-labelledby="pdf-2503.21752">pdf</a>, <a href="/format/2503.21752" title="Other formats" id="oth-2503.21752" aria-labelledby="oth-2503.21752">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Hypergraphic zonotopes and acyclohedra </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Pohoata,+C">Cosmin Pohoata</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Zhu,+D+G">Daniel G. Zhu</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 7 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> We introduce a higher-uniformity analogue of graphic zonotopes and permutohedra. Specifically, given a $(d+1)$-uniform hypergraph $H$, we define its hypergraphic zonotope $\mathcal{Z}_H$, and when $H$ is the complete $(d+1)$-uniform hypergraph $K^{(d+1)}_n$, we call its hypergraphic zonotope the acyclohedron $\mathcal{A}_{n,d}$. <br>We express the volume of $\mathcal{Z}_H$ as a homologically weighted count of the spanning $d$-dimensional hypertrees of $H$, which is closely related to Kalai's generalization of Cayley's theorem in the case when $H=K^{(d+1)}_n$ (but which, curiously, is not the same). We also relate the vertices of hypergraphic zonotopes to a notion of acyclic orientations previously studied by Linial and Morganstern for complete hypergraphs. </p> </div> </dd> </dl> <dl id='articles'> <h3>Cross submissions (showing 4 of 4 entries)</h3> <dt> <a name='item14'>[14]</a> <a href ="/abs/2503.21008" title="Abstract" id="2503.21008"> arXiv:2503.21008 </a> (cross-list from math.AC) [<a href="/pdf/2503.21008" title="Download PDF" id="pdf-2503.21008" aria-labelledby="pdf-2503.21008">pdf</a>, <a href="https://arxiv.org/html/2503.21008v1" title="View HTML" id="html-2503.21008" aria-labelledby="html-2503.21008" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21008" title="Other formats" id="oth-2503.21008" aria-labelledby="oth-2503.21008">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Density of linearity index in the interval of matching numbers </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Erey,+N">Nursel Erey</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Hibi,+T">Takayuki Hibi</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 7 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Commutative Algebra (math.AC)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> Given integers $2 \leq p \leq c \leq q$, we construct a finite simple graph $G$ with $\nu_1(G) = p$ and $\nu(G) = q$ for which the squarefree power $I(G)^{[k]}$ of the edge ideal $I(G)$ of $G$ has linear quotients for each $c \leq k \leq q$ and is not linearly related for each $1 \leq k < c$, where $\nu_1(G)$ is the induced matching number of $G$ and $\nu(G)$ is the matching number of $G$. </p> </div> </dd> <dt> <a name='item15'>[15]</a> <a href ="/abs/2503.21151" title="Abstract" id="2503.21151"> arXiv:2503.21151 </a> (cross-list from math.NT) [<a href="/pdf/2503.21151" title="Download PDF" id="pdf-2503.21151" aria-labelledby="pdf-2503.21151">pdf</a>, <a href="https://arxiv.org/html/2503.21151v1" title="View HTML" id="html-2503.21151" aria-labelledby="html-2503.21151" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21151" title="Other formats" id="oth-2503.21151" aria-labelledby="oth-2503.21151">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Hilbert-Kamke equations and geometric designs of degree five for classical orthogonal polynomials </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Mishima,+T">Teruyuki Mishima</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Lu,+X">Xiao-Nan Lu</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Sawa,+M">Masanori Sawa</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Uchida,+Y">Yukihiro Uchida</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 32 pages </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 elucidate the advantage of examining the connections between Hilbert-Kamke equations and geometric designs, or Chebyshev-type quadrature, for classical orthogonal polynomials. We first establish a classification theorem for such equations of degree 5 in 6 variables. The proof is based on an elementary polynomial identity, which Kawada and Wooley (1999) employed in their work on the Waring problem, and some advanced techniques on the computation of the genus of a certain irreducible curve. We then prove a necessary and sufficient condition for the existence of rational solutions of Hilbert-Kamke equations of degree 5, especially for the Chebyshev measure of the first kind. It is noteworthy that this result presents a completely explicit construction of rational solutions. Moreover, we create novel connections among Hilbert-Kamke equations, geometric designs and the Prouhet-Tarry-Escott (PTE) problem. For example, we establish that our solutions of Hilbert-Kamke equations of degree 5 in 6 variables appear in the famous parametric solution for the PTE problem found by Borwein (2002). </p> </div> </dd> <dt> <a name='item16'>[16]</a> <a href ="/abs/2503.21440" title="Abstract" id="2503.21440"> arXiv:2503.21440 </a> (cross-list from cs.CR) [<a href="/pdf/2503.21440" title="Download PDF" id="pdf-2503.21440" aria-labelledby="pdf-2503.21440">pdf</a>, <a href="https://arxiv.org/html/2503.21440v1" title="View HTML" id="html-2503.21440" aria-labelledby="html-2503.21440" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21440" title="Other formats" id="oth-2503.21440" aria-labelledby="oth-2503.21440">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the Maiorana-McFarland Class Extensions </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Kolomeec,+N">Nikolay Kolomeec</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Bykov,+D">Denis Bykov</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Cryptography and Security (cs.CR)</span>; Discrete Mathematics (cs.DM); Combinatorics (math.CO) </div> <p class='mathjax'> The closure $\mathcal{M}_{m}^{\#}$ and the extension $\widehat{\mathcal{M}}_{m}$ of the Maiorana--McFarland class $\mathcal{M}_{m}$ in $m = 2n$ variables relative to the extended-affine equivalence and the bent function construction $f \oplus \mathrm{Ind}_{U}$ are considered, where $U$ is an affine subspace of $\mathbb{F}_{2}^{m}$ of dimension $m/2$. We obtain an explicit formula for $|\widehat{\mathcal{M}}_{m}|$ and an upper bound for $|\widehat{\mathcal{M}}_{m}^{\#}|$. Asymptotically tight bounds for $|\mathcal{M}_{m}^{\#}|$ are proved as well, for instance, $|\mathcal{M}_{8}^{\#}| \approx 2^{77.865}$. Metric properties of $\mathcal{M}_{m}$ and $\mathcal{M}_{m}^{\#}$ are also investigated. We find the number of all closest bent functions to the set $\mathcal{M}_{m}$ and provide an upper bound of the same number for $\mathcal{M}_{m}^{\#}$. The average number $E(\mathcal{M}_{m})$ of $m/2$-dimensional affine subspaces of $\mathbb{F}_{2}^{m}$ such that a function from $\mathcal{M}_{m}$ is affine on each of them is calculated. We obtain that similarly defined $E(\mathcal{M}_{m}^{\#})$ satisfies $E(\mathcal{M}_{m}^{\#}) < E(\mathcal{M}_{m})$ and $E(\mathcal{M}_{m}^{\#}) = E(\mathcal{M}_{m}) - o(1)$. </p> </div> </dd> <dt> <a name='item17'>[17]</a> <a href ="/abs/2503.21682" title="Abstract" id="2503.21682"> arXiv:2503.21682 </a> (cross-list from math.NT) [<a href="/pdf/2503.21682" title="Download PDF" id="pdf-2503.21682" aria-labelledby="pdf-2503.21682">pdf</a>, <a href="https://arxiv.org/html/2503.21682v1" title="View HTML" id="html-2503.21682" aria-labelledby="html-2503.21682" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.21682" title="Other formats" id="oth-2503.21682" aria-labelledby="oth-2503.21682">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Twisted moments of characteristic polynomials of random matrices in the unitary group </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Baluyot,+S">Siegfred Baluyot</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Conrey,+B">Brian Conrey</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 24 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Number Theory (math.NT)</span>; Mathematical Physics (math-ph); Combinatorics (math.CO) </div> <p class='mathjax'> Recently, Keating and the second author of this paper devised a heuristic for predicting asymptotic formulas for moments of the Riemann zeta-function $\zeta(s)$. Their approach indicates how lower twisted moments of $\zeta(s)$ may be used to evaluate higher moments. In this paper, we present a rigorous random matrix theory analogue of their heuristic. To do this, we develop a notion of "twisted moment" of characteristic polynomials of matrices in the unitary group $U(N)$, and we prove several identities involving Schur polynomials. Our results may be viewed as a proof of concept of the heuristic for $\zeta(s)$. </p> </div> </dd> </dl> <dl id='articles'> <h3>Replacement submissions (showing 16 of 16 entries)</h3> <dt> <a name='item18'>[18]</a> <a href ="/abs/2311.10069" title="Abstract" id="2311.10069"> arXiv:2311.10069 </a> (replaced) [<a href="/pdf/2311.10069" title="Download PDF" id="pdf-2311.10069" aria-labelledby="pdf-2311.10069">pdf</a>, <a href="https://arxiv.org/html/2311.10069v4" title="View HTML" id="html-2311.10069" aria-labelledby="html-2311.10069" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2311.10069" title="Other formats" id="oth-2311.10069" aria-labelledby="oth-2311.10069">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The fractional chromatic number of the plane is at least 4 </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Matolcsi,+M">M谩t茅 Matolcsi</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Ruzsa,+I+Z">Imre Z. Ruzsa</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Varga,+D">D谩niel Varga</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Zs%C3%A1mboki,+P">P谩l Zs谩mboki</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Metric Geometry (math.MG) </div> <p class='mathjax'> We prove that the fractional chromatic number $\chi_f(\mathbb R^2)$ of the unit distance graph of the Euclidean plane is greater than or equal to $4$. Interestingly, however, we cannot present a finite subgraph $G$ of the plane such that $\chi_f(G)\ge 4$. Instead, we utilize the concept of the geometric fractional chromatic number $\chi_{gf}(G)$, which was introduced recently in connection with density bounds for 1-avoiding sets. <br>First, as $G$ ranges over finite subgraphs of the plane, we establish that the supremum of $\chi_f(G)$ is the same as that of $\chi_{gf}(G)$. The proof exploits the amenability of the group of Euclidean transformations in dimension 2 and, as such, we do not know whether the analogous statement holds in higher dimensions. We then present a specific planar unit distance graph $G$ on 27 vertices such that $\chi_{gf}(G)=4$, and conclude $\chi_f(\mathbb R^2)\ge 4$ as a corollary. <br>As another main result we show that the finitary fractional chromatic number and the Hall ratio of the plane are equal. As a consequence, we conclude that there exist finite unit distance graphs with independence ratio $\frac{1}{4}+\varepsilon$, while we conjecture that the value $\frac{1}{4}$ cannot be reached. </p> </div> </dd> <dt> <a name='item19'>[19]</a> <a href ="/abs/2405.05222" title="Abstract" id="2405.05222"> arXiv:2405.05222 </a> (replaced) [<a href="/pdf/2405.05222" title="Download PDF" id="pdf-2405.05222" aria-labelledby="pdf-2405.05222">pdf</a>, <a href="https://arxiv.org/html/2405.05222v2" title="View HTML" id="html-2405.05222" aria-labelledby="html-2405.05222" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2405.05222" title="Other formats" id="oth-2405.05222" aria-labelledby="oth-2405.05222">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Brooks-type colourings of digraphs in linear time </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Gon%C3%A7alves,+D">Daniel Gon莽alves</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Picasarri-Arrieta,+L">Lucas Picasarri-Arrieta</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Reinald,+A">Amadeus Reinald</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 26 pages, 5 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; Data Structures and Algorithms (cs.DS) </div> <p class='mathjax'> Brooks' Theorem is a fundamental result on graph colouring, stating that the chromatic number of a graph is almost always upper bounded by its maximal degree. Lov谩sz showed that such a colouring may then be computed in linear time when it exists. Many analogues are known for variants of (di)graph colouring, notably for list-colouring and partitions into subgraphs with prescribed degeneracy. One of the most general results of this kind is due to Borodin, Kostochka, and Toft, when asking for classes of colours to satisfy "variable degeneracy" constraints. An extension of this result to digraphs has recently been proposed by Bang-Jensen, Schweser, and Stiebitz, by considering colourings as partitions into "variable weakly degenerate" subdigraphs. Unlike earlier variants, there exists no linear-time algorithm to produce colourings for these generalisations. <br>We introduce the notion of (variable) bidegeneracy for digraphs, capturing multiple (di)graph degeneracy variants. We define the corresponding concept of $F$-dicolouring, where $F = (f_1,...,f_s)$ is a vector of functions, and an $F$-dicolouring requires vertices coloured $i$ to induce a "strictly-$f_i$-bidegenerate" subdigraph. We prove an analogue of Brooks' theorem for $F$-dicolouring, generalising the result of Bang-Jensen et al., and earlier analogues in turn. <br>Our new approach provides a linear-time algorithm that, given a digraph $D$, either produces an $F$-dicolouring of $D$, or correctly certifies that none exist. This yields the first linear-time algorithms to compute (di)colourings corresponding to the aforementioned generalisations of Brooks' theorem. In turn, it gives an unified framework to compute such colourings for various intermediate generalisations of Brooks' theorem such as list-(di)colouring and partitioning into (variable) degenerate sub(di)graphs. </p> </div> </dd> <dt> <a name='item20'>[20]</a> <a href ="/abs/2405.10088" title="Abstract" id="2405.10088"> arXiv:2405.10088 </a> (replaced) [<a href="/pdf/2405.10088" title="Download PDF" id="pdf-2405.10088" aria-labelledby="pdf-2405.10088">pdf</a>, <a href="https://arxiv.org/html/2405.10088v2" title="View HTML" id="html-2405.10088" aria-labelledby="html-2405.10088" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2405.10088" title="Other formats" id="oth-2405.10088" aria-labelledby="oth-2405.10088">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Vertex-transitive graphs with small motion and transitive permutation groups with small minimal degree </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Montero,+A">Antonio Montero</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Poto%C4%8Dnik,+P">Primo啪 Poto膷nik</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> The motion of a graph is the minimum number of vertices that are moved by a non-trivial automorphism. Equivalently, it can be defined as the minimal degree of its automorphism group (as a permutation group on the vertices). In this paper we develop some results on permutation groups (primitive and imprimitive) with small minimal degree. As a consequence of such results we classify vertex-transitive graphs whose motion is $4$ or a prime number. </p> </div> </dd> <dt> <a name='item21'>[21]</a> <a href ="/abs/2407.10576" title="Abstract" id="2407.10576"> arXiv:2407.10576 </a> (replaced) [<a href="/pdf/2407.10576" title="Download PDF" id="pdf-2407.10576" aria-labelledby="pdf-2407.10576">pdf</a>, <a href="https://arxiv.org/html/2407.10576v2" title="View HTML" id="html-2407.10576" aria-labelledby="html-2407.10576" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2407.10576" title="Other formats" id="oth-2407.10576" aria-labelledby="oth-2407.10576">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Vector spaces over finite commutative rings </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Guo,+J">Jun Guo</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Liu,+J">Junli Liu</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Xu,+Q">Qiuli Xu</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'> Vector spaces over finite fields and Anzahl formulas of subspaces were studied by Wan (Geometry of Classical Groups over Finite Fields, Science Press, 2002). As a generalization, we study vector spaces and singular linear spaces over commutative rings, and obtain some Anzahl formulas and dimensional formula for subspaces. Moreover, we discuss arcs and caps by using these subspaces. </p> </div> </dd> <dt> <a name='item22'>[22]</a> <a href ="/abs/2408.16318" title="Abstract" id="2408.16318"> arXiv:2408.16318 </a> (replaced) [<a href="/pdf/2408.16318" title="Download PDF" id="pdf-2408.16318" aria-labelledby="pdf-2408.16318">pdf</a>, <a href="https://arxiv.org/html/2408.16318v2" title="View HTML" id="html-2408.16318" aria-labelledby="html-2408.16318" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2408.16318" title="Other formats" id="oth-2408.16318" aria-labelledby="oth-2408.16318">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Quaternary Legendre pairs II </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Kotsireas,+I+S">Ilias S. Kotsireas</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Koutschan,+C">Christoph Koutschan</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Winterhof,+A">Arne Winterhof</a></div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Discrete Mathematics 348(9), Article 114501, 2025 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> Quaternary Legendre pairs are pertinent to the construction of quaternary Hadamard matrices and have many applications, for example in coding theory and communications. In contrast to binary Legendre pairs, quaternary ones can exist for even length $\ell$ as well. It is conjectured that there is a quaternary Legendre pair for any even $\ell$. The smallest open case until now had been $\ell=28$, and $\ell=38$ was the only length $\ell$ with $28\le \ell\le 60$ resolved before. Here we provide constructions for $\ell=28,30,32$, and $34$. In parallel and independently, Jedwab and Pender found a construction of quaternary Legendre pairs of length $\ell=(q-1)/2$ for any prime power $q\equiv 1\bmod 4$, which in particular covers $\ell=30$, $36$, and $40$, so that now $\ell=42$ is the smallest unresolved case. The main new idea of this paper is a way to separate the search for the subsequences along even and odd indices which substantially reduces the complexity of the search algorithm. In addition, we use Galois theory for cyclotomic fields to derive conditions which improve the PSD test. </p> </div> </dd> <dt> <a name='item23'>[23]</a> <a href ="/abs/2410.06156" title="Abstract" id="2410.06156"> arXiv:2410.06156 </a> (replaced) [<a href="/pdf/2410.06156" title="Download PDF" id="pdf-2410.06156" aria-labelledby="pdf-2410.06156">pdf</a>, <a href="https://arxiv.org/html/2410.06156v2" title="View HTML" id="html-2410.06156" aria-labelledby="html-2410.06156" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2410.06156" title="Other formats" id="oth-2410.06156" aria-labelledby="oth-2410.06156">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Linear dependencies, polynomial factors in the Duke--Erd\H os forbidden sunflower problem </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Kupavskii,+A">Andrey Kupavskii</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Noskov,+F">Fedor Noskov</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> We call a family of $s$ sets $\{F_1, \ldots, F_s\}$ a \textit{sunflower with $s$ petals} if, for any distinct $i, j \in [s]$, one has $F_i \cap F_j = \cap_{u = 1}^s F_u$. The set $C = \cap_{u = 1}^s F_u$ is called the {\it core} of the sunflower. It is a classical result of Erd\H os and Rado that there is a function $\phi(s,k)$ such that any family of $k$-element sets contains a sunflower with $s$ petals. In 1977, Duke and Erd\H os asked for the size of the largest family $\mathcal{F}\subset{[n]\choose k}$ that contains no sunflower with $s$ petals and core of size $t-1$. In 1987, Frankl and F\" uredi asymptotically solved this problem for $k\ge 2t+1$ and $n>n_0(s,k)$. This paper is one of the pinnacles of the so-called Delta-system method. <br>In this paper, we extend the result of Frankl and F眉redi to a much broader range of parameters: $n>f_0(s,t) k$ with $f_0(s,t)$ polynomial in $s$ and $t$. We also extend this result to other domains, such as $[n]^k$ and ${n\choose k/w}^w$ and obtain even stronger and more general results for forbidden sunflowers with core at most $t-1$ (including results for families of permutations and subfamilies of the $k$-th layer in a simplicial complex). <br>The methods of the paper, among other things, combine the spread approximation technique, introduced by Zakharov and the first author, with the Delta-system approach of Frankl and F眉redi and the hypercontractivity approach for global functions, developed by Keller, Lifshitz and coauthors. Previous works in extremal set theory relied on at most one of these methods. Creating such a unified approach was one of the goals for the paper. </p> </div> </dd> <dt> <a name='item24'>[24]</a> <a href ="/abs/2412.15170" title="Abstract" id="2412.15170"> arXiv:2412.15170 </a> (replaced) [<a href="/pdf/2412.15170" title="Download PDF" id="pdf-2412.15170" aria-labelledby="pdf-2412.15170">pdf</a>, <a href="https://arxiv.org/html/2412.15170v2" title="View HTML" id="html-2412.15170" aria-labelledby="html-2412.15170" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2412.15170" title="Other formats" id="oth-2412.15170" aria-labelledby="oth-2412.15170">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Induced arithmetic removal for partition-regular patterns of complexity 1 </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Gladkova,+V">V. Gladkova</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> In 2019, Fox, Tidor and Zhao (<a href="https://arxiv.org/abs/1911.03427" data-arxiv-id="1911.03427" class="link-https">arXiv:1911.03427</a>) proved an induced arithmetic removal lemma for linear patterns of complexity 1 in vector spaces over a fixed finite field. With no further assumptions on the pattern, this induced removal lemma cannot guarantee a fully pattern-free recolouring of the space, as some `non-generic' instances must necessarily remain. On the other hand, Bhattacharyya et al. (<a href="https://arxiv.org/abs/1212.3849" data-arxiv-id="1212.3849" class="link-https">arXiv:1212.3849</a>) showed that in the case of translation-invariant patterns, it is possible to obtain recolourings that eliminate the given pattern completely, with no exceptions left behind. This paper demonstrates that such complete removal can be achieved for all partition-regular arithmetic patterns of complexity 1. </p> </div> </dd> <dt> <a name='item25'>[25]</a> <a href ="/abs/2501.14691" title="Abstract" id="2501.14691"> arXiv:2501.14691 </a> (replaced) [<a href="/pdf/2501.14691" title="Download PDF" id="pdf-2501.14691" aria-labelledby="pdf-2501.14691">pdf</a>, <a href="https://arxiv.org/html/2501.14691v2" title="View HTML" id="html-2501.14691" aria-labelledby="html-2501.14691" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2501.14691" title="Other formats" id="oth-2501.14691" aria-labelledby="oth-2501.14691">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Stability of products of double Grothendieck polynomials </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Hardt,+A">Andrew Hardt</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Wallach,+D">David Wallach</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 14 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> We prove that products of double Grothendieck polynomials have the same back- and forward-stability numbers as products of Schubert polynomials, characterize which simple reflections appear in such products, and also give a new proof of a finiteness conjecture of Lam-Lee-Shimozono on products of back-stable Grothendieck polynomials which was first proved by Anderson. To do this, we use the main theorems from our recent work, as well as expansion formulas of Lenart, Fomin-Kirillov, and Lam-Lee-Shimozono. </p> </div> </dd> <dt> <a name='item26'>[26]</a> <a href ="/abs/2502.15394" title="Abstract" id="2502.15394"> arXiv:2502.15394 </a> (replaced) [<a href="/pdf/2502.15394" title="Download PDF" id="pdf-2502.15394" aria-labelledby="pdf-2502.15394">pdf</a>, <a href="https://arxiv.org/html/2502.15394v2" title="View HTML" id="html-2502.15394" aria-labelledby="html-2502.15394" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2502.15394" title="Other formats" id="oth-2502.15394" aria-labelledby="oth-2502.15394">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On generic $螖$-modular integer matrices with two rows </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Kriepke,+B">Bj枚rn Kriepke</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Schymura,+M">Matthias Schymura</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 27 pages, 1 figure, added application to matroids </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span> </div> <p class='mathjax'> The column number question asks for the maximal number of columns of an integer matrix with the property that all its rank size minors are bounded by a fixed parameter $\Delta$ in absolute value. Polynomial upper bounds have been proved in various settings in recent years, with consequences for algorithmic questions in integer linear programming and matroid theory. In this paper, we focus on the exact determination of the maximal column number of such matrices with two rows and no vanishing $2$-minors. We prove that for large enough $\Delta$, this number is a quasi-linear function, non-decreasing and always even. Such basic structural properties of column number functions are barely known, but expected to hold in other settings as well. Moreover, our results identify the unique excluded (co)rank two minors for the class of matroids that are representable as a $\Delta$-submodular matrix. </p> </div> </dd> <dt> <a name='item27'>[27]</a> <a href ="/abs/2503.18615" title="Abstract" id="2503.18615"> arXiv:2503.18615 </a> (replaced) [<a href="/pdf/2503.18615" title="Download PDF" id="pdf-2503.18615" aria-labelledby="pdf-2503.18615">pdf</a>, <a href="https://arxiv.org/html/2503.18615v2" title="View HTML" id="html-2503.18615" aria-labelledby="html-2503.18615" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2503.18615" title="Other formats" id="oth-2503.18615" aria-labelledby="oth-2503.18615">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Scales, products and the second row of the Scheepers diagram </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Pawlikowski,+M">Micha艂 Pawlikowski</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Szewczak,+P">Piotr Szewczak</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Zdomskyy,+L">Lyubomyr Zdomskyy</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 23 pp </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Combinatorics (math.CO)</span>; General Topology (math.GN) </div> <p class='mathjax'> We consider products of sets of reals with a combinatorial structure based on scales parameterized by filters. This kind of sets were intensively investigated in products of spaces with combinatorial covering properties as Hurewicz, Scheepers, Menger and Rothberger. We will complete this picture with focusing on properties from the second row of the Scheepers diagram. In particular we show that in the Miller model a product space of two $\mathfrak{d}$-concentrated sets has a strong covering property $\mathsf{S}_1(\Gamma,\Omega)$. We provide also counterexamples in products to demonstrate limitations of used methods. </p> </div> </dd> <dt> <a name='item28'>[28]</a> <a href ="/abs/2210.09771" title="Abstract" id="2210.09771"> arXiv:2210.09771 </a> (replaced) [<a href="/pdf/2210.09771" title="Download PDF" id="pdf-2210.09771" aria-labelledby="pdf-2210.09771">pdf</a>, <a href="https://arxiv.org/html/2210.09771v3" title="View HTML" id="html-2210.09771" aria-labelledby="html-2210.09771" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2210.09771" title="Other formats" id="oth-2210.09771" aria-labelledby="oth-2210.09771">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Weighted simple games and the topology of simplicial complexes </div> <div class='list-authors'><a href="https://arxiv.org/search/physics?searchtype=author&query=Brooks,+A">Anastasia Brooks</a>, <a href="https://arxiv.org/search/physics?searchtype=author&query=Sarcevic,+F">Franjo Sarcevic</a>, <a href="https://arxiv.org/search/physics?searchtype=author&query=Volic,+I">Ismar Volic</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 27 pages, 5 figures, 4 tables </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Physics and Society (physics.soc-ph)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> We use simplicial complexes to model simple games as well as weighted voting games where certain coalitions are considered impossible. Topological characterizations of various ideas from simple games are provided, as are the expressions for Banzhaf and Shapley-Shubik power indices for weighted games. We calculate the indices in several examples of weighted voting games with unfeasible coalitions, including the U.S. Electoral College and the Parliament of Bosnia-Herzegovina. </p> </div> </dd> <dt> <a name='item29'>[29]</a> <a href ="/abs/2312.02574" title="Abstract" id="2312.02574"> arXiv:2312.02574 </a> (replaced) [<a href="/pdf/2312.02574" title="Download PDF" id="pdf-2312.02574" aria-labelledby="pdf-2312.02574">pdf</a>, <a href="/format/2312.02574" title="Other formats" id="oth-2312.02574" aria-labelledby="oth-2312.02574">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Intersection multiplicity one for the Belkale-Kumar product in G/B </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Ressayre,+N">Nicolas Ressayre</a> (ICJ, AGL, UCBL), <a href="https://arxiv.org/search/math?searchtype=author&query=Francone,+L">Luca Francone</a> (ICJ, UCBL, AGL)</div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Algebraic Geometry (math.AG)</span>; Combinatorics (math.CO); Representation Theory (math.RT) </div> <p class='mathjax'> Consider the complete flag variety $X$ of a complex semisimple algebraic group $G$. We show that the structure coefficients of the Belkale-Kumar product $\odot_0$, on the cohomology $\mathrm{H}^{*}(X,\mathbf{Z})$, are all either $0$ or $1$. We also derive some consequences. The proof that is mainly geometric also uses new combinatorial results on root systems. Moreover, it is uniform and avoids case by case considerations. </p> </div> </dd> <dt> <a name='item30'>[30]</a> <a href ="/abs/2401.14605" title="Abstract" id="2401.14605"> arXiv:2401.14605 </a> (replaced) [<a href="/pdf/2401.14605" title="Download PDF" id="pdf-2401.14605" aria-labelledby="pdf-2401.14605">pdf</a>, <a href="https://arxiv.org/html/2401.14605v2" title="View HTML" id="html-2401.14605" aria-labelledby="html-2401.14605" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2401.14605" title="Other formats" id="oth-2401.14605" aria-labelledby="oth-2401.14605">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Borel Ramsey properties for countable Borel equivalence relations </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Gao,+S">Su Gao</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Xiao,+M">Ming Xiao</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Logic (math.LO)</span>; Combinatorics (math.CO) </div> <p class='mathjax'> We define some natural notions of strong and weak Borel Ramsey properties for countable Borel equivalence relations and show that they hold for a countable Borel equivalence relation if and only if the equivalence relation is smooth. We also consider some variation of the notion for hyperfinite non-smooth Borel equivalence relations. </p> </div> </dd> <dt> <a name='item31'>[31]</a> <a href ="/abs/2405.10809" title="Abstract" id="2405.10809"> arXiv:2405.10809 </a> (replaced) [<a href="/pdf/2405.10809" title="Download PDF" id="pdf-2405.10809" aria-labelledby="pdf-2405.10809">pdf</a>, <a href="https://arxiv.org/html/2405.10809v3" title="View HTML" id="html-2405.10809" aria-labelledby="html-2405.10809" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2405.10809" title="Other formats" id="oth-2405.10809" aria-labelledby="oth-2405.10809">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Framization and Deframization </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Aicardi,+F">Francesca Aicardi</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Juyumaya,+J">Jes煤s Juyumaya</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Papi,+P">Paolo Papi</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Latex file, 41 pages, revision version </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Rings and Algebras (math.RA)</span>; Combinatorics (math.CO); General Topology (math.GN) </div> <p class='mathjax'> Starting from the geometric construction of the framed braid group, we define and study the framization of several Brauer-type monoids and also the set partition monoid, all of which appear in knot theory. We introduce the concept of deframization, which is a procedure to obtain a tied monoid from a given framed monoid. Furthermore, we show in detail how this procedure works on the monoids mentioned above. We also discuss the framization and deframization of some algebras, which are deformations, respectively, of the framized and deframized monoids discussed here. </p> </div> </dd> <dt> <a name='item32'>[32]</a> <a href ="/abs/2410.17887" title="Abstract" id="2410.17887"> arXiv:2410.17887 </a> (replaced) [<a href="/pdf/2410.17887" title="Download PDF" id="pdf-2410.17887" aria-labelledby="pdf-2410.17887">pdf</a>, <a href="https://arxiv.org/html/2410.17887v2" title="View HTML" id="html-2410.17887" aria-labelledby="html-2410.17887" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2410.17887" title="Other formats" id="oth-2410.17887" aria-labelledby="oth-2410.17887">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Average-case matrix discrepancy: satisfiability bounds </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Maillard,+A">Antoine Maillard</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 37 pages, 2 figures ; v2: corrections of small typos and error estimates, move of parts of the proof of the first moment method to appendix, and addition of the failure of the second moment method </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Probability (math.PR)</span>; Disordered Systems and Neural Networks (cond-mat.dis-nn); Discrete Mathematics (cs.DM); Combinatorics (math.CO) </div> <p class='mathjax'> Given a sequence of $d \times d$ symmetric matrices $\{\mathbf{W}_i\}_{i=1}^n$, and a margin $\Delta > 0$, we investigate whether it is possible to find signs $(\epsilon_1, \dots, \epsilon_n) \in \{\pm 1\}^n$ such that the operator norm of the signed sum satisfies $\|\sum_{i=1}^n \epsilon_i \mathbf{W}_i\|_{\rm op} \leq \Delta$. Kunisky and Zhang (2023) recently introduced a random version of this problem, where the matrices $\{\mathbf{W}_i\}_{i=1}^n$ are drawn from the Gaussian orthogonal ensemble. This model can be seen as a random variant of the celebrated Matrix Spencer conjecture and as a matrix-valued analog of the symmetric binary perceptron in statistical physics. In this work, we establish a satisfiability transition in this problem as $n, d \to \infty$ with $n / d^2 \to \tau > 0$. First, we prove that the expected number of solutions with margin $\Delta=\kappa \sqrt{n}$ has a sharp threshold at a critical $\tau_1(\kappa)$: for $\tau < \tau_1(\kappa)$ the problem is typically unsatisfiable, while for $\tau > \tau_1(\kappa)$ the average number of solutions is exponentially large. Second, combining a second-moment method with recent results from Altschuler (2023) on margin concentration in perceptron-type problems, we identify a second threshold $\tau_2(\kappa)$, such that for $\tau>\tau_2(\kappa)$ the problem admits solutions with high probability. In particular, we establish that a system of $n = \Theta(d^2)$ Gaussian random matrices can be balanced so that the spectrum of the resulting matrix macroscopically shrinks compared to the semicircle law. Finally, under a technical assumption, we show that there exists values of $(\tau,\kappa)$ for which the number of solutions has large variance, implying the failure of the second moment method. Our proofs rely on establishing concentration and large deviation properties of correlated Gaussian matrices under spectral norm constraints. </p> </div> </dd> <dt> <a name='item33'>[33]</a> <a href ="/abs/2502.05655" title="Abstract" id="2502.05655"> arXiv:2502.05655 </a> (replaced) [<a href="/pdf/2502.05655" title="Download PDF" id="pdf-2502.05655" aria-labelledby="pdf-2502.05655">pdf</a>, <a href="/format/2502.05655" title="Other formats" id="oth-2502.05655" aria-labelledby="oth-2502.05655">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Folded Gentle Algebras </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Duffield,+D+D">Drew Damien Duffield</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 58 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Representation Theory (math.RT)</span>; Combinatorics (math.CO); Rings and Algebras (math.RA) </div> <p class='mathjax'> We use folding techniques to define a new class of gentle-like algebras that generalise the iterated tilted algebras of type $C$ and $\widetilde{C}$, which we call folded gentle algebras. We then show that folded gentle algebras satisfy many of the same remarkable properties of gentle algebras, and that the proof of these properties follows directly from folding arguments. In particular, we classify the indecomposable modules of folded gentle algebras in terms symmetric and asymmetric string and band modules. We classify the Auslander-Reiten sequences over these algebras, showing that irreducible morphisms between string modules are given by adding/deleting hooks and cohooks to/from strings. Finally, we show that the class of folded gentle algebras are closed under derived equivalence. </p> </div> </dd> </dl> <div class='paging'>Total of 33 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