http://www.rssboard.org/rss-specification720Recent combinatorial_theory items
https://escholarship.org/uc/combinatorial_theory/rss
Recent eScholarship items from Combinatorial TheoryThu, 8 Aug 2024 20:18:19 -0700On quasi-polynomials counting planar tight maps
https://escholarship.org/uc/item/9h946160
<p>A tight map is a map with some of its vertices marked, such that every vertex of degree \(1\) is marked. We give an explicit formula for the number \(N_{0,n}(d_1,\ldots,d_n)\) of planar tight maps with \(n\) labeled faces of prescribed degrees \(d_1,\ldots,d_n\), where a marked vertex is seen as a face of degree \(0\). It is a quasi-polynomial in \((d_1,\ldots,d_n)\), as shown previously by Norbury. Our derivation is bijective and based on the slice decomposition of planar maps. In the non-bipartite case, we also rely on enumeration results for two-type forests. We discuss the connection with the enumeration of non necessarily tight maps. In particular, we provide a generalization of Tutte's classical slicings formula to all non-bipartite maps.</p><p>Mathematics Subject Classifications: 05A15, 05A19</p><p>Keywords: Planar maps, bijective enumeration, slice decomposition</p>https://escholarship.org/uc/item/9h946160Mon, 1 Jul 2024 00:00:00 +0000Bouttier, JérémieGuitter, EmmanuelMiermont, GrégoryIntervals in the greedy Tamari posets
https://escholarship.org/uc/item/9342r6p5
<p>We consider a greedy version of the \(m\)-Tamari order defined on \(m\)-Dyck paths, recently introduced by Dermenjian. Inspired by intriguing connections between intervals in the ordinary {1-}Tamari order and planar triangulations, and more generally by the existence of simple formulas counting intervals in the ordinary \(m\)-Tamari orders, we investigate the number of intervals in the greedy order on \(m\)-Dyck paths of fixed size. We find again a simple formula, which also counts certain planar maps (of prescribed size) called \((m+1)\)-constellations.</p><p>For instance, when \(m=1\) the number of intervals in the greedy order on {1-}Dyck paths of length \(2n\) is proved to be \(\frac{3\cdot 2^{n-1}}{(n+1)(n+2)} \binom{2n}{n}\), which is also the number of bipartite maps with \(n\) edges.</p><p>Our approach is recursive, and uses a "catalytic" parameter, namely the length of the final descent of the upper path of the interval. The resulting bivariate generating function...https://escholarship.org/uc/item/9342r6p5Mon, 1 Jul 2024 00:00:00 +0000Bousquet-Mélou, MireilleChapoton, FrédéricShort proofs of three results about intersecting systems
https://escholarship.org/uc/item/8ph5f0p8
<p>In this note, we give short proofs of three theorems about intersection problems. The first one is a determination of the maximum size of a nontrivial \(k\)-uniform, \(d\)-wise intersecting family for \(n\ge \left(1+\frac{d}{2}\right)(k-d+2)\), which improves the range of \(n\) of a recent result of O'Neill and Verstraëte. Our proof also extends to \(d\)-wise, \(t\)-intersecting families, and from this result we obtain a version of the Erdős-Ko-Rado theorem for \(d\)-wise, \(t\)-intersecting families.</p><p>Our second result partially proves a conjecture of Frankl and Tokushige about \(k\)-uniform families with restricted pairwise intersection sizes.</p><p>Our third result is about intersecting families of graphs. Answering a question of Ellis, we construct \(K_{s, t}\)-intersecting families of graphs which have size larger than the Erdős-Ko-Rado-type construction, whenever \(t\) is sufficiently large in terms of \(s\). The construction is based on nontrivial \((2s)\)-wise...https://escholarship.org/uc/item/8ph5f0p8Mon, 1 Jul 2024 00:00:00 +0000Balogh, JózsefLinz, WilliamSets of mutually orthogoval projective and affine planes
https://escholarship.org/uc/item/6q20z7sg
<p>A pair of planes, both projective or both affine, of the same order and on the same point set are orthogoval if each line of one plane intersects each line of the other plane in at most two points. In this paper we prove new constructions for sets of mutually orthogoval planes, both projective and affine, and review known results that are equivalent to sets of more than two mutually orthogoval planes. We also discuss the connection between sets of mutually orthogoval planes and covering arrays.</p><p>Mathematics Subject Classifications: 05B25, 05B40, 51E20, 51E21</p><p>Keywords: Finite geometry, projective planes, affine planes, covering arrays, orthogoval planes</p>https://escholarship.org/uc/item/6q20z7sgMon, 1 Jul 2024 00:00:00 +0000Colbourn, Charles J.Ingalls, ColinJedwab, JonathanSaaltink, MarkSmith, Ken W.Stevens, BrettCounting conjugacy classes of elements of finite order in exceptional Lie groups
https://escholarship.org/uc/item/68q5g0vj
<p>This paper continues the study of two numbers that are associated with Lie groups. The first number is \(N(G,m)\), the number of conjugacy classes of elements in \(G\) whose order divides \(m\). The second number is \(N(G,m,s)\), the number of conjugacy classes of elements in \(G\) whose order divides \(m\) and which have \(s\) distinct eigenvalues, where we view \(G\) as a matrix group in its smallest-degree faithful representation. We describe systematic algorithms for computing both numbers for \(G\) a connected and simply-connected exceptional Lie group. We also provide explicit results for all of \(N(G,m)\), \(N(G_2,m,s)\), and \(N(F_4,m,s)\). The numbers \(N(G,m,s)\) were previously known only for the classical Lie groups; our results for \(N(G,m)\) agree with those already in the literature but are obtained differently.</p><p>Mathematics Subject Classifications: 05A15, 05E16, 22E40, 22E10, 22E15</p><p>Keywords: Lie groups, conjugacy classes, element of finite order,...https://escholarship.org/uc/item/68q5g0vjMon, 1 Jul 2024 00:00:00 +0000Friedmann, TamarHe, QidongThe spectral even cycle problem
https://escholarship.org/uc/item/64r017cx
<p>In this paper, we study the maximum adjacency spectral radii of graphs of large order that do not contain an even cycle of given length. For \(n›k\), let \(S_{n,k}\) be the join of a clique on \(k\) vertices with an independent set of \(n-k\) vertices and denote by \(S_{n,k}^+\) the graph obtained from \(S_{n,k}\) by adding one edge. In 2010, Nikiforov conjectured that for \(n\) large enough, the \(C_{2k+2}\)-free graph of maximum spectral radius is \(S_{n,k}^+\) and that the \(\{C_{2k+1},C_{2k+2}\}\)-free graph of maximum spectral radius is \(S_{n,k}\). We solve this two-part conjecture.</p><p>Mathematics Subject Classifications: 05C35, 05C50</p><p>Keywords: Spectral Turán number, even-cycle problem, Brualdi-Solheid problem</p>https://escholarship.org/uc/item/64r017cxMon, 1 Jul 2024 00:00:00 +0000Cioab, SebastianDesai, Dheer NoalTait, MichaelRowmotion on \(m\)-Tamari and biCambrian lattices
https://escholarship.org/uc/item/5x945586
<p>Thomas and Williams conjectured that rowmotion acting on the rational \((a,b)\)-Tamari lattice has order \(a+b-1\). We construct an equivariant bijection that proves this conjecture when \(a\equiv 1\pmod b\); in fact, we determine the entire orbit structure of rowmotion in this case, showing that it exhibits the cyclic sieving phenomenon. We additionally show that the down-degree statistic is homomesic for this action. In a different vein, we consider the action of rowmotion on Barnard and Reading's biCambrian lattices. Settling a different conjecture of Thomas and Williams, we prove that if \(c\) is a bipartite Coxeter element of a coincidental-type Coxeter group \(W\), then the orbit structure of rowmotion on the \(c\)-biCambrian lattice is the same as the orbit structure of rowmotion on the lattice of order ideals of the doubled root poset of type \(W\).</p><p>Mathematics Subject Classifications: 05E18, 06B10, 06D75</p><p>Keywords: Rowmotion, \(m\)-Tamari lattice, biCambrian...https://escholarship.org/uc/item/5x945586Mon, 1 Jul 2024 00:00:00 +0000Defant, ColinLin, JamesGeneralized recursive atom ordering and equivalence to CL-shellability
https://escholarship.org/uc/item/5242n3vj
<p>Björner and Wachs introduced CL-shellability as a technique for studying the topological structure of order complexes of partially ordered sets. They also introduced the notion of recursive atom ordering, and they proved that a finite bounded poset is CL-shellable if and only if it admits a recursive atom ordering.</p><p>In this paper, a generalization of the notion of recursive atom ordering is introduced. A finite bounded poset is proven to admit such a generalized recursive atom ordering if and only if it admits a traditional recursive atom ordering. This is also proven equivalent to admitting a CC-shelling (a type of shelling introduced by Kozlov) with a further property called self-consistency. Thus, CL-shellability is proven equivalent to self-consistent CC-shellability. As an application, the uncrossing posets, namely the face posets for stratified spaces of planar electrical networks, are proven to be dual CL-shellable.</p><p>Mathematics Subject Classifications: 05E45,...https://escholarship.org/uc/item/5242n3vjMon, 1 Jul 2024 00:00:00 +0000Hersh, PatriciaStadnyk, GraceOn the size of maximal binary codes with 2, 3, and 4 distances
https://escholarship.org/uc/item/3th2g2bk
<p>We address the maximum size of binary codes and binary constant weight codes with few distances. Previous works established a number of bounds for these quantities as well as the exact values for a range of small code lengths. As our main results, we determine the exact size of maximal binary codes with two distances for all lengths \(n\ge 6\) as well as the exact size of maximal binary constant weight codes with \(2\), \(3\), and \(4\) distances for several values of the weight and for all but small lengths.</p><p>Mathematics Subject Classifications: 52C10, 05D05, 94B65</p><p>Keywords: Johnson space, Erdös-Ko-Rado, Delsarte inequalities</p>https://escholarship.org/uc/item/3th2g2bkMon, 1 Jul 2024 00:00:00 +0000Barg, AlexanderGlazyrin, AlexeyKao, Wei-JiunLai, Ching-YiTseng, Pin-ChiehYu, Wei-HsuanA criterion for sharpness in tree enumeration and the asymptotic number of triangulations in Kuperberg's \(G_2\) spider
https://escholarship.org/uc/item/3t4812dw
<p>We prove a conjectured asymptotic formula of Kuperberg from the representation theory of the Lie algebra \(G_2\). Given two non-negative integer sequences \((a_n)_{n\geq 0}\) and \((b_n)_{n\geq 0}\), with \(a_0=b_0=1\), it is well-known that if the identity \(B(x)=A(xB(x))\) holds for the generating functions \(A(x)=1+\sum_{n\geq 1} a_n x^n\) and \(B(x)=1+\sum_{n\geq 1} b_n x^n\), then \(b_n\) is the number of rooted planar trees with \(n+1\) vertices such that each vertex having \(i\) children may be colored with any one of \(a_i\) distinct colors. Kuperberg proved a specific case when this identity holds, namely when \(b_n=\dim \operatorname{Inv}_{G_2} (V(\lambda_1)^{\otimes n})\), where \(V(\lambda_1)\) is the 7-dimensional fundamental representation of \(G_2\), and \(a_n\) is the number of triangulations of a regular \(n\)-gon such that each internal vertex has degree at least \(6\). He also observed that \(\limsup_{n\to\infty}\sqrt[n]{a_n}\leq 7/B(1/7)\) and conjectured...https://escholarship.org/uc/item/3t4812dwMon, 1 Jul 2024 00:00:00 +0000Scherer, RobertAn aperiodic monotile
https://escholarship.org/uc/item/3317z9z9
<p>A longstanding open problem asks for an aperiodic monotile, also known as an "einstein": a shape that admits tilings of the plane, but never periodic tilings. We answer this problem for topological disk tiles by exhibiting a continuum of combinatorially equivalent aperiodic polygons. We first show that a representative example, the "hat" polykite, can form clusters called "metatiles", for which substitution rules can be defined. Because the metatiles admit tilings of the plane, so too does the hat. We then prove that generic members of our continuum of polygons are aperiodic, through a new kind of geometric incommensurability argument. Separately, we give a combinatorial, computer-assisted proof that the hat must form hierarchical--and hence aperiodic--tilings.</p><p>Mathematics Subject Classifications: 05B45, 52C20, 05B50</p><p>Keywords: Tilings, aperiodic order, polyforms</p>https://escholarship.org/uc/item/3317z9z9Mon, 1 Jul 2024 00:00:00 +0000Smith, DavidMyers, Joseph SamuelKaplan, Craig S.Goodman-Strauss, ChaimResilience for tight Hamiltonicity
https://escholarship.org/uc/item/2x43q0st
<p>We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any \(\gamma›0\) and \(k\ge3\), we show that asymptotically almost surely, every subgraph of the binomial random \(k\)-uniform hypergraph \(G^{(k)}\big(n,n^{\gamma-1}\big)\) in which all \((k-1)\)-sets are contained in at least \(\big(\tfrac12+2\gamma\big)pn\) edges has a tight Hamilton cycle. This is a cyclic ordering of the \(n\) vertices such that each consecutive \(k\) vertices forms an edge.</p><p>Mathematics Subject Classifications: 05C80, 05C35</p><p>Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience</p>https://escholarship.org/uc/item/2x43q0stMon, 1 Jul 2024 00:00:00 +0000Allen, PeterParczyk, OlafPfenninger, VincentExact antichain saturation numbers via a generalisation of a result of Lehman-Ron
https://escholarship.org/uc/item/2s4544d9
<p>For given positive integers \(k\) and \(n\), a family \(\mathcal{F}\) of subsets of \(\{1,\dots,n\}\) is \(k\)-antichain saturated if it does not contain an antichain of size \(k\), but adding any set to \(\mathcal{F}\) creates an antichain of size \(k\). We use sat\(^*(n, k)\) to denote the smallest size of such a family. For all \(k\) and sufficiently large \(n\), we determine the exact value of sat\(^*(n, k)\). Our result implies that sat\(^*(n, k)=n(k-1)-\Theta(k\log k)\), which confirms several conjectures on antichain saturation. Previously, exact values for sat\(^*(n,k)\) were only known for \(k\) up to \(6\).</p><p>We also prove a strengthening of a result of Lehman-Ron which may be of independent interest. We show that given \(m\) disjoint chains \(C^1,\dots,C^m\) in the Boolean lattice, we can create \(m\) disjoint skipless chains that cover the elements from \(\cup_{i=1}^mC^i\) (where we call a chain skipless if any two consecutive elements differ in size by exactly...https://escholarship.org/uc/item/2s4544d9Mon, 1 Jul 2024 00:00:00 +0000Bastide, PaulGroenland, CarlaJacob, HugoJohnston, TomThe primitive Eulerian polynomial
https://escholarship.org/uc/item/25m2v64h
<p>We introduce the primitive Eulerian polynomial \(P_{\mathcal{A}}(z)\) of a central hyperplane arrangement \(\mathcal{A}\). It is a reparametrization of its cocharacteristic polynomial. Previous work by the first author implicitly shows that for simplicial arrangements, \(P_{\mathcal{A}}(z)\) has nonnegative coefficients. For reflection arrangements of types A and B, the same work interprets the coefficients of \(P_{\mathcal{A}}(z)\) using the (flag) excedance statistic on (signed) permutations.</p><p>The main result of this article is to provide an interpretation of the coefficients of \(P_{\mathcal{A}}(z)\) for all simplicial arrangements using only the geometry and combinatorics of \(\mathcal{A}\). This new interpretation sheds more light to the case of reflection arrangements and, for the first time, gives combinatorial significance to the coefficients of the primitive Eulerian polynomial of the reflection arrangement of type D, for which no well-behaved excedance statistic...https://escholarship.org/uc/item/25m2v64hMon, 1 Jul 2024 00:00:00 +0000Bastidas, JoseHohlweg, ChristopheSaliola, FrancoRefining trees of tangles in abstract separation systems: inessential parts
https://escholarship.org/uc/item/0pt1052t
<p>Robertson and Seymour proved two fundamental theorems about tangles in graphs: the tree-of-tangles theorem, which says that every graph has a tree-decomposition such that distinguishable tangles live in different nodes of the tree, and the tangle-tree duality theorem, which says that graphs without a \(k\)-tangle have a tree-decomposition that witnesses the non-existence of such tangles, in that \(k\)-tangles would have to live in a node but no node is large enough to accommodate one.</p><p>Erde combined these two fundamental theorems into one, by constructing a single tree-decomposition such that every node either accommodates a single \(k\)-tangle or is too small to accommodate one. Such a tree-decomposition thus shows at a glance how many \(k\)-tangles a graph has and where they are.</p><p>The two fundamental theorems have since been extended to abstract separation systems, which support tangles in more general discrete structures. In this paper we extend Erde's unified...https://escholarship.org/uc/item/0pt1052tMon, 1 Jul 2024 00:00:00 +0000Albrechtsen, SandraDecompositions of packed words and self duality of Word Quasisymmetric Functions
https://escholarship.org/uc/item/80g252tm
<p>By Foissy's work, the bidendriform structure of the Word Quasisymmetric Functions Hopf algebra (WQSym) implies that it is isomorphic to its dual. However, the only known explicit isomorphism due to Vargas does not respect the bidendriform structure. This structure is entirely determined by so-called totally primitive elements (elements such that the two half-coproducts vanish). In this paper, we construct two bases indexed by two new combinatorial families called red (dual side) and blue (primal side) biplane forests in bijection with packed words. In those bases, primitive elements are indexed by biplane trees and totally primitive elements by a certain subset of trees. We carefully combine red and blue forests to get bicolored forests. A simple recoloring of the edges allows us to obtain the first explicit bidendriform automorphism of WQSym.</p><p>Mathematics Subject Classifications: 05A05, 05A19, 05E05, 05E18</p><p>Keywords: Bidendriform Hopf algebras, Word Quasisymmetric...https://escholarship.org/uc/item/80g252tmFri, 28 Jun 2024 00:00:00 +0000Mlodecki, HugoThe spine of the \(T\)-graph of the Hilbert scheme of points in the plane
https://escholarship.org/uc/item/74v009bx
<p>The torus \(T\) of projective space also acts on the Hilbert scheme of subschemes of projective space. The \(T\)-graph of the Hilbert scheme has vertices the fixed points of this action, and edges connecting pairs of fixed points in the closure of a one-dimensional orbit. In general this graph depends on the underlying field. We construct a subgraph, which we call the spine, of the \(T\)-graph of \(\operatorname{Hilb}^m(\mathbb A^2)\) that is independent of the choice of infinite field. For certain edges in the spine we also give a description of the tropical ideal, in the sense of tropical scheme theory, of a general ideal in the edge. This gives a more refined understanding of these edges, and of the tropical stratification of the Hilbert scheme.</p><p>Mathematics Subject Classifications: 14C05, 14T10, 14L30</p><p>Keywords: Hilbert scheme, \(T\)-graph, tropical ideal</p>https://escholarship.org/uc/item/74v009bxFri, 28 Jun 2024 00:00:00 +0000Maclagan, DianeSilversmith, RobColorful words and \(d\)-Tverberg complexes
https://escholarship.org/uc/item/3ff81565
<p>We give a complete combinatorial characterization of weakly \(d\)-Tverberg complexes. These complexes record which intersection combinatorics of convex hulls necessarily arise in any sufficiently large general position point set in \(\mathbb R^d\). This strengthens the concept of \(d\)-representable complexes, which describe intersection combinatorics that arise in at least one point set. Our characterization allows us to construct for every fixed \(d\) a graph that is not weakly \(d'\)-Tverberg for any \({d' \le d}\), answering a question of De Loera, Hogan, Oliveros, and Yang.</p><p>Mathematics Subject Classifications: 52A35, 52C45</p><p>Keywords: Tverberg's theorem, word representable, \(d\)-representable, nerve, general position, strong general position, fully independent</p>https://escholarship.org/uc/item/3ff81565Fri, 28 Jun 2024 00:00:00 +0000Frick, FlorianJeffs, R. AmziA symmetric function lift of torus link homology
https://escholarship.org/uc/item/9km9594f
<p>Suppose \(M\) and \(N\) are positive integers and let \(k = \gcd(M, N)\), \(m = M/k\), and \(n=N/k\). We define a symmetric function \(L_{M,N}\) as a weighted sum over certain tuples of lattice paths. We show that \(L_{M,N}\) satisfies a generalization of Hogancamp and Mellit's recursion for the triply-graded Khovanov-Rozansky homology of the \(M,N\)-torus link. As a corollary, we obtain the triply-graded Khovanov-Rozansky homology of the \(M,N\)-torus link as a specialization of \(L_{M,N}\). We conjecture that \(L_{M,N}\) is equal (up to a constant) to the elliptic Hall algebra operator \(\mathbf{Q}_{m,n}\) composed \(k\) times and applied to 1.</p><p>Mathematics Subject Classifications: 05E05, 57M27</p><p>Keywords: Lattice paths, Dyck paths, link homology, torus links, elliptic Hall algebra, LLT polynomials</p>https://escholarship.org/uc/item/9km9594fFri, 22 Dec 2023 00:00:00 +0000Wilson, AndyUnimodular covers of \(3\)-dimensional parallelepipeds and Cayley sums
https://escholarship.org/uc/item/82n2n71d
<p>We show that the following classes of lattice polytopes have unimodular covers, in dimension three: parallelepipeds, smooth centrally symmetric polytopes, and Cayley sums \(\operatorname{Cay}(P,Q)\) where the normal fan of \(Q\) refines that of \(P\). This improves results of Beck et al. (2018) and Haase et al. (2008) where the last two classes were shown to be IDP.</p><p>Mathematics Subject Classifications: 52B10, 52B20, 52C17</p><p>Keywords: Lattice polytopes, unimodular covers, integer decomposition property</p>https://escholarship.org/uc/item/82n2n71dFri, 22 Dec 2023 00:00:00 +0000Codenotti, GiuliaSantos, FranciscoCovering grids with multiplicity
https://escholarship.org/uc/item/7p97h8mn
<p>Given a finite grid in \(\mathbb{R}^2\), how many lines are needed to cover all but one point at least \(k\) times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball-Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball-Serra and provide an asymptotic answer for almost all grids. For the standard grid \(\{0,\ldots,n-1\} \times \{0,\ldots,n-1\}\), we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments.</p><p> </p><p>Mathematics Subject Classifications: 05B40, 52C15, 05D40</p><p>Keywords: Grid covering, Alon-Füredi Theorem, combinatorial geometry, linear programming</p>https://escholarship.org/uc/item/7p97h8mnFri, 22 Dec 2023 00:00:00 +0000Bishnoi, AnuragBoyadzhiyska, SimonaDas, ShagnikBakker, Yvonne denLocally uniform random permutations with large increasing subsequences
https://escholarship.org/uc/item/74p4n0rz
<p>We investigate the maximal size of an increasing subset among points randomly sampled from certain probability densities. Kerov and Vershik's celebrated result states that the largest increasing subset among \(N\) uniformly random points on \([0,1]^2\) has size asymptotically \(2\sqrt{N}\). More generally, the order \(\Theta(\sqrt{N})\) still holds if the sampling density is continuous. In this paper we exhibit two sufficient conditions on the density to obtain a growth rate equivalent to any given power of \(N\) greater than \(\sqrt{N}\), up to logarithmic factors. Our proofs use methods of slicing the unit square into appropriate grids, and investigating sampled points appearing in each box.</p><p>Mathematics Subject Classifications: 60C05, 05A05</p><p>Keywords: Random permutations, longest increasing subsequences, permutons</p>https://escholarship.org/uc/item/74p4n0rzFri, 22 Dec 2023 00:00:00 +0000Dubach, VictorOn a common-extendable, non-Sidorenko linear system
https://escholarship.org/uc/item/72c5b093
<p>A system of linear equations in \(\mathbb{F}_p^n\) is common if every two-colouring of \(\mathbb{F}_p^n\) yields at least as many monochromatic solutions as a random two-colouring, asymptotically as \(n \to \infty\). By analogy to the graph-theoretic setting, Alon has asked whether any (non-Sidorenko) system of linear equations can be made uncommon by adding sufficiently many free variables. Fox, Pham and Zhao answered this question in the affirmative among systems which consist of a single equation. We answer Alon's question in the negative.</p><p>We also observe that the property of remaining common despite that addition of arbitrarily many free variables is closely related to a notion of commonness in which one replaces the arithmetic mean of the number of monochromatic solutions with the geometric mean, and furthermore resolve questions of Kamčev-Liebenau-Morrison.</p><p>Mathematics Subject Classifications: 05D10, 11B30</p><p>Keywords: Sidorenko's conjecture, Sidorenko...https://escholarship.org/uc/item/72c5b093Fri, 22 Dec 2023 00:00:00 +0000Altman, DanielThe monopole-dimer model on Cartesian products of plane graphs
https://escholarship.org/uc/item/6gs2p4jx
<p>The monopole-dimer model is a signed variant of the monomer-dimer model which has determinantal structure. We extend the monopole-dimer model for planar graphs (Math. Phys. Anal. Geom., 2015) to Cartesian products thereof and show that the partition function of this model can be expressed as a determinant of a generalised signed adjacency matrix. We then show that the partition function is independent of the orientations of the planar graphs so long as the orientations are Pfaffian. When these planar graphs are bipartite, we show that the computation of the partition function becomes especially simple. We then give an explicit product formula for the partition function of three-dimensional grid graphs a la Kasteleyn and Temperley-Fischer, which turns out to be fourth power of a polynomial when all grid lengths are even. Finally, we generalise this product formula to \(d\) dimensions, again obtaining an explicit product formula. We conclude with a discussion on asymptotic formulas...https://escholarship.org/uc/item/6gs2p4jxFri, 22 Dec 2023 00:00:00 +0000Arora, AnitaAyyer, ArvindBirational rowmotion on a rectangle over a noncommutative ring
https://escholarship.org/uc/item/5407m0q4
<p>We extend the periodicity of birational rowmotion for rectangular posets to the case when the base field is replaced by a noncommutative ring (under appropriate conditions). This resolves a conjecture from 2014. The proof uses a novel approach and is fully self-contained. Consider labelings of a finite poset \(P\) by \(\left\vert P\right\vert + 2\) elements of a ring \(\mathbb{K}\): one label associated with each poset element and two constant labels for the added top and bottom elements in \(\widehat{P}\). Birational rowmotion is a partial map on such labelings. It was originally defined by Einstein and Propp for \(\mathbb{K}=\mathbb{R}\) as a lifting (via detropicalization) of piecewise-linear rowmotion, a map on the order polytope \(\mathcal{O}(P) := \{\text{order-preserving } f: P \to[0,1]\}\). The latter, in turn, extends the well-studied rowmotion map on the set of order ideals (or more properly, the set of order filters) of \(P\), which correspond to the vertices of...https://escholarship.org/uc/item/5407m0q4Fri, 22 Dec 2023 00:00:00 +0000Grinberg, DarijRoby, TomMinimum degrees of finite rectangular bands, null semigroups, and variants of full transformation semigroups
https://escholarship.org/uc/item/4z41x488
<p>For a positive integer \(n\), the full transformation semigroup \({\mathcal T}_n\) consists of all self maps of the set \(\{1,\ldots,n\}\) under composition. Any finite semigroup \(S\) embeds in some \({\mathcal T}_n\), and the least such \(n\) is called the (minimum transformation) degree of \(S\) and denoted \(\mu(S)\). We find degrees for various classes of finite semigroups, including rectangular bands, rectangular groups and null semigroups. The formulae we give involve natural parameters associated to integer compositions. Our results on rectangular bands answer a question of Easdown from 1992, and our approach utilises some results of independent interest concerning partitions/colourings of hypergraphs.</p><p>As an application, we prove some results on the degree of a variant \({\mathcal T}_n^a\). (The variant \(S^a=(S,\star)\) of a semigroup \(S\), with respect to a fixed element \(a\in S\), has underlying set \(S\) and operation \(x\star y=xay\).) It has been previously...https://escholarship.org/uc/item/4z41x488Fri, 22 Dec 2023 00:00:00 +0000Cameron, Peter J.East, JamesFitzGerald, DesMitchell, James D.Pebody, LukeQuinn-Gregson, ThomasSchubert matroids, Delannoy paths, and Speyer's invariant
https://escholarship.org/uc/item/4n0207rm
<p>We provide a combinatorial way of computing Speyer's \(g\)-polynomial on arbitrary Schubert matroids via the enumeration of certain Delannoy paths. We define a new statistic of a basis in a matroid, and express the \(g\)-polynomial of a Schubert matroid in terms of it and internal and external activities. Some surprising positivity properties of the \(g\)-polynomial of Schubert matroids are deduced from our expression. Finally, we combine our formulas with a fundamental result of Derksen and Fink to provide an algorithm for computing the \(g\)-polynomial of an arbitrary matroid.</p><p>Mathematics Subject Classifications: 05B35, 52B40, 14T15</p><p>Keywords: Schubert matroids, \(g\)-polynomial, matroid polytopes, series-parallel matroids, lattice path enumeration</p>https://escholarship.org/uc/item/4n0207rmFri, 22 Dec 2023 00:00:00 +0000Ferroni, LuisShifted insertion algorithms for primed words
https://escholarship.org/uc/item/3pb0v9p9
<p>This article studies some new insertion algorithms that associate pairs of shifted tableaux to finite integer sequences in which certain terms may be primed. When primes are ignored in the input word these algorithms reduce to known correspondences, namely, a shifted form of Edelman-Greene insertion, Sagan-Worley insertion, and Haiman's shifted mixed insertion. These maps have the property that when the input word varies such that one output tableau is fixed, the other output tableau ranges over all (semi)standard tableaux of a given shape with no primed diagonal entries. Our algorithms have the same feature, but now with primes allowed on the main diagonal. One application of this is to give another Littlewood-Richardson rule for products of Schur \(Q\)-functions. It is hoped that there will exist set-valued generalizations of our bijections that can be used to understand products of \(K\)-theoretic Schur \(Q\)-functions.</p><p>Mathematics Subject Classifications: 05A19, 05E05</p><p>Keywords:...https://escholarship.org/uc/item/3pb0v9p9Fri, 22 Dec 2023 00:00:00 +0000Marberg, EricThe induced saturation problem for posets
https://escholarship.org/uc/item/3jd9q8x0
<p>For a fixed poset \(P\), a family \(\mathcal F\) of subsets of \([n]\) is induced \(P\)-saturated if \(\mathcal F\) does not contain an induced copy of \(P\), but for every subset \(S\) of \([n]\) such that \( S\not \in \mathcal F\), \(P\) is an induced subposet of \(\mathcal F \cup \{S\}\). The size of the smallest such family \(\mathcal F\) is denoted by \(\text{sat}^* (n,P)\). Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset \(P\), either \(\text{sat}^* (n,P)=O(1)\) or \(\text{sat}^* (n,P)\geq \log _2 n\). In this paper we improve this general result showing that either \(\text{sat}^* (n,P)=O(1)\) or \(\text{sat}^* (n,P) \geq \min\{ 2 \sqrt{n}, n/2+1\}\). Our proof makes use of a Turán-type result for digraphs.</p><p>Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states...https://escholarship.org/uc/item/3jd9q8x0Fri, 22 Dec 2023 00:00:00 +0000Freschi, AndreaPiga, SimónSharifzadeh, MaryamTreglown, AndrewCounting numerical semigroups by Frobenius number, multiplicity, and depth
https://escholarship.org/uc/item/38w3q7f8
<p>In 1990, Backelin showed that the number of numerical semigroups with Frobenius number \(f\) approaches \(C_i \cdot 2^{f/2}\) for constants \(C_0\) and \(C_1\) depending on the parity of \(f\). In this paper, we generalize this result to semigroups of arbitrary depth by showing there are \(\lfloor (q+1)^2/4 \rfloor^{f/(2q-2)+o(f)}\) semigroups with Frobenius number \(f\) and depth \(q\). More generally, for fixed \(q \geq 3\), we show that, given \((q-1)m ‹ f ‹ qm\), the number of numerical semigroups with Frobenius number \(f\) and multiplicity \(m\) is \[\left(\left\lfloor \frac{(q+2)^2}{4} \right\rfloor^{\alpha/2} \left \lfloor \frac{(q+1)^2}{4} \right\rfloor^{(1-\alpha)/2}\right)^{m + o(m)}\] where \(\alpha = f/m - (q-1)\). Among other things, these results imply Backelin's result, strengthen bounds on \(C_i\), characterize the limiting distribution of multiplicity and genus with respect to Frobenius number, and resolve a recent conjecture of Singhal on the number of semigroups...https://escholarship.org/uc/item/38w3q7f8Fri, 22 Dec 2023 00:00:00 +0000Li, SeanA horizontal-strip LLT polynomial is determined by its weighted graph
https://escholarship.org/uc/item/2sn420w1
<p>We prove that two horizontal-strip LLT polynomials are equal if the associated weighted graphs defined by the author in a previous paper are isomorphic. This provides a sufficient condition for equality of horizontal-strip LLT polynomials and yields a well-defined LLT polynomial indexed by a weighted graph. We use this to prove some new relations between LLT polynomials and we explore a connection with extended chromatic symmetric functions.</p><p>Mathematics Subject Classifications: 05E05, 05E10, 05C15</p><p>Keywords: Chromatic symmetric function, LLT polynomial, Hall-Littlewood polynomial, interval graph, Schur function, weighted graph</p>https://escholarship.org/uc/item/2sn420w1Fri, 22 Dec 2023 00:00:00 +0000Tom, FosterUnavoidable order-size pairs in hypergraphs -- positive forcing density
https://escholarship.org/uc/item/29v8h0bq
<p>Erdős, Füredi, Rothschild and Sós initiated a study of classes of graphs that forbid every induced subgraph on a given number \(m\) of vertices and number \(f\) of edges. Extending their notation to \(r\)-graphs, we write \((n,e) \to_r (m,f)\) if every \(r\)-graph \(G\) on \(n\) vertices with \(e\) edges has an induced subgraph on \(m\) vertices and \(f\) edges. The forcing density of a pair \((m,f)\) is \[ \sigma_r(m,f) =\left. \limsup\limits_{n \to \infty} \frac{|\{e : (n,e) \to_r (m,f)\}|}{\binom{n}{r}} \right. .\] In the graph setting it is known that there are infinitely many pairs \((m, f)\) with positive forcing density. Weber asked if there is a pair of positive forcing density for \(r\geq 3\) apart from the trivial ones \((m, 0)\) and \((m, \binom{m}{r})\). Answering her question, we show that \((6,10)\) is such a pair for \(r=3\) and conjecture that it is the unique such pair. Further, we find necessary conditions for a pair to have positive forcing density, supporting...https://escholarship.org/uc/item/29v8h0bqFri, 22 Dec 2023 00:00:00 +0000Axenovich, MariaBalogh, JózsefClemen, Felix ChristianWeber, LeaHarmonic differential forms for pseudo-reflection groups II. Bi-degree bounds
https://escholarship.org/uc/item/2289r0v1
<p>This paper studies three results that describe the structure of the super-coinvariant algebra of pseudo-reflection groups over a field of characteristic \(0\). Our most general result determines the top component in total degree, which we prove for all Shephard-Todd groups \(G(m, p, n)\) with \(m \neq p\) or \(m=1\). Our strongest result gives tight bi-degree bounds and is proven for all \(G(m, 1, n)\), which includes the Weyl groups of types \(A\) and \(B\)/\(C\). For symmetric groups (i.e. type \(A\)), this provides new evidence for a recent conjecture of Zabrocki related to the Delta Conjecture of Haglund-Remmel-Wilson. Finally, we examine analogues of a classic theorem of Steinberg and the Operator Theorem of Haiman.</p><p>Our arguments build on the type-independent classification of semi-invariant harmonic differential forms carried out in the first paper in this sequence. In this paper we use concrete constructions including Gröbner and Artin bases for the classical coinvariant...https://escholarship.org/uc/item/2289r0v1Fri, 22 Dec 2023 00:00:00 +0000Swanson, Joshua P.Wallach, Nolan R.Webs and canonical bases in degree two
https://escholarship.org/uc/item/1s28q0vg
<p>We show that Lusztig's canonical basis for the degree two part of the Grassmannian coordinate ring is given by \({\rm SL}_k\) web diagrams. Equivalently, we show that every \({\rm SL}_2\) web immanant of a plabic graph for \({\rm Gr}(k,n)\) is an \({\rm SL}_k\) web invariant.</p><p>Mathematics Subject Classifications: 05E10, 14M15, 20C30</p><p>Keywords: Grassmannians, webs, canonical basis, Catalan</p>https://escholarship.org/uc/item/1s28q0vgFri, 22 Dec 2023 00:00:00 +0000Fraser, ChrisThe combinatorics of a tree-like functional equation for connected chord diagrams
https://escholarship.org/uc/item/1qg5647z
<p>We build on recent work of Yeats, Courtiel, and others involving connected chord diagrams. We first derive from a Hopf-algebraic foundation a class of tree-like functional equations and prove that they are solved by weighted generating functions of two different subsets of weighted connected chord diagrams: arbitrary diagrams and diagrams forbidding so-called top cycle subdiagrams. These equations generalize the classic specification for increasing ordered trees and their solution uses a novel decomposition, simplifying and generalizing previous results. The resulting tree perspective on chord diagrams leads to new enumerative insights through the study of novel diagram classes. We present a recursive bijection between connected top-cycle-free diagrams with \(n\) chords and triangulations of a disk with \(n+1\) vertices, thereby counting the former. This connects to combinatorial maps, Catalan intervals, and uniquely sorted permutations, leading to new conjectured bijective...https://escholarship.org/uc/item/1qg5647zFri, 22 Dec 2023 00:00:00 +0000Nabergall, LukasHighest weight crystals for Schur \(Q\)-functions
https://escholarship.org/uc/item/8hb775tk
<p>Work of Grantcharov et al. develops a theory of abstract crystals for the queer Lie superalgebra \(\mathfrak{q}_n\). Such \(\mathfrak{q}_n\)-crystals form a monoidal category in which the connected normal objects have unique highest weight elements and characters that are Schur \(P\)-polynomials. This article studies a modified form of this category, whose connected normal objects again have unique highest weight elements but now possess characters that are Schur \(Q\)-polynomials. The crystals in this category have some interesting features not present for ordinary \(\mathfrak{q}_n\)-crystals. For example, there is an extra crystal operator, a different tensor product, and an action of the hyperoctahedral group exchanging highest and lowest weight elements. There are natural examples of \(\mathfrak{q}_n\)-crystal structures on certain families of shifted tableaux and factorized reduced words. We describe extended forms of these structures that give similar examples in our...https://escholarship.org/uc/item/8hb775tkThu, 14 Sep 2023 00:00:00 +0000Marberg, EricTong, Kam HungOn the sizes of \(t\)-intersecting \(k\)-chain-free families
https://escholarship.org/uc/item/8236n14k
<p>A set system \({\mathcal F}\) is \(t\)-intersecting, if the size of the intersection of every pair of its elements has size at least \(t\). A set system \({\mathcal F}\) is \(k\)-Sperner, if it does not contain a chain of length \(k+1\). Our main result is the following: Suppose that \(k\) and \(t\) are fixed positive integers, where \(n+t\) is even and \(n\) is large enough. If \({\mathcal F}\subseteq 2^{[n]}\) is a \(t\)-intersecting \(k\)-Sperner family, then \(|{\mathcal F}|\) has size at most the size of the sum of \(k\) layers, of sizes \((n+t)/2,\ldots, (n+t)/2+k-1\). This bound is best possible. The case when \(n+t\) is odd remains open.</p><p>Mathematics Subject Classifications: 05D05</p><p>Keywords: Extremal set theory, Sperner families, intersection theorems</p>https://escholarship.org/uc/item/8236n14kThu, 14 Sep 2023 00:00:00 +0000Balogh, JózsefLinz, William B.Patkós, BalázsOn the birational geometry of matroids
https://escholarship.org/uc/item/7t28108s
<p>This paper investigates isomorphisms of Bergman fans of matroids respecting different fan structures, which we regard as matroid analogs of birational maps. We show that isomorphisms respecting the fine fan structure are induced by matroid isomorphisms.</p><p>We introduce Cremona automorphisms of the coarse structure of Bergman fans, which are not induced by matroid automorphisms. We show that the automorphism group of the coarse fan structure is generated by matroid automorphisms and Cremona maps in the case of rank \(3\) matroids which are not parallel connections and for modularly complemented matroids.</p><p>Mathematics Subject Classifications: 14T20, 52B40, 14E07</p><p>Keywords: Matroids, birational geometry</p>https://escholarship.org/uc/item/7t28108sThu, 14 Sep 2023 00:00:00 +0000Shaw, KrisWerner, AnnetteA proof of Frankl's conjecture on cross-union families
https://escholarship.org/uc/item/6gt1p3j8
<p>The families \(\mathcal{F}_0,\ldots,\mathcal{F}_s\) of \(k\)-element subsets of \([n]:=\{1,2,\ldots,n\}\) are called cross-union if there is no choice of \(F_0\in \mathcal{F}_0, \ldots, F_s\in \mathcal{F}_s\) such that \(F_0\cup\ldots\cup F_s=[n]\). A natural generalization of the celebrated Erdős-Ko-Rado theorem, due to Frankl and Tokushige, states that for \(n\le (s+1)k\) the geometric mean of \(\lvert\mathcal{F}_i\rvert\) is at most \(\binom{n-1}{k}\). Frankl conjectured that the same should hold for the arithmetic mean under some mild conditions. We prove Frankl's conjecture in a strong form by showing that the unique (up to isomorphism) maximizer for the arithmetic mean of cross-union families is the natural one \(\mathcal{F}_0=\ldots=\mathcal{F}_s={[n-1]\choose k}\).</p><p>Mathematics Subject Classifications: 05D05</p><p>Keywords: Extremal set theory, generalizations of Erdős-Ko-Rado, cross-union families, cross-intersecting families</p>https://escholarship.org/uc/item/6gt1p3j8Thu, 14 Sep 2023 00:00:00 +0000Cambie, StijnKim, JaehoonLiu, HongTran, TuanTilings of benzels via the abacus bijection
https://escholarship.org/uc/item/5h16p4t1
<p>Propp recently introduced regions in the hexagonal grid called benzels and stated several enumerative conjectures about the tilings of benzels using two types of prototiles called stones and bones. We resolve two of his conjectures and prove some additional results that he left tacit. In order to solve these problems, we first transfer benzels into the square grid. One of our primary tools, which we combine with several new ideas, is a bijection (rediscovered by Stanton and White and often attributed to them although it is considerably older) between \(k\)-ribbon tableaux of certain skew shapes and certain \(k\)-tuples of Young tableaux.</p><p>Mathematics Subject Classifications: 05B45, 05A15, 05A17</p><p>Keywords: Tiling, benzel, abacus bijection, core partition, domino, stone, bone</p>https://escholarship.org/uc/item/5h16p4t1Thu, 14 Sep 2023 00:00:00 +0000Defant, ColinLi, RupertPropp, JamesYoung, BenjaminOptimal schemes for combinatorial query problems with integer feedback
https://escholarship.org/uc/item/5cb9m4f1
<p>A query game is a pair of a set \(Q\) of queries and a set \(\mathcal{F}\) of functions, or codewords \(f:Q\rightarrow \mathbb{Z}.\) We think of this as a two-player game. One player, Codemaker, picks a hidden codeword \(f\in \mathcal{F}\). The other player, Codebreaker, then tries to determine \(f\) by asking a sequence of queries \(q\in Q\), after each of which Codemaker must respond with the value \(f(q)\). The goal of Codebreaker is to uniquely determine \(f\) using as few queries as possible. Two classical examples of such games are coin-weighing with a spring scale, and Mastermind, which are of interest both as recreational games and for their connection to information theory.</p><p>In this paper, we will present a general framework for finding short solutions to query games. As applications, we give new self-contained proofs of the query complexity of variations of the coin-weighing problems, and prove new results that the deterministic query complexity of Mastermind...https://escholarship.org/uc/item/5cb9m4f1Thu, 14 Sep 2023 00:00:00 +0000Martinsson, AndersHomomesy via toggleability statistics
https://escholarship.org/uc/item/53j5m46g
<p>The rowmotion operator acting on the set of order ideals of a finite poset has been the focus of a significant amount of recent research. One of the major goals has been to exhibit homomesies: statistics that have the same average along every orbit of the action. We systematize a technique for proving that various statistics of interest are homomesic by writing these statistics as linear combinations of "toggleability statistics" (originally introduced by Striker) plus a constant. We show that this technique recaptures most of the known homomesies for the posets on which rowmotion has been most studied. We also show that the technique continues to work in modified contexts. For instance, this technique also yields homomesies for the piecewise-linear and birational extensions of rowmotion; furthermore, we introduce a \(q\)-analogue of rowmotion and show that the technique yields homomesies for "\(q\)-rowmotion" as well.</p><p>Mathematics Subject Classifications: 06A07, 05E18,...https://escholarship.org/uc/item/53j5m46gThu, 14 Sep 2023 00:00:00 +0000Defant, ColinHopkins, SamPoznanović, SvetlanaPropp, JamesDiscrete dynamics in cluster integrable systems from geometric \(R\)-matrix transformations
https://escholarship.org/uc/item/2z04v7bz
<p>Cluster integrable systems are a broad class of integrable systems modelled on bipartite dimer models on the torus. Many discrete integrable dynamics arise by applying sequences of local transformations, which form the cluster modular group of the cluster integrable system. This cluster modular group was recently characterized by the first author and Inchiostro. There exist some discrete integrable dynamics that make use of non-local transformations associated with geometric \(R\)-matrices. In this article we characterize the generalized cluster modular group - which includes both local and non-local transformations - in terms of extended affine symmetric groups. We also describe the action of the generalized cluster modular group on the spectral data associated with cluster integrable systems.</p><p>Mathematics Subject Classifications: 82B23, 13F60, 14H70, 20B35</p><p>Keywords: Bipartite dimer model, cluster algebras, geometric \(R\)-matrices, discrete integrable systems,...https://escholarship.org/uc/item/2z04v7bzThu, 14 Sep 2023 00:00:00 +0000George, TerrenceRamassamy, SanjaySub-Fibonacci behavior in numerical semigroup enumeration
https://escholarship.org/uc/item/2qm1c11d
<p>In 2013, Zhai proved that most numerical semigroups of a given genus have depth at most \(3\) and that the number \(n_g\) of numerical semigroups of a genus \(g\) is asymptotic to \(S\varphi^g\), where \(S\) is some positive constant and \(\varphi \approx 1.61803\) is the golden ratio. In this paper, we prove exponential upper and lower bounds on the factors that cause \(n_g\) to deviate from a perfect exponential, including the number of semigroups with depth at least \(4\). Among other applications, these results imply the sharpest known asymptotic bounds on \(n_g\) and shed light on a conjecture by Bras-Amorós (2008) that \(n_g \geq n_{g-1} + n_{g-2}\). Our main tools are the use of Kunz coordinates, introduced by Kunz (1987), and a result by Zhao (2011) bounding weighted graph homomorphisms.</p><p>Mathematics Subject Classifications: 20M14, 05A15, 05A16</p><p>Keywords: Numerical semigroup, genus, Kunz coordinate, graph homomorphism</p>https://escholarship.org/uc/item/2qm1c11dThu, 14 Sep 2023 00:00:00 +0000Zhu, Daniel G.Mullineux involution and crystal isomorphisms
https://escholarship.org/uc/item/2q44c38n
<p>We develop a new approach for the computation of the Mullineux involution for the symmetric group and its Hecke algebra using the notion of crystal isomorphism and the Iwahori-Matsumoto involution for the affine Hecke algebra of type \(A\). As a consequence, we obtain several new elementary combinatorial algorithms for its computation, one of which is equivalent to Xu algorithm (and thus Mullineux original algorithm). We thus obtain a simple interpretation of these algorithms and a new elementary proof that they indeed compute the Mullineux involution.</p><p>Mathematics Subject Classifications: 20C08, 05E10</p><p>Keywords: Symmetric group, Mullineux involution, crystal graph</p>https://escholarship.org/uc/item/2q44c38nThu, 14 Sep 2023 00:00:00 +0000Jacon, NicolasThe Schwarzian octahedron recurrence (dSKP equation) I: explicit solutions
https://escholarship.org/uc/item/2jq67049
<p>We prove an explicit expression for the solutions of the discrete Schwarzian octahedron recurrence, also known as the discrete Schwarzian KP equation (dSKP), as the ratio of two partition functions. Each one counts weighted oriented dimer configurations of an associated bipartite graph, and is equal to the determinant of a Kasteleyn matrix. This is in the spirit of Speyer's result on the dKP equation, or octahedron recurrence (Journal of Alg. Comb. 2007). One consequence is that dSKP has zero algebraic entropy, meaning that the growth of the degrees of the polynomials involved is only polynomial. There are cancellations in the partition function, and we prove an alternative, cancellation free explicit expression involving complementary trees and forests. Using all of the above, we show several instances of the Devron property for dSKP, i.e., that certain singularities in initial data repeat after a finite number of steps. This has many applications for discrete geometric systems...https://escholarship.org/uc/item/2jq67049Thu, 14 Sep 2023 00:00:00 +0000Affolter, Niklas Christophde Tilière, BéatriceMelotti, PaulExact enumeration of satisfiable 2-SAT formulae
https://escholarship.org/uc/item/1m48c7s8
<p>We obtain exact expressions counting the satisfiable 2-SAT formulae and describe the structure of associated implication digraphs. Our approach is based on generating function manipulations. To reflect the combinatorial specificities of the implication digraphs, we introduce a new kind of generating function, the Implication generating function, inspired by the Graphic generating function used in digraph enumeration. Using the underlying recurrences, we make accurate numerical predictions of the phase transition curve of the 2-SAT problem inside the critical window. We expect these exact formulae to be amenable to rigorous asymptotic analysis using complex analytic tools, leading to a more detailed picture of the 2-SAT phase transition in the future.</p><p>Mathematics Subject Classifications: 05A15, 68Q87, 68R95</p><p>Keywords: 2-CNF, exact enumeration, random graphs, phase transitions, strongly connected components, satisfiability, generating functions</p>https://escholarship.org/uc/item/1m48c7s8Thu, 14 Sep 2023 00:00:00 +0000Dovgal, Sergeyde Panafieu, ÉlieRavelomanana, VladyGeneralized weights of codes over rings and invariants of monomial ideals
https://escholarship.org/uc/item/10z7j96g
<p>We develop an algebraic theory of supports for \(R\)-linear codes of fixed length, where \(R\) is a finite commutative unitary ring. A support naturally induces a notion of generalized weights and allows one to associate a monomial ideal to a code. Our main result states that, under suitable assumptions, the generalized weights of a code can be obtained from the graded Betti numbers of its associated monomial ideal. In the case of \(\mathbb{F}_q\)-linear codes endowed with the Hamming metric, the ideal coincides with the Stanley-Reisner ideal of the matroid associated to the code via its parity-check matrix. In this special setting, we recover the known result that the generalized weights of an \(\mathbb{F}_q\)-linear code can be obtained from the graded Betti numbers of the ideal of the matroid associated to the code. We also study subcodes and codewords of minimal support in a code, proving that a large class of \(R\)-linear codes is generated by its codewords of minimal...https://escholarship.org/uc/item/10z7j96gThu, 14 Sep 2023 00:00:00 +0000Gorla, ElisaRavagnani, AlbertoPaths of given length in tournaments
https://escholarship.org/uc/item/89b7027k
<p>We prove that every \(n\)-vertex tournament has at most \(n \left(\frac{n-1}{2} \right)^k\) walks of length \(k\).</p><p>Mathematics Subject Classifications: 05C38, 05D99</p><p>Keywords: Paths, tournaments</p>https://escholarship.org/uc/item/89b7027kWed, 13 Sep 2023 00:00:00 +0000Sah, AshwinSawhney, MehtaabZhao, YufeiRSK tableaux and box-ball systems
https://escholarship.org/uc/item/5700d4s0
<p>A box-ball system is a discrete dynamical system whose dynamics come from the balls jumping according to certain rules. A permutation on \(n\) objects gives a box-ball system state by assigning its one-line notation to \(n\) consecutive boxes. After a finite number of steps, a box-ball system will reach a steady state. From any steady state, we can construct a tableau called the soliton decomposition of the box-ball system. We prove that if the soliton decomposition of a permutation \(w\) is a standard tableau or if its shape coincides with the Robinson-Schensted (RS) partition of \(w\), then the soliton decomposition of \(w\) and the RS insertion tableau of \(w\) are equal. We also use row reading words, Knuth moves, RS recording tableaux, and a localized version of Greene's theorem (proven recently by Lewis, Lyu, Pylyavskyy, and Sen) to study various properties of a box-ball system.</p><p>Mathematics Subject Classifications: 05A05, 05A17, 37B15</p><p>Keywords: Permutations,...https://escholarship.org/uc/item/5700d4s0Wed, 13 Sep 2023 00:00:00 +0000Drucker, BenGarcia, EliGunawan, EmilyRumbolt, AubreySilver, RoseRectangular analogues of the square paths conjecture and the univariate Delta conjecture
https://escholarship.org/uc/item/53s7m4h3
<p>In this paper, we extend the rectangular side of the shuffle conjecture by stating a rectangular analogue of the square paths conjecture. In addition, we describe a set of combinatorial objects and one statistic that are a first step towards a rectangular extension of (the rise version of) the Delta conjecture, and of (the rise version of) the Delta square conjecture, corresponding to the case \(q=1\) of an expected general statement. We also prove our new rectangular paths conjecture in the special case when the sides of the rectangle are coprime.</p><p>Mathematics Subject Classifications: 05E05</p><p>Keywords: Macdonald polynomials, symmetric functions</p>https://escholarship.org/uc/item/53s7m4h3Wed, 13 Sep 2023 00:00:00 +0000Iraci, AlessandroPagaria, RobertoPaolini, GiovanniVanden Wyngaerd, AnnaA lattice model for super LLT polynomials
https://escholarship.org/uc/item/24s1x99c
<p>We introduce a solvable lattice model for supersymmetric LLT polynomials, also known as super LLT polynomials, based upon particle interactions in super \(n\)-ribbon tableaux. Using related Heisenberg operators on a Fock space, we prove Cauchy and Pieri identities for super LLT polynomials, simultaneously generalizing the Cauchy, dual Cauchy, and Pieri identities for LLT polynomials. Lastly, we construct a solvable semi-infinite Cauchy lattice model with a surprising Yang-Baxter equation and examine its connections to the Pieri and Cauchy identities.</p><p>Mathematics Subject Classifications: 05E05, 82B20, 05E10</p><p>Keywords: Lattice models, super LLT polynomials</p>https://escholarship.org/uc/item/24s1x99cWed, 13 Sep 2023 00:00:00 +0000Curran, Michael J.Frechette, ClaireYost-Wolff, CalvinZhang, Sylvester W.Zhang, ValerieAn asymptotically tight lower bound for superpatterns with small alphabets
https://escholarship.org/uc/item/0cd5r5c8
<p>A permutation \(\sigma \in S_n\) is a \(k\)-superpattern (or \(k\)-universal) if it contains each \({\tau \in S_k}\) as a pattern. This notion of "superpatterns" can be generalized to words on smaller alphabets, and several questions about superpatterns on small alphabets have recently been raised in the survey of Engen and Vatter. One of these questions concerned the length of the shortest \(k\)-superpattern on \([k+1]\). A construction by Miller gave an upper bound of \({(k^2+k)/2}\), which we show is optimal up to lower-order terms. This implies a weaker version of a conjecture by Eriksson, Eriksson, Linusson and Wastlund. Our results also refute a 40-year-old conjecture of Gupta.</p><p>Mathematics Subject Classifications: 05A05, 60C05</p><p>Keywords: Patterns, permutations, probabalistic method</p>https://escholarship.org/uc/item/0cd5r5c8Wed, 13 Sep 2023 00:00:00 +0000Hunter, ZachGrass(mannian) trees and forests: Variations of the exponential formula, with applications to the momentum amplituhedron
https://escholarship.org/uc/item/8xv6q5w3
<p>The Exponential Formula allows one to enumerate any class of combinatorial objects built by choosing a set of connected components and placing a structure on each connected component which depends only on its size. There are multiple variants of this result, including Speicher's result for noncrossing partitions, as well as analogues of the Exponential Formula for series-reduced planar trees and forests. In this paper we use these formulae to give generating functions for contracted Grassmannian trees and forests, certain graphs whose vertices are decorated with a helicity. Along the way we enumerate bipartite planar trees and forests, and we apply our results to enumerate various families of permutations: for example, bipartite planar trees are in bijection with separable permutations. It is postulated by Livia Ferro, Tomasz Łukowski and Robert Moerman (2020) that contracted Grassmannian forests are in bijection with boundary strata of the momentum amplituhedron, an object...https://escholarship.org/uc/item/8xv6q5w3Tue, 14 Mar 2023 00:00:00 +0000Moerman, RobertWilliams, Lauren K.Self-avoiding walks and multiple context-free languages
https://escholarship.org/uc/item/8928m3zx
<p>Let \(G\) be a quasi-transitive, locally finite, connected graph rooted at a vertex \(o\), and let \(c_n(o)\) be the number of self-avoiding walks of length \(n\) on \(G\) starting at \(o\). We show that if \(G\) has only thin ends, then the generating function \(F_{\mathrm{SAW},o}(z)=\sum_{n \geq 1} c_n(o) z^n\) is an algebraic function. In particular, the connective constant of such a graph is an algebraic number.</p><p>If \(G\) is deterministically edge-labelled, that is, every (directed) edge carries a label such that no two edges starting at the same vertex have the same label, then the set of all words which can be read along the edges of self-avoiding walks starting at \(o\) forms a language denoted by \(L_{\mathrm{SAW},o}\). Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that \(L_{\mathrm{SAW},o}\) is a \(k\)-multiple context-free language if and only if the size of all ends of \(G\) is at most \(2k\). Applied to Cayley...https://escholarship.org/uc/item/8928m3zxTue, 14 Mar 2023 00:00:00 +0000Lehner, FlorianLindorfer, ChristianPackings and Steiner systems in polar spaces
https://escholarship.org/uc/item/83g3149p
<p>A finite classical polar space of rank \(n\) consists of the totally isotropic subspaces of a finite vector space equipped with a nondegenerate form such that \(n\) is the maximal dimension of such a subspace. A \(t\)-Steiner system in a finite classical polar space of rank \(n\) is a collection \(Y\) of totally isotropic \(n\)-spaces such that each totally isotropic \(t\)-space is contained in exactly one member of \(Y\). Nontrivial examples are known only for \(t=1\) and \(t=n-1\). We give an almost complete classification of such \(t\)-Steiner systems, showing that such objects can only exist in some corner cases. This classification result arises from a more general result on packings in polar spaces.</p><p>Mathematics Subject Classifications: 51E23, 05E30, 33C80</p><p>Keywords: Association schemes, codes, polar spaces, Steiner systems</p>https://escholarship.org/uc/item/83g3149pTue, 14 Mar 2023 00:00:00 +0000Schmidt, Kai-UweWeiß, CharleneA combinatorial basis for the fermionic diagonal coinvariant ring
https://escholarship.org/uc/item/7nv8g68m
<p>Let \(\Theta_n = (\theta_1, \dots, \theta_n)\) and \(\Xi_n = (\xi_1, \dots, \xi_n)\) be two lists of \(n\) variables and consider the diagonal action of \(\mathfrak{S}_n\) on the exterior algebra \(\wedge \{ \Theta_n, \Xi_n \}\) generated by these variables. Jongwon Kim and Rhoades defined and studied the fermionic diagonal coinvariant ring \(FDR_n\) obtained from \(\wedge \{ \Theta_n, \Xi_n \}\) by modding out by the \(\mathfrak{S}_n\)-invariants with vanishing constant term. The author and Rhoades gave a basis for the maximal degree components of this ring where the action of \(\mathfrak{S}_n\) could be interpreted combinatorially via noncrossing set partitions. This paper will do similarly for the entire ring, although the combinatorial interpretation will be limited to the action of \(\mathfrak{S}_{n-1} \subset \mathfrak{S}_n\). The basis will be indexed by a certain class of noncrossing partitions.</p><p>Mathematics Subject Classifications: 05E10, 05E18, 20C30</p><p>Keywords:...https://escholarship.org/uc/item/7nv8g68mTue, 14 Mar 2023 00:00:00 +0000Kim, JesseBar-and-joint rigidity on the moment curve coincides with cofactor rigidity on a conic
https://escholarship.org/uc/item/7n514431
<p>We show that, for points along the moment curve, the bar-and-joint rigidity matroid and the hyperconnectivity matroid coincide, and that both coincide with the \(C^{d-2}_{d-1}\)-cofactor rigidity of points along any (non-degenerate) conic in the plane. For hyperconnectivity in dimension two, having the points in the moment curve is no loss of generality. We also show that, restricted to bipartite graphs, the bar-and-joint rigidity matroid is freer than the hyperconnectivity matroid.</p><p>Mathematics Subject Classifications: 52C25, 52B40</p><p>Keywords: Rigidity, hyperconnectivity, moment curve, cofactor rigidity</p>https://escholarship.org/uc/item/7n514431Tue, 14 Mar 2023 00:00:00 +0000Crespo Ruiz, LuisSantos, FranciscoTriangular-grid billiards and plabic graphs
https://escholarship.org/uc/item/5tg1p6sx
<p>Given a polygon \(P\) in the triangular grid, we obtain a permutation \(\pi_P\) via a natural billiards system in which beams of light bounce around inside of \(P\). The different cycles in \(\pi_P\) correspond to the different trajectories of light beams. We prove that \[\operatorname{area}(P)\geq 6\operatorname{cyc}(P)-6\quad\text{and}\quad\operatorname{perim}(P)\geq\frac{7}{2}\operatorname{cyc}(P)-\frac{3}{2},\] where \(\operatorname{area}(P)\) and \(\operatorname{perim}(P)\) are the (appropriately normalized) area and perimeter of \(P\), respectively, and \(\operatorname{cyc}(P)\) is the number of cycles in \(\pi_P\). The inequality concerning \(\operatorname{area}(P)\) is tight, and we characterize the polygons \(P\) satisfying \(\operatorname{area}(P)=6\operatorname{cyc}(P)-6\). These results can be reformulated in the language of Postnikov's plabic graphs as follows. Let \(G\) be a connected reduced plabic graph with essential dimension \(2\). Suppose \(G\) has \(n\)...https://escholarship.org/uc/item/5tg1p6sxTue, 14 Mar 2023 00:00:00 +0000Defant, ColinJiradilok, PakawutChain enumeration, partition lattices and polynomials with only real roots
https://escholarship.org/uc/item/5nh7x8kr
<p>The coefficients of the chain polynomial of a finite poset enumerate chains in the poset by their number of elements. The chain polynomials of the partition lattices and their standard type \(B\) analogues are shown to have only real roots. The real-rootedness of the chain polynomial is conjectured for all geometric lattices and is shown to be preserved by the pyramid and the prism operations on Cohen-Macaulay posets. As a result, new families of convex polytopes whose barycentric subdivisions have real-rooted \(f\)-polynomials are presented. An application to the face enumeration of the second barycentric subdivision of the boundary complex of the simplex is also included.</p><p>Mathematics Subject Classifications: 05A05, 05A18, 05E45, 06A07, 26C10</p><p>Keywords: Chain polynomial, geometric lattice, partition lattice, real-rooted polynomial, flag \(h\)-vector, convex polytope, barycentric subdivision</p>https://escholarship.org/uc/item/5nh7x8krTue, 14 Mar 2023 00:00:00 +0000Athanasiadis, Christos A.Kalampogia-Evangelinou, KaterinaClasses of graphs embeddable in order-dependent surfaces
https://escholarship.org/uc/item/5102m2m6
<p>Given a function \(g=g(n)\) we let \(\mathcal{E}^g\) be the class of all graphs \(G\) such that if \(G\) has order \(n\) (that is, has \(n\) vertices) then it is embeddable in some surface of Euler genus at most \(g(n)\), and let \(\widetilde{\mathcal E}^g\) be the corresponding class of unlabelled graphs. We give estimates of the sizes of these classes. For example we show that if \(g(n)=o(n/\log^3n)\) then the class \(\mathcal{E}^{g}\) has growth constant \(\gamma_{\mathcal{P}}\), the (labelled) planar graph growth constant; and when \(g(n) = O(n)\) we estimate the number of n-vertex graphs in \(\mathcal{E}^{g}\) and \(\widetilde{\mathcal E}^g\) up to a factor exponential in \(n\). From these estimates we see that, if \(\mathcal{E}^g\) has growth constant \(\gamma_{\mathcal{P}}\) then we must have \(g(n)=o(n/\log n)\), and the generating functions for \(\mathcal{E}^g\) and \(\widetilde{\mathcal E}^g\) have strictly positive radius of convergence if and only if \(g(n)=O(n/\log...https://escholarship.org/uc/item/5102m2m6Tue, 14 Mar 2023 00:00:00 +0000McDiarmid, ColinSaller, SophiaExtensions of the Kahn-Saks inequality for posets of width two
https://escholarship.org/uc/item/4bd6q0m1
<p>The Kahn-Saks inequality is a classical result on the number of linear extensions of finite posets. We give a new proof of this inequality for posets of width two and both elements in the same chain using explicit injections of lattice paths. As a consequence we obtain a \(q\)-analogue, a multivariate generalization and an equality condition in this case. We also discuss the equality conditions of the Kahn-Saks inequality for general posets and prove several implications between conditions conjectured to be equivalent.</p><p>Mathematics Subject Classifications: 05A15, 05A19, 05A20, 05A30, 06A07</p><p>Keywords: Poset inequality, Stanley's inequality, Kahn-Saks inequality, log-concavity, q-analogues, equality conditions, lattice paths</p>https://escholarship.org/uc/item/4bd6q0m1Tue, 14 Mar 2023 00:00:00 +0000Chan, Swee HongPak, IgorPanova, GretaProof of a bi-symmetric septuple equidistribution on ascent sequences
https://escholarship.org/uc/item/3225t6v2
<p>It is well known since the seminal work by Bousquet-Mélou, Claesson, Dukes and Kitaev (2010) that certain refinements of the ascent sequences with respect to several natural statistics are in bijection with corresponding refinements of \(({\bf2+2})\)-free posets and permutations that avoid a bi-vincular pattern. Different multiply-refined enumerations of ascent sequences and other bijectively equivalent structures have subsequently been extensively studied by various authors. In this paper, our main contributions are</p>a bijective proof of a bi-symmetric septuple equidistribution of Euler-Stirling statistics on ascent sequences, involving the number of ascents (\(\mathsf{asc}\)), the number of repeated entries (\(\mathsf{rep}\)), the number of zeros (\(\mathsf{zero}\)), the number of maximal entries (\(\mathsf{max}\)), the number of right-to-left minima (\(\mathsf{rmin}\)) and two auxiliary statistics; a new transformation formula for non-terminating basic hypergeometric \(_4\phi_3\)...https://escholarship.org/uc/item/3225t6v2Tue, 14 Mar 2023 00:00:00 +0000Jin, Emma YuSchlosser, Michael J.Set-valued tableaux rule for Lascoux polynomials
https://escholarship.org/uc/item/2qp6q4w9
<p>Lascoux polynomials generalize Grassmannian stable Grothendieck polynomials and may be viewed as K-theoretic analogs of key polynomials. The latter two polynomials have combinatorial formulas involving tableaux: Lascoux and Schützenberger gave a combinatorial formula for key polynomials using right keys; Buch gave a set-valued tableau formula for Grassmannian stable Grothendieck polynomials. We establish a novel combinatorial description for Lascoux polynomials involving right keys and set-valued tableaux. Our description generalizes the tableaux formulas of key polynomials and Grassmannian stable Grothendieck polynomials. To prove our description, we construct a new abstract Kashiwara crystal structure on set-valued tableaux. This construction answers an open problem of Monical, Pechenik and Scrimshaw.</p><p>Mathematics Subject Classifications: 05E05</p><p>Keywords: Lascoux polynomials, set-valued tableaux, crystal operators</p>https://escholarship.org/uc/item/2qp6q4w9Tue, 14 Mar 2023 00:00:00 +0000Yu, TianyiRainbow version of the Erdős Matching Conjecture via concentration
https://escholarship.org/uc/item/2c6553mf
<p>We say that the families \(\mathcal{F}_1,\ldots, \mathcal{F}_{s+1}\) of \(k\)-element subsets of \([n]\) are cross-dependent if there are no pairwise disjoint sets \(F_1,\ldots, F_{s+1}\), where \(F_i\in \mathcal{F}_i\) for each \(i\). The rainbow version of the Erdős Matching Conjecture due to Aharoni and Howard and independently to Huang, Loh and Sudakov states that \(\min_{i} |\mathcal{F}_i|\le \max\big\{{n\choose k}-{n-s\choose k}, {(s+1)k-1\choose k}\big\}\) for \(n\ge (s+1)k\). In this paper, we prove this conjecture for \(n›3e(s+1)k\) and \(s›10^7\). One of the main tools in the proof is a concentration inequality due to Frankl and Kupavskii.</p><p>Mathematics Subject Classifications: 05D05</p><p>Keywords: Extremal set theory, Erdos matching conjecture, rainbow version</p>https://escholarship.org/uc/item/2c6553mfTue, 14 Mar 2023 00:00:00 +0000Kupavskii, AndreyLazy tournaments and multidegrees of a projective embedding of \(\overline{M}_{0,n}\)
https://escholarship.org/uc/item/24j1h4dk
<p>We consider the (iterated) Kapranov embedding \(\Omega_n:\overline{M}_{0,n+3} \hookrightarrow \mathbb{P}^1 \times \cdots \times \mathbb{P}^n\), where \(\overline{M}_{0,n+3}\) is the moduli space of stable genus \(0\) curves with \(n+3\) marked points. In 2020, Gillespie, Cavalieri, and Monin gave a recursion satisfied by the multidegrees of \(\Omega_n\) and showed, using two combinatorial insertion algorithms on certain parking functions, that the total degree of \(\Omega_n\) is \((2n-1)!!=(2n-1)\cdot (2n-3) \cdots 5 \cdot 3 \cdot 1\). In this paper, we give a new proof of this fact by enumerating each multidegree by a set of boundary points of \(\overline{M}_{0,n+3}\), via an algorithm on trivalent trees that we call a lazy tournament. The advantages of this new interpretation are twofold: first, these sets project to one another under the forgetting maps used to derive the multidegree recursion. Second, these sets naturally partition the complete set of boundary points on...https://escholarship.org/uc/item/24j1h4dkTue, 14 Mar 2023 00:00:00 +0000Gillespie, MariaGriffin, Sean T.Levinson, JakeShelling the \(m=1\) amplituhedron
https://escholarship.org/uc/item/245432bz
<p>The amplituhedron \(\mathcal{A}_{n,k,m}\) was introduced by Arkani-Hamed and Trnka (2014) in order to give a geometric basis for calculating scattering amplitudes in planar \(\mathcal{N}=4\) supersymmetric Yang-Mills theory. It is a projection inside the Grassmannian \(\text{Gr}_{k,k+m}\) of the totally nonnegative part of \(\text{Gr}_{k,n}\). Karp and Williams (2019) studied the \(m=1\) amplituhedron \(\mathcal{A}_{n,k,1}\), giving a regular CW decomposition of it. Its face poset \(R_{n,l}\) (with \(l := n-k-1\)) consists of all projective sign vectors of length \(n\) with exactly \(l\) sign changes. We show that \(R_{n,l}\) is EL-shellable, resolving a problem posed by Karp and Williams. This gives a new proof that \(\mathcal{A}_{n,k,1}\) is homeomorphic to a closed ball, which was originally proved by Karp and Williams. We also give explicit formulas for the \(f\)-vector and \(h\)-vector of \(R_{n,l}\), and show that it is rank-log-concave and strongly Sperner. Finally,...https://escholarship.org/uc/item/245432bzTue, 14 Mar 2023 00:00:00 +0000Karp, Steven N.Machacek, JohnAn exact characterization of saturation for permutation matrices
https://escholarship.org/uc/item/1dd7c0q9
<p>A 0-1 matrix \(M\) contains a 0-1 matrix pattern \(P\) if we can obtain \(P\) from \(M\) by deleting rows and/or columns and turning arbitrary 1-entries into 0s. The saturation function \(\mathrm{sat}(P,n)\) for a 0-1 matrix pattern \(P\) indicates the minimum number of 1s in an \(n \times n\) 0-1 matrix that does not contain \(P\), but changing any 0-entry into a 1-entry creates an occurrence of \(P\). Fulek and Keszegh recently showed that each pattern has a saturation function either in \(\mathcal{O}(1)\) or in \(\Theta(n)\). We fully classify the saturation functions of permutation matrices.</p><p>Mathematics Subject Classifications: 05D99</p><p>Keywords: Forbidden submatrices, saturation</p>https://escholarship.org/uc/item/1dd7c0q9Tue, 14 Mar 2023 00:00:00 +0000Berendsohn, Benjamin AramMaximum entropy and integer partitions
https://escholarship.org/uc/item/0nw2d8hb
<p>We derive asymptotic formulas for the number of integer partitions with given sums of \(j\)th powers of the parts for \(j\) belonging to a finite, non-empty set \(J \subset \mathbb N\). The method we use is based on the `principle of maximum entropy' of Jaynes. This principle leads to an intuitive variational formula for the asymptotics of the logarithm of the number of constrained partitions as the solution to a convex optimization problem over real-valued functions. Finding the polynomial corrections and leading constant involves two steps: quantifying the error in approximating a discrete optimization problem by a continuous one and proving a multivariate local central limit theorem.</p><p>Mathematics Subject Classifications: 05A17, 05A16, 60F05</p><p>Keywords: Integer partitions, maximum entropy, asymptotic enumeration, local central limit theorem, limit shape</p>https://escholarship.org/uc/item/0nw2d8hbTue, 14 Mar 2023 00:00:00 +0000McKinley, GwenethMichelen, MarcusPerkins, WillVon Staudt constructions for skew-linear and multilinear matroids
https://escholarship.org/uc/item/01q1x044
<p>This paper compares skew-linear and multilinear matroid representations. These are matroids that are representable over division rings and (roughly speaking) invertible matrices, respectively. The main tool is the von Staudt construction, by which we translate our problems to algebra. After giving an exposition of a simple variant of the von Staudt construction we present the following results:</p>Undecidability of several matroid representation problems over division rings. An example of a matroid with an infinite multilinear characteristic set, but which is not multilinear in characteristic \(0\). An example of a skew-linear matroid that is not multilinear. <p> </p><p>Mathematics Subject Classifications: 05B35, 52B40, 14N20, 52C35, 20F10, 03D40</p><p>Keywords: Matroids, division ring representations, subspace arrangements, \(c\)-arrange\-ments, multilinear matroids, von Staudt constructions, word problem, Weyl algebra, Baumslag-Solitar group</p>https://escholarship.org/uc/item/01q1x044Tue, 14 Mar 2023 00:00:00 +0000Kühne, LukasPendavingh, RudiYashfe, GevaOriented matroids and combinatorial neural codes
https://escholarship.org/uc/item/00c6r759
<p>A combinatorial neural code \({\mathscr C}\subseteq 2^{[n]}\) is called convex if it arises as the intersection pattern of convex open subsets of \(\mathbb{R}^d\). We relate the emerging theory of convex neural codes to the established theory of oriented matroids, both with respect to geometry and computational complexity and categorically. For geometry and computational complexity, we show that a code has a realization with convex polytopes if and only if it lies below the code of a representable oriented matroid in the partial order of codes introduced by Jeffs. We show that previously published examples of non-convex codes do not lie below any oriented matroids, and we construct examples of non-convex codes lying below non-representable oriented matroids. By way of this construction, we can apply Mnëv-Sturmfels universality to show that deciding whether a combinatorial code is convex is NP-hard.</p><p>On the categorical side, we show that the map taking an acyclic oriented...https://escholarship.org/uc/item/00c6r759Tue, 14 Mar 2023 00:00:00 +0000Kunin, Alexander B.Lienkaemper, CaitlinRosen, ZviTriangulations, Order Polytopes, and Generalized Snake Posets
https://escholarship.org/uc/item/9rf590vk
<p>This work regards the order polytopes arising from the class of generalized snake posets and their posets of meet-irreducible elements. Among generalized snake posets of the same rank, we characterize those whose order polytopes have minimal and maximal volume. We give a combinatorial characterization of the circuits in related order polytopes and then conclude that all of their triangulations are unimodular. For a generalized snake word, we count the number of flips for the canonical triangulation of these order polytopes. We determine that the flip graph of the order polytope of the poset whose lattice of upper order ideals comes from a ladder is the Cayley graph of a symmetric group. Lastly, we introduce an operation on triangulations called twists and prove that twists preserve regular triangulations.</p><p>Mathematics Subject Classifications: 52B20, 52B05, 52B12, 06A07</p><p>Keywords: Order polytopes, triangulations, flow polytopes, circuits</p>https://escholarship.org/uc/item/9rf590vkWed, 12 Oct 2022 00:00:00 +0000von Bell, MatiasBraun, BenjaminHanely, DerekSerhiyenko, KhrystynaVega, JulianneVindas-Meléndez, Andrés R.Yip, MarthaPeriod collapse in Ehrhart quasi-polynomials of \(\{1,3\}\)-graphs
https://escholarship.org/uc/item/8n44x9vm
<p>A graph whose nodes have degree \(1\) or \(3\) is called a \(\{1,3\}\)-graph. Liu and Osserman associated a polytope to each \(\{1,3\}\)-graph and studied the Ehrhart quasi-polynomials of these polytopes. They showed that the vertices of these polytopes have coordinates in the set \(\{0,\frac14,\frac12,1\}\), which implies that the period of their Ehrhart quasi-polynomials is either \(1, 2\), or \(4\). We show that the period of the Ehrhart quasi-polynomial of these polytopes is 2 if the graph is a tree, the period is at most 2 if the graph is cubic, and the period is \(4\) otherwise. In the process of proving this theorem, several interesting combinatorial and geometric properties of these polytopes were uncovered, arising from the structure of their associated graphs. The tools developed here may find other applications in the study of Ehrhart quasi-polynomials and enumeration problems for other polytopes that arise from graphs. Additionally, we have identified some interesting...https://escholarship.org/uc/item/8n44x9vmWed, 12 Oct 2022 00:00:00 +0000Fernandes, Cristina G.de Pina, José C.Ramírez Alfonsín, Jorge LuisRobins, SinaiDisjoint dijoins for classes of dicuts in finite and infinite digraphs
https://escholarship.org/uc/item/8cz6n02x
<p>A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of a set of edges meeting every non-empty dicut equals the maximum number of disjoint dicuts in that digraph. Such sets are called dijoins. Woodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a directed graph equals the minimum size of a non-empty dicut. We study a modification of this question where we restrict our attention to certain classes of non-empty dicuts, i.e. whether for a class \(\mathfrak{B}\) of dicuts of a directed graph the maximum number of disjoint sets of edges meeting every dicut in \(\mathfrak{B}\) equals the size of a minimum dicut in \(\mathfrak{B}\). In particular, we verify this questions for nested classes of finite dicuts, for the class of dicuts of minimum size, and for classes of infinite dibonds, and we investigate...https://escholarship.org/uc/item/8cz6n02xWed, 12 Oct 2022 00:00:00 +0000Gollin, J. PascalHeuer, KarlStavropoulos, KonstantinosLabelled well-quasi-order for permutation classes
https://escholarship.org/uc/item/8579b1dq
<p>While the theory of labelled well-quasi-order has received significant attention in the graph setting, it has not yet been considered in the context of permutation patterns. We initiate this study here, and show how labelled well quasi order provides a lens through which to view and extend previous well-quasi-order results in the permutation patterns literature. Connections to the graph setting are emphasised throughout. In particular, we establish that a permutation class is labelled well-quasi-ordered if and only if its corresponding graph class is also labelled well-quasi-ordered.</p><p>Mathematics Subject Classifications: 05A05, 06A07</p><p>Keywords: Labelled well-quasi-order, permutation patterns, well-quasi-order</p>https://escholarship.org/uc/item/8579b1dqWed, 12 Oct 2022 00:00:00 +0000Brignall, RobertVatter, VincentIntersecting psi-classes on tropical Hassett spaces
https://escholarship.org/uc/item/6569z31w
<p>We study the intersection of tropical \(\psi\)-classes on tropical heavy/light Hassett spaces, generalising a result of Kerber-Markwig for \(M^{\operatorname{trop}}_{0, n}\). Our computation reveals that the weight of a maximal cone in an intersection has a combinatorial intepretation in terms of the underlying tropical curve and it is always nonnegative. In particular, our result specialises to that, in top dimension, the tropical intersection product coincides with its classical counterpart.</p><p>Mathematics Subject Classifications: 14T90, 14N35</p><p>Keywords: Tropical intersection theory, Hassett spaces, \(\psi\)-classes</p>https://escholarship.org/uc/item/6569z31wWed, 12 Oct 2022 00:00:00 +0000Hahn, Marvin AnasLi, ShiyueConvex subspaces of Lie incidence geometries
https://escholarship.org/uc/item/632884hc
<p>We classify the convex subspaces of all hexagonic Lie incidence geometries (among which all long root geometries of spherical Tits-buildings). We perform a similar classification for most other Lie incidence geometries of spherical Tits-buildings, in particular for all projective and polar Grassmannians, and for exceptional Grassmannians of diameter at most 3.</p><p>Mathematics Subject Classifications: 51E24</p><p>Keywords: Buildings, parapolar spaces, long root geometries, hexagonal Lie incidence geometries</p>https://escholarship.org/uc/item/632884hcWed, 12 Oct 2022 00:00:00 +0000Meulewaeter, JeroenVan Maldeghem, HendrikLinear-sized independent sets in random cographs and increasing subsequences in separable permutations
https://escholarship.org/uc/item/23340676
<p>This paper is interested in independent sets (or equivalently, cliques) in uniform random cographs. We also study their permutation analogs, namely, increasing subsequences in uniform random separable permutations. First, we prove that, with high probability as \(n\) gets large, the largest independent set in a uniform random cograph with \(n\) vertices has size \(o(n)\). This answers a question of Kang, McDiarmid, Reed and Scott. Using the connection between graphs and permutations via inversion graphs, we also give a similar result for the longest increasing subsequence in separable permutations. These results are proved using the self-similarity of the Brownian limits of random cographs and random separable permutations, and actually apply more generally to all families of graphs and permutations with the same limit. Second, and unexpectedly given the above results, we show that for \(\beta >0\) sufficiently small, the expected number of independent sets of size \(\beta...https://escholarship.org/uc/item/23340676Wed, 12 Oct 2022 00:00:00 +0000Bassino, FrédériqueBouvel, MathildeDrmota, MichaelFéray, ValentinGerin, LucasMaazoun, MickaëlPierrot, AdelinePop-stack-sorting for Coxeter groups
https://escholarship.org/uc/item/0n9037xd
<p>Let \(W\) be an irreducible Coxeter group. We define the Coxeter pop-stack-sorting operator \(\mathsf{Pop}:W\to W\) to be the map that fixes the identity element and sends each nonidentity element \(w\) to the meet of the elements covered by \(w\) in the right weak order. When \(W\) is the symmetric group \(S_n\), \(\mathsf{Pop}\) coincides with the pop-stack-sorting map. Generalizing a theorem about the pop-stack-sorting map due to Ungar, we prove that \[\sup\limits_{w\in W}\left|O_{\mathsf{Pop}}(w)\right|=h,\] where \(h\) is the Coxeter number of \(W\) (with \(h=\infty\) if \(W\) is infinite) and \(O_f(w)\) denotes the forward orbit of \(w\) under a map \(f\). When \(W\) is finite, this result is equivalent to the statement that the maximum number of terms appearing in the Brieskorn normal form of an element of \(W\) is \(h-1\). More generally, we define a map \(f:W\to W\) to be compulsive if for every \(w\in W\), \(f(w)\) is less than or equal to \(\mathsf{Pop}(w)\) in the...https://escholarship.org/uc/item/0n9037xdWed, 12 Oct 2022 00:00:00 +0000Defant, ColinInducibility and universality for trees
https://escholarship.org/uc/item/9gd4317z
<p>We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive \(\varepsilon_1\) and \(\varepsilon_2\) such that every tree that is neither a path nor a star has inducibility at most \(1-\varepsilon_1\), where the inducibility of a tree \(T\) is defined as the maximum limit density of \(T\), and that there are infinitely many trees with inducibility at least \(\varepsilon_2\). Finally, we construct a universal sequence of trees; that is, a sequence in which the limit density of any tree is positive.</p><p>Mathematics Subject Classifications: 05C05, 05C35</p><p>Keywords: Trees, inducibility, graph density</p>https://escholarship.org/uc/item/9gd4317zTue, 11 Oct 2022 00:00:00 +0000Chan, Timothy F. N.Král', DanielMohar, BojanWood, David R.The bipermutahedron
https://escholarship.org/uc/item/8gh2s5vz
<p>The harmonic polytope and the bipermutahedron are two related polytopes that arose in the Lagrangian geometry of matroids. We study the bipermutahedron. We show that it is a simple polytope whose faces are in bijection with the vertex-labeled and edge-labeled multigraphs with no isolated vertices; the generating function for its \(f\)-vector is a simple evaluation of the three variable Rogers-Ramanujan function. We introduce the biEulerian polynomial, which counts bipermutations according to their number of descents, and equals the \(h\)-polynomial of the bipermutahedral fan. We construct a unimodular triangulation of the product \(\Delta \times \cdots \times \Delta\) of triangles that is combinatorially equivalent to (the triple cone over) the bipermutahedral fan. Ehrhart theory then gives us a formula for the biEulerian polynomial, which we use to show that this polynomial is real-rooted and that the \(h\)-vector of the bipermutahedral fan is log-concave and unimodal. We...https://escholarship.org/uc/item/8gh2s5vzTue, 11 Oct 2022 00:00:00 +0000Ardila, FedericoQuasi-polar spaces
https://escholarship.org/uc/item/8ff3j88m
<p>Quasi-polar spaces are sets of points having the same intersection numbers with respect to hyperplanes as classical polar spaces. Non-classical examples of quasi-quadrics have been constructed using a technique called {\em pivoting} in a paper by De Clerck, Hamilton, O'Keefe and Penttila. We introduce a more general notion of pivoting, called switching, and also extend this notion to Hermitian polar spaces. The main result of this paper studies the switching technique in detail by showing that, for \(q\geq 4\), if we modify the points of a hyperplane of a polar space to create a quasi-polar space, the only thing that can be done is pivoting. The cases \(q=2\) and \(q=3\) play a special role for parabolic quadrics and are investigated in detail. Furthermore, we give a construction for quasi-polar spaces obtained from pivoting multiple times. Finally, we focus on the case of parabolic quadrics in even characteristic and determine under which hypotheses the existence of a nucleus...https://escholarship.org/uc/item/8ff3j88mTue, 11 Oct 2022 00:00:00 +0000Schillewaert, JeroenVan de Voorde, GeertruiPolynomial removal lemmas for ordered graphs
https://escholarship.org/uc/item/7xw1r1rw
<p>A recent result of Alon, Ben-Eliezer and Fischer establishes an induced removal lemma for ordered graphs. That is, if \(F\) is an ordered graph and \(\varepsilon›0\), then there exists \(\delta_{F}(\varepsilon)›0\) such that every \(n\)-vertex ordered graph \(G\) containing at most \(\delta_{F}(\varepsilon) n^{v(F)}\) induced copies of \(F\) can be made induced \(F\)-free by adding/deleting at most \(\varepsilon n^2\) edges. We prove that \(\delta_{F}(\varepsilon)\) can be chosen to be a polynomial function of \(\varepsilon\) if and only if \(|V(F)|=2\), or \(F\) is the ordered graph with vertices \(x‹y‹z\) and edges \(\{x,y\},\{x,z\}\) (up to complementation and reversing the vertex order). We also discuss similar problems in the non-induced case.</p><p>Mathematics Subject Classifications: 05C35, 05C75</p><p>Keywords: Ordered graph, removal lemma</p>https://escholarship.org/uc/item/7xw1r1rwTue, 11 Oct 2022 00:00:00 +0000Gishboliner, LiorTomon, IstvánSchubert polynomials as projections of Minkowski sums of Gelfand-Tsetlin polytopes
https://escholarship.org/uc/item/4c6659v6
<p>Gelfand-Tsetlin polytopes are classical objects in algebraic combinatorics arising in the representation theory of \(\mathfrak{gl}_n(\mathbb{C})\). The integer point transform of the Gelfand-Tsetlin polytope \(\mathrm{GT}(\lambda)\) projects to the Schur function \(s_{\lambda}\). Schur functions form a distinguished basis of the ring of symmetric functions; they are also special cases of Schubert polynomials \(\mathfrak{S}_{w}\) corresponding to Grassmannian permutations. For any permutation \(w \in S_n\) with column-convex Rothe diagram, we construct a polytope \(\mathcal{P}_{w}\) whose integer point transform projects to the Schubert polynomial \(\mathfrak{S}_{w}\). Such a construction has been sought after at least since the construction of twisted cubes by Grossberg and Karshon in 1994, whose integer point transforms project to Schubert polynomials \(\mathfrak{S}_{w}\) for all \(w \in S_n\). However, twisted cubes are not honest polytopes; rather one can think of them as...https://escholarship.org/uc/item/4c6659v6Tue, 11 Oct 2022 00:00:00 +0000Liu, Ricky IniMészáros, KarolaDizier, Avery St.The polyhedral tree complex
https://escholarship.org/uc/item/3mx155d7
<p>The tree complex is a simplicial complex defined in recent work of Belk, Lanier, Margalit, and Winarski with applications to mapping class groups and complex dynamics. This article introduces a connection between this setting and the convex polytopes known as associahedra and cyclohedra. Specifically, we describe a characterization of these polytopes using planar embeddings of trees and show that the tree complex is the barycentric subdivision of a polyhedral cell complex for which the cells are products of associahedra and cyclohedra.</p><p>Mathematics Subject Classifications: 05C05, 05C10, 20F65, 52B11</p><p>Keywords: Associahedra, cyclohedra, planar trees, mapping class groups</p>https://escholarship.org/uc/item/3mx155d7Tue, 11 Oct 2022 00:00:00 +0000Dougherty, MichaelMinimizing cycles in tournaments and normalized \(q\)-norms
https://escholarship.org/uc/item/2rm2x1nm
<p>Akin to the Erdős-Rademacher problem, Linial and Morgenstern made the following conjecture in tournaments: for any \(d\in (0,1]\), among all \(n\)-vertex tournaments with \(d\binom{n}{3}\) many 3-cycles, the number of 4-cycles is asymptotically minimized by a special random blow-up of a transitive tournament. Recently, Chan, Grzesik, Král' and Noel introduced spectrum analysis of adjacency matrices of tournaments in this study, and confirmed this for \(d\geq 1/36\). In this paper, we investigate the analogous problem of minimizing the number of cycles of a given length. We prove that for integers \(\ell\not\equiv 2\mod 4\), there exists some constant \(c_\ell>0\) such that if \(d\geq 1-c_\ell\), then the number of \(\ell\)-cycles is also asymptotically minimized by the same extremal examples. In doing so, we answer a question of Linial and Morgenstern about minimizing the \(q\)-norm of a probabilistic vector with given \(p\)-norm for integers \(q>p>1\). For integers...https://escholarship.org/uc/item/2rm2x1nmTue, 11 Oct 2022 00:00:00 +0000Ma, JieTang, TianyunLarge expanders in high genus unicellular maps
https://escholarship.org/uc/item/2q57v46b
<p>We study large uniform random maps with one face whose genus grows linearly with the number of edges. They can be seen as a model of discrete hyperbolic geometry. In the past, several of these hyperbolic geometric features have been discovered, such as their local limit or their logarithmic diameter. In this work, we show that with high probability such a map contains a very large induced subgraph that is an expander.</p><p>Mathematics Subject Classifications: 05C10, 05C48, 60C05, 60D05</p><p>Keywords: Combinatorial maps, high genus, expander graphs</p>https://escholarship.org/uc/item/2q57v46bTue, 11 Oct 2022 00:00:00 +0000Louf, BaptisteOn characters of wreath products
https://escholarship.org/uc/item/4r2614sp
<p>A character identity which relates irreducible character values of the hyperoctahedral group \(B_n\) to those of the symmetric group \(S_{2n}\) was recently proved by Lübeck and Prasad. Their proof is algebraic and involves Lie theory. We present a short combinatorial proof of this identity, as well as a generalization to other wreath products.</p><p>Mathematics Subject Classifications: 20C30, 20E22, 05E10</p><p>Keywords: Character identity, wreath product, partition, Murnaghan-Nakayama rule, colored permutations</p>https://escholarship.org/uc/item/4r2614spMon, 27 Jun 2022 00:00:00 +0000Adin, Ron M.Roichman, YuvalA refinement of the Murnaghan-Nakayama rule by descents for border strip tableaux
https://escholarship.org/uc/item/9cs438vb
<p>Lusztig's fake degree is the generating polynomial for the major index of standard Young tableaux of a given shape. Results of Springer (1974) and James & Kerber (1984) imply that, mysteriously, its evaluation at a \(k\)-th primitive root of unity yields the number of border strip tableaux with all strips of size \(k\), up to sign. This is essentially the special case of the Murnaghan-Nakayama rule for evaluating an irreducible character of the symmetric group at a rectangular partition. We refine this result to standard Young tableaux and border strip tableaux with a given number of descents. To do so, we introduce a new statistic for border strip tableaux, extending the classical definition of descents in standard Young tableaux. Curiously, it turns out that our new statistic is very closely related to a descent set for tuples of standard Young tableaux appearing in the quasisymmetric expansion of LLT polynomials given by Haglund, Haiman and Loehr (2005).</p><p>Mathematics...https://escholarship.org/uc/item/9cs438vbSat, 25 Jun 2022 00:00:00 +0000Pfannerer, StephanTwin-width II: small classes
https://escholarship.org/uc/item/9cs265b9
<p>The recently introduced twin-width of a graph \(G\) is the minimum integer \(d\) such that \(G\) has a \(d\)-contraction sequence, that is, a sequence of \(\left| V(G) \right|-1\) iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most \(d\), where a red edge appears between two sets of identified vertices if they are not homogeneous in \(G\) (not fully adjacent nor fully non-adjacent). We show that if a graph admits a \(d\)-contraction sequence, then it also has a linear-arity tree of \(f(d)\)-contractions, for some function \(f\). Informally if we accept to worsen the twin-width bound, we can choose the next contraction from a set of \(\Theta(\left| V(G) \right|)\) pairwise disjoint pairs of vertices. This has two main consequences. First it permits to show that every bounded twin-width class is small, i.e., has at most \(n!c^n\) graphs labeled by \([n]\), for some constant \(c\). This unifies and extends the...https://escholarship.org/uc/item/9cs265b9Sat, 25 Jun 2022 00:00:00 +0000Bonnet, ÉdouardGeniet, ColinKim, Eun JungThomassé, StéphanWatrigant, RémiTutte short exact sequences of graphs
https://escholarship.org/uc/item/9297n4tn
<p>We associate two modules, the \(G\)-parking critical module and the toppling critical module, to an undirected connected graph \(G\). The \(G\)-parking critical module and the toppling critical module are canonical modules (with suitable twists) of quotient rings of the well-studied \(G\)-parking function ideal and the toppling ideal, respectively. For each critical module, we establish a Tutte-like short exact sequence relating the modules associated to \(G\), an edge contraction \(G/e\) and an edge deletion \(G \setminus e\) (\(e\) is a non-bridge). We obtain purely combinatorial consequences of Tutte short exact sequences. For instance, we reprove a theorem of Merino that the critical polynomial of a graph is an evaluation of its Tutte polynomial, and relate the vanishing of certain combinatorial invariants (the number of acyclic orientations on connected partition graphs satisfying a unique sink property) of \(G/e\) to the equality of the corresponding invariants of \(G\)...https://escholarship.org/uc/item/9297n4tnSat, 25 Jun 2022 00:00:00 +0000Manjunath, MadhusudanFrom weakly separated collections to matroid subdivisions
https://escholarship.org/uc/item/9265777p
<p>We study arrangements of slightly skewed tropical hyperplanes, called blades by A. Ocneanu, on the vertices of a hypersimplex \(\Delta_{k,n}\), and we investigate the resulting induced polytopal subdivisions. We show that placing a blade on a vertex \(e_J\) induces an \(\ell\)-split matroid subdivision of \(\Delta_{k,n}\), where \(\ell\) is the number of cyclic intervals in the \(k\)-element subset \(J\). We prove that a given collection of \(k\)-element subsets is weakly separated, in the sense of the work of Leclerc and Zelevinsky on quasicommuting families of quantum minors, if and only if the arrangement of the blade \(((1,2,\ldots, n))\) on the corresponding vertices of \(\Delta_{k,n}\) induces a matroid (in fact, a positroid) subdivision. In this way we obtain a compatibility criterion for (planar) multi-splits of a hypersimplex, generalizing the rule known for 2-splits. We study in an extended example a matroidal arrangement of six blades on the vertices \(\Delta_{3,7}\)....https://escholarship.org/uc/item/9265777pSat, 25 Jun 2022 00:00:00 +0000Early, NickHigh-dimensional tennis balls
https://escholarship.org/uc/item/8bs4n5hc
<p>We show that there exist constants \(\alpha,\epsilon>0\) such that for every positive integer \(n\) there is a continuous odd function \(f:S^m\to S^n\), with \(m\geq \alpha n\), such that the \(\epsilon\)-expansion of the image of \(f\) does not contain a great circle. This result is motivated by a conjecture of Vitali Milman about well-complemented almost Euclidean subspaces of spaces uniformly isomorphic to \(\ell_2^n\).</p><p>Mathematics Subject Classifications: 46B09, 60C05</p><p>Keywords: Anti-Ramsey, antipodal subsphere</p>https://escholarship.org/uc/item/8bs4n5hcSat, 25 Jun 2022 00:00:00 +0000Gowers, TimothyWyczesany, KatarzynaSaturation of Newton polytopes of type A and D cluster variables
https://escholarship.org/uc/item/7x0979ct
<p>We study Newton polytopes for cluster variables in cluster algebras \(\mathcal{A}(\Sigma)\) of types A and D. A famous property of cluster algebras is the Laurent phenomenon: each cluster variable can be written as a Laurent polynomial in the cluster variables of the initial seed \(\Sigma\). The cluster variable Newton polytopes are the Newton polytopes of these Laurent polynomials. We show that if \(\Sigma\) has principal coefficients or boundary frozen variables, then all cluster variable Newton polytopes are saturated. We also characterize when these Newton polytopes are empty; that is, when they have no non-vertex lattice points.</p><p>Mathematics Subject Classifications: 13F60, 52B20</p><p>Keywords: Cluster algebras, Newton polytopes, snake graphs</p>https://escholarship.org/uc/item/7x0979ctSat, 25 Jun 2022 00:00:00 +0000Mattoo, AmalSherman-Bennett, MelissaThe metric space of limit laws for \(q\)-hook formulas
https://escholarship.org/uc/item/7p7557d3
<p>Billey-Konvalinka-Swanson studied the asymptotic distribution of the coefficients of Stanley's \(q\)-hook length formula, or equivalently the major index on standard tableaux of straight shape and certain skew shapes. We extend those investigations to Stanley's \(q\)-hook-content formula related to semistandard tableaux and \(q\)-hook length formulas of Björner-Wachs related to linear extensions of labeled forests. We show that, while their coefficients are "generically" asymptotically normal, there are uncountably many non-normal limit laws. More precisely, we introduce and completely describe the compact closure of the metric space of distributions of these statistics in several regimes. The additional limit distributions involve generalized uniform sum distributions which are topologically parameterized by certain decreasing sequence spaces with bounded \(2\)-norm. The closure of these distributions in the Lévy metric gives rise to the space of DUSTPAN distributions. As...https://escholarship.org/uc/item/7p7557d3Sat, 25 Jun 2022 00:00:00 +0000Billey, Sara C.Swanson, Joshua P.Generalised Howe duality and injectivity of induction: the symplectic case
https://escholarship.org/uc/item/79s5h3hd
<p>We study the symplectic Howe duality using two new and independent combinatorial methods: via determinantal formulae on the one hand, and via (bi)crystals on the other hand. The first approach allows us to establish a generalised version where weight multiplicities are replaced by branching coefficients. In turn, this generalised Howe duality is used to prove the injectivity of induction for Levi branchings as previously conjectured by the last two authors.</p><p>Mathematics Subject Classifications: 17B10, 17B37, 05E05, 05E10</p><p>Keywords: Lie algebras, representation theory, Schur-Weyl duality, Howe duality, crystals, Schur functions, induced modules</p>https://escholarship.org/uc/item/79s5h3hdSat, 25 Jun 2022 00:00:00 +0000Gerber, ThomasGuilhot, JérémieLecouvey, CédricCounting lattice paths by crossings and major index I: the corner-flipping bijections
https://escholarship.org/uc/item/58x811km
<p>We solve two problems regarding the enumeration of lattice paths in \(\mathbb{Z}^2\) with steps \((1,1)\) and \((1,-1)\) with respect to the major index, defined as the sum of the positions of the valleys, and to the number of certain crossings. The first problem considers crossings of a single path with a fixed horizontal line. The second one counts pairs of paths with respect to the number of times they cross each other. Our proofs introduce lattice path bijections with convenient visual descriptions, and the answers are given by remarkably simple formulas involving \(q\)-binomial coefficients.</p><p>Mathematics Subject Classifications: 05A19, 05A15, 05A30</p><p>Keywords: Lattice path, major index, crossing, valley, bijection</p>https://escholarship.org/uc/item/58x811kmSat, 25 Jun 2022 00:00:00 +0000Elizalde, SergiMultiplication theorems for self-conjugate partitions
https://escholarship.org/uc/item/4pd822pc
<p>In 2011, Han and Ji proved addition-multiplication theorems for integer partitions, from which they derived modular analogues of many classical identities involving hook-length. In the present paper, we prove addition-multiplication theorems for the subset of self-conjugate partitions. Although difficulties arise due to parity questions, we are almost always able to include the BG-rank introduced by Berkovich and Garvan. This gives us as consequences many self-conjugate modular versions of classical hook-lengths identities for partitions. Our tools are mainly based on fine properties of the Littlewood decomposition restricted to self-conjugate partitions.</p><p>Mathematics Subject Classifications: 05A15, 05A17, 05A19, 05E05, 05E10, 11P81</p><p>Keywords: Hook-length formulas, BGP-ranks, Integers partitions, Littlewood decomposition, core partitions</p>https://escholarship.org/uc/item/4pd822pcSat, 25 Jun 2022 00:00:00 +0000Wahiche, DavidA note on saturation for \(k\)-wise intersecting families
https://escholarship.org/uc/item/30f8m0xh
<p>A family \(\mathcal{F}\) of subsets of \(\{1,\dots,n\}\) is called \(k\)-wise intersecting if any \(k\) members of \(\mathcal{F}\) have non-empty intersection, and it is called maximal \(k\)-wise intersecting if no family strictly containing \(\mathcal{F}\) satisfies this condition. We show that for each \(k\geq 2\) there is a maximal \(k\)-wise intersecting family of size \(O(2^{n/(k-1)})\). Up to a constant factor, this matches the best known lower bound, and answers an old question of Erdős and Kleitman, recently studied by Hendrey, Lund, Tompkins, and Tran.</p><p>Mathematics Subject Classifications: 05D05</p><p>Keywords: Intersecting family, saturation, set system</p>https://escholarship.org/uc/item/30f8m0xhSat, 25 Jun 2022 00:00:00 +0000Janzer, BarnabásMonotone subsets in lattices and the Schensted shape of a Sós permutation
https://escholarship.org/uc/item/18b556r3
<p>For a fixed irrational number \(\alpha\) and \(n\in \mathbb{N}\), we look at the shape of the sequence \((f(1),\ldots,f(n))\) after Schensted insertion, where \(f(i) = \alpha i \mod 1\). Our primary result is that the boundary of the Schensted shape is approximated by a piecewise linear function with at most two slopes. This piecewise linear function is explicitly described in terms of the continued fraction expansion for \(\alpha\). Our results generalize those of Boyd and Steele, who studied longest monotone subsequences. Our proofs are based on a careful analysis of monotone sets in two-dimensional lattices.</p><p>Mathematics Subject Classifications: 05A05, 11H06, 11B57, 11K06</p><p>Keywords: Longest increasing subsequence, Schensted shape, geometry of numbers, S\'os permutations</p>https://escholarship.org/uc/item/18b556r3Sat, 25 Jun 2022 00:00:00 +0000Liechty, KarlPetersen, T. Kyle