http://www.rssboard.org/rss-specification720Recent combinatorial_theory items
https://escholarship.org/uc/combinatorial_theory/rss
Recent eScholarship items from Combinatorial TheoryMon, 30 Jan 2023 09:26:25 +0000Triangulations, 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 +0000Period 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 +0000Disjoint 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 +0000Labelled 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 +0000Intersecting 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 +0000Convex 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 +0000Linear-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 +0000Pop-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 +0000Inducibility 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 +0000The 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 +0000Quasi-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 +0000Polynomial 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 +0000Schubert 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 +0000The 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 +0000Minimizing 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 +0000Large 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 +0000On 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 +0000A 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 +0000Twin-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 +0000Tutte 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 +0000From 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 +0000High-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 +0000Saturation 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 +0000The 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 +0000Generalised 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 +0000Counting 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 +0000Multiplication 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 +0000A 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 +0000Monotone 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 +0000The hull metric on Coxeter groups
https://escholarship.org/uc/item/0hz0g20z
<p>We reinterpret an inequality, due originally to Sidorenko, for linear extensions of posets in terms of convex subsets of the symmetric group \(\mathfrak{S}_n\). We conjecture that the analogous inequalities hold in arbitrary (not-necessarily-finite) Coxeter groups \(W\), and prove this for the hyperoctahedral groups \(B_n\) and all right-angled Coxeter groups. Our proof for \(B_n\) (and new proof for \(\mathfrak{S}_n\)) use a combinatorial insertion map closely related to the well-studied promotion operator on linear extensions; this map may be of independent interest. We also note that the inequalities in question can be interpreted as a triangle inequalities, so that convex hulls can be used to define a new invariant metric on \(W\) whenever our conjecture holds. Geometric properties of this metric are an interesting direction for future research.</p><p>Mathematics Subject Classifications: 05A20, 05C12, 05E16, 20F55</p><p>Keywords: Linear extension, promotion, Coxeter group,...https://escholarship.org/uc/item/0hz0g20zSat, 25 Jun 2022 00:00:00 +0000Polynomiality properties of tropical refined invariants
https://escholarship.org/uc/item/5h52m8t6
<p>Tropical refined invariants of toric surfaces constitute a fascinating interpolation between real and complex enumerative geometries via tropical geometry. They were originally introduced by Block and Göttsche, and further extended by Göttsche and Schroeter in the case of rational curves. In this paper, we study the polynomial behavior of coefficients of these tropical refined invariants. We prove that coefficients of small codegree are polynomials in the Newton polygon of the curves under enumeration, when one fixes the genus of the latter. This provides a surprising reappearance, in a dual setting, of the so-called node polynomials and the Göttsche conjecture. Our methods, based on floor diagrams introduced by Mikhalkin and the first author, are entirely combinatorial. Although the combinatorial treatment needed here is different, we follow the overall strategy designed by Fomin and Mikhalkin and further developed by Ardila and Block. Hence our results may suggest phenomena...https://escholarship.org/uc/item/5h52m8t6Wed, 22 Jun 2022 00:00:00 +0000Sequence positivity through numeric analytic continuation: uniqueness of the Canham model for biomembranes
https://escholarship.org/uc/item/3hx5h6ct
<p>We prove solution uniqueness for the genus one Canham variational problem arising in the shape prediction of biomembranes. The proof builds on a result of Yu and Chen that reduces the variational problem to proving positivity of a sequence defined by a linear recurrence relation with polynomial coefficients. We combine rigorous numeric analytic continuation of D-finite functions with classic bounds from singularity analysis to derive an effective index where the asymptotic behaviour of the sequence, which is positive, dominates the sequence behaviour. Positivity of the finite number of remaining terms is then checked separately.</p><p>Mathematics Subject Classifications: 05A16, 68Q40, 30B40</p><p>Keywords: Analytic combinatorics, D-finite, P-recursive, positivity, Canham model</p>https://escholarship.org/uc/item/3hx5h6ctWed, 22 Jun 2022 00:00:00 +0000\(F\)- and \(H\)-triangles for \(\nu\)-associahedra
https://escholarship.org/uc/item/2vq6z17j
<p>For any northeast path \(\nu\), we define two bivariate polynomials associated with the \(\nu\)-associahedron: the \(F\)- and the \(H\)-triangle. We prove combinatorially that we can obtain one from the other by an invertible transformation of variables. These polynomials generalize the classical \(F\)- and \(H\)-triangles of F. Chapoton in type \(A\). Our proof is completely new and has the advantage of providing a combinatorial explanation of the relation between the \(F\)- and \(H\)-triangle.</p><p>Mathematics Subject Classifications: 05E45, 52B05</p><p>Keywords: \(\nu\)-Tamari lattice, \(\nu\)-associahedron, \(F\)-triangle, \(H\)-triangle</p>https://escholarship.org/uc/item/2vq6z17jWed, 22 Jun 2022 00:00:00 +0000On the Okounkov-Olshanski formula for standard tableaux of skew shapes
https://escholarship.org/uc/item/9zx5x4ck
<p>The classical hook length formula counts the number of standard tableaux of straight shapes. In 1996, Okounkov and Olshanski found a positive formula for the number of standard Young tableaux of a skew shape. We prove various properties of this formula, including three determinantal formulas for the number of nonzero terms, an equivalence between the Okounkov-Olshanski formula and another skew tableaux formula involving Knutson-Tao puzzles, and two \(q\)-analogues for reverse plane partitions, which complement work by Stanley and Chen for semistandard tableaux. We also give several reformulations of the formula, including two in terms of the excited diagrams appearing in a more recent skew tableaux formula by Naruse. Lastly, for thick zigzag shapes we show that the number of nonzero terms is given by a determinant of the Genocchi numbers and improve on known upper bounds by Morales-Pak-Panova on the number of standard tableaux of these shapes.</p><p>Mathematics Subject Classifications:...https://escholarship.org/uc/item/9zx5x4ckWed, 23 Mar 2022 00:00:00 +0000On the homology of independence complexes
https://escholarship.org/uc/item/9r20x01z
<p>The independence complex \(\mathrm{Ind}(G)\) of a graph \(G\) is the simplicial complex formed by its independent sets of vertices. We introduce a deformation of the simplicial chain complex of \(\mathrm{Ind}(G)\) that gives rise to a spectral sequence which contains on its first page the homology groups of the independence complexes of \(G\) and various subgraphs of \(G\), obtained by removing independent sets together with their neighborhoods. We show how this can be used to study the homology of \(\mathrm{Ind}(G)\). Furthermore, a careful investigation of the sequence's first page exhibits a relation between the cardinality of maximal independent sets in \(G\) and the vanishing of certain homology groups of independence complexes of subgraphs of \(G\). We show that it holds for all paths and cycles.</p><p>Mathematics Subject Classifications: 05C69, 55U10</p>https://escholarship.org/uc/item/9r20x01zWed, 23 Mar 2022 00:00:00 +0000Even circuits in oriented matroids
https://escholarship.org/uc/item/95h763tz
<p>In this paper we generalise the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. We define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then we show that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. Our main result is a precise characterisation of the class of non-even oriented cographic matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen.</p><p>Mathematics Subject Classifications: 05B35, 05C20, 05C70, 05C75, 05C83, 05C85, 52C40</p>https://escholarship.org/uc/item/95h763tzWed, 23 Mar 2022 00:00:00 +0000Linear spaces embedded into projective spaces via Baer sublines
https://escholarship.org/uc/item/7r95048p
<p>Every nontrivial linear space embedded in a Pappian projective space such that the blocks of the linear space are projectively equivalent Baer sublines with respect to a separable quadratic field extension is either a Baer subspace, or a Hermitian unital.</p><p>Mathematics Subject Classifications: 51A45, 51E10</p>https://escholarship.org/uc/item/7r95048pWed, 23 Mar 2022 00:00:00 +0000A rectangular additive convolution for polynomials
https://escholarship.org/uc/item/75t2b1bw
<p>Motivated by the study of singular values of random rectangular matrices, we define and study the rectangular additive convolution of polynomials with nonnegative real roots. Our definition directly generalizes the asymmetric additive convolution introduced by Marcus, Spielman and Srivastava (2015), and our main theorem gives the corresponding generalization of the bound on the largest root from that paper. The main tool used in the analysis is a differential operator derived from the "rectangular Cauchy transform" introduced by Benaych-Georges (2009). The proof is inductive, with the base case requiring a new nonasymptotic bound on the Cauchy transform of Gegenbauer polynomials which may be of independent interest.</p><p>Mathematics Subject Classifications: 26C10, 33C45</p>https://escholarship.org/uc/item/75t2b1bwWed, 23 Mar 2022 00:00:00 +0000Minuscule analogues of the plane partition periodicity conjecture of Cameron and Fon-Der-Flaass
https://escholarship.org/uc/item/6ws3v6xn
<p>Let \(P\) be a graded poset of rank \(r\) and let \(\mathbf{c}\) be a \(c\)-element chain. A plane partition on \(P\) is an order ideal of \(P \times \mathbf{c}\). For an order ideal \(I\) of \(P \times \mathbf{c}\), its rowmotion \(\psi(I)\) is the smallest ideal containing the minimal elements of the complementary filter of \(I\). The map \(\psi\) defines invertible dynamics on the set of plane partitions. We say that \(P\) has NRP (`not relatively prime') rowmotion if no \(\psi\)-orbit has cardinality relatively prime to \(r+c+1\). In recent work, R. Patrias and the author (2020) proved a 1995 conjecture of P. Cameron and D. Fon-Der-Flaass by establishing NRP rowmotion for the product \(P = \mathbf{a} \times \mathbf{b}\) of two chains, the poset whose order ideals correspond to the Schubert varieties of a Grassmann variety \(\mathrm{Gr}_a(\mathbb{C}^{a+b})\) under containment. Here, we initiate the general study of posets with NRP rowmotion. Our first main result establishes...https://escholarship.org/uc/item/6ws3v6xnWed, 23 Mar 2022 00:00:00 +0000The \(q\)-analog of the Markoff injectivity conjecture over the language of a balanced sequence
https://escholarship.org/uc/item/6pn049mp
<p>The Markoff injectivity conjecture states that \(w\mapsto\mu(w)_{12}\) is injective on the set of Christoffel words where \(\mu:\{\mathtt{0},\mathtt{1}\}^*\to\mathrm{SL}_2(\mathbb{Z})\) is a certain homomorphism and \(M_{12}\) is the entry above the diagonal of a \(2\times2\) matrix \(M\). Recently, Leclere and Morier-Genoud (2021) proposed a \(q\)-analog \(\mu_q\) of \(\mu\) such that \(\mu_{q}(w)_{12}|_{q=1}=\mu(w)_{12}\) is the Markoff number associated to the Christoffel word \(w\) when evaluated at \(q=1\). We show that there exists an order \(<_{radix}\) on \(\{\mathtt{0},\mathtt{1}\}^*\) such that for every balanced sequence \(s \in \{\mathtt{0},\mathtt{1}\}^\mathbb{Z}\) and for all factors \(u, v\) in the language of \(s\) with \(u <_{radix} v\), the difference \(\mu_q(v)_{12} - \mu_q(u)_{12}\) is a nonzero polynomial of indeterminate \(q\) with nonnegative integer coefficients. Therefore, the map \(u\mapsto\mu_q(u)_{12}\) is injective over the language of a balanced...https://escholarship.org/uc/item/6pn049mpWed, 23 Mar 2022 00:00:00 +0000The non-existence of block-transitive subspace designs
https://escholarship.org/uc/item/66t045d3
<p>Let \(q\) be a prime power and \(V\cong\mathbb{F}_q^d\). A \(t\)-\((d,k,\lambda)_q\) design, or simply a subspace design, is a pair \(\mathcal{D}=(V,\mathcal{B})\), where \(\mathcal{B}\) is a subset of the set of all \(k\)-dimensional subspaces of \(V\), with the property that each \(t\)-dimensional subspace of \(V\) is contained in precisely \(\lambda\) elements of \(\mathcal{B}\). Subspace designs are the \(q\)-analogues of balanced incomplete block designs. Such a design is called block-transitive if its automorphism group \(\mathrm{Aut}(\mathcal{D})\) acts transitively on \(\mathcal{B}\). It is shown here that if \(t\geq 2\) and \(\mathcal{D}\) is a block-transitive \(t\)-\((d,k,\lambda)_q\) design then \(\mathcal{D}\) is trivial, that is, \(\mathcal{B}\) is the set of all \(k\)-dimensional subspaces of \(V\).</p><p>Mathematics Subject Classifications: 05E18, 05B99</p>https://escholarship.org/uc/item/66t045d3Wed, 23 Mar 2022 00:00:00 +0000Maximal cocliques in the generating graphs of the alternating and symmetric groups
https://escholarship.org/uc/item/6152c771
<p>The generating graph \(\Gamma(G)\) of a finite group \(G\) has vertex set the non-identity elements of \(G\), with two elements adjacent exactly when they generate \(G\). A coclique in a graph is an empty induced subgraph, so a coclique in \(\Gamma(G)\) is a subset of \(G\) such that no pair of elements generate \(G\). A coclique is maximal if it is contained in no larger coclique. It is easy to see that the non-identity elements of a maximal subgroup of \(G\) form a coclique in \(\Gamma(G)\), but this coclique need not be maximal. In this paper we determine when the intransitive maximal subgroups of \(\mathrm{S}_n\) and \(\mathrm{A}_n\) are maximal cocliques in the generating graph. In addition, we prove a conjecture of Cameron, Lucchini, and Roney-Dougal in the case of \(G = \mathrm{A}_n\) and \(\mathrm{S}_n\), when \(n\) is prime and \({n \neq \frac{q^d-1}{q-1}}\) for all prime powers \(q\) and \(d \geq 2\). Namely, we show that two elements of \(G\) have identical sets...https://escholarship.org/uc/item/6152c771Wed, 23 Mar 2022 00:00:00 +0000Odd diagrams, Bruhat order, and pattern avoidance
https://escholarship.org/uc/item/5pj7s2gq
<p>The odd diagram of a permutation is a subset of the classical diagram with additional parity conditions. In this paper, we study classes of permutations with the same odd diagram, which we call odd diagram classes. First, we prove a conjecture relating odd diagram classes and 213- and 312-avoiding permutations. Secondly, we show that each odd diagram class is a Bruhat interval. Instrumental to our proofs is an explicit description of the Bruhat edges that link permutations in a class.</p><p>Mathematics Subject Classifications: 05A05, 05A15</p>https://escholarship.org/uc/item/5pj7s2gqWed, 23 Mar 2022 00:00:00 +0000The Hurwitz action in complex reflection groups
https://escholarship.org/uc/item/4xg2m191
<p>We enumerate Hurwitz orbits of shortest reflection factorizations of an arbitrary element in the infinite family \(G(m, p, n)\) of complex reflection groups. As a consequence, we characterize the elements for which the action is transitive and give a simple criterion to tell when two shortest reflection factorizations belong to the same Hurwitz orbit. We also characterize the quasi-Coxeter elements (those with a shortest reflection factorization that generates the whole group) in \(G(m, p, n)\).</p><p>Mathematics Subject Classifications: 05A05, 05A15, 05E18, 20F55</p>https://escholarship.org/uc/item/4xg2m191Wed, 23 Mar 2022 00:00:00 +0000Three Fuss-Catalan posets in interaction and their associative algebras
https://escholarship.org/uc/item/4s55d1j5
<p>We introduce \(\delta\)-cliffs, a generalization of permutations and increasing trees depending on a range map \(\delta\). We define a first lattice structure on these objects and we establish general results about its subposets. Among them, we describe sufficient conditions to have EL-shellable posets, lattices with algorithms to compute the meet and the join of two elements, and lattices constructible by interval doubling. Some of these subposets admit natural geometric realizations. Then, we introduce three families of subposets which, for some maps \(\delta\), have underlying sets enumerated by the Fuss-Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. These three families of posets fit into a chain for the order extension relation and they share some properties. Finally, in the same way as the product of the Malvenuto-Reutenauer algebra forms intervals of the right weak Bruhat order of permutations,...https://escholarship.org/uc/item/4s55d1j5Wed, 23 Mar 2022 00:00:00 +0000Intersecting principal Bruhat ideals and grades of simple modules
https://escholarship.org/uc/item/35x678r9
<p>We prove that the grades of simple modules indexed by boolean permutations, over the incidence algebra of the symmetric group with respect to the Bruhat order, are given by Lusztig's \(\mathbf{a}\)-function. Our arguments are combinatorial, and include a description of the intersection of two principal order ideals when at least one permutation is boolean. An important object in our work is a reduced word written as minimally many runs of consecutive integers, and one step of our argument shows that this minimal quantity is equal to the length of the second row in the permutation's shape under the Robinson-Schensted correspondence. We also prove that a simple module over the above-mentioned incidence algebra is perfect if and only if its index is the longest element of a parabolic subgroup.</p><p>Mathematics Subject Classifications: 20F55, 06A07, 05E15</p>https://escholarship.org/uc/item/35x678r9Wed, 23 Mar 2022 00:00:00 +0000Stack-sorting for Coxeter groups
https://escholarship.org/uc/item/34q9t2nn
<p>Given an essential semilattice congruence \(\equiv\) on the left weak order of a \linebreak Coxeter group \(W\), we define the Coxeter stack-sorting operator \({\bf S}_\equiv:W\to W\) by \({{\bf S}_\equiv(w)=w\big(\pi_\downarrow^\equiv(w)\big)^{-1}}\), where \(\pi_\downarrow^\equiv(w)\) is the unique minimal element of the congruence class of \(\equiv\) containing \(w\). When \(\equiv\) is the sylvester congruence on the symmetric group \(S_n\), the operator \({\bf S}_\equiv\) is West's stack-sorting map. When \(\equiv\) is the descent congruence on \(S_n\), the operator \({\bf S}_\equiv\) is the pop-stack-sorting map. We establish several general results about Coxeter stack-sorting operators, especially those acting on symmetric groups. For example, we prove that if \(\equiv\) is an essential lattice congruence on \(S_n\), then every permutation in the image of \({\bf S}_\equiv\) has at most \(\left\lfloor\frac{2(n-1)}{3}\right\rfloor\) right descents; we also show that this...https://escholarship.org/uc/item/34q9t2nnWed, 23 Mar 2022 00:00:00 +0000A bijective proof of Kohnert's rule for Schubert polynomials
https://escholarship.org/uc/item/2t93n5mm
<p>Kohnert proposed a formula for Schubert polynomials as the generating polynomial for certain unit cell diagrams obtained from the diagram of a permutation. Billey, Jockusch and Stanley proved a formula for Schubert polynomials as the generating polynomial for compatible sequences of reduced words. In this paper, we give an explicit bijection between these two models, thereby proving Kohnert's rule for Schubert polynomials.</p><p>Mathematics Subject Classifications: 05A05, 05A19, 14N10, 14N15</p>https://escholarship.org/uc/item/2t93n5mmWed, 23 Mar 2022 00:00:00 +0000The homogenized Linial arrangement and Genocchi numbers
https://escholarship.org/uc/item/2f1915hz
<p>We study the intersection lattice of a hyperplane arrangement recently introduced by Hetyei who showed that the number of regions of the arrangement is a median Genocchi number. Using a different method, we refine Hetyei's result by providing a combinatorial interpretation of the coefficients of the characteristic polynomial of the intersection lattice of this arrangement. The Genocchi numbers count a class of permutations known as Dumont permutations and the median Genocchi numbers count the derangements in this class. We show that the signless coefficients of the characteristic polynomial count Dumont-like permutations with a given number of cycles. This enables us to derive formulas for the generating function of the characteristic polynomial, which reduce to known formulas for the generating functions of the Genocchi numbers and the median Genocchi numbers. As a byproduct of our work, we obtain new models for the Genocchi and median Genocchi numbers.</p><p>Mathematics Subject...https://escholarship.org/uc/item/2f1915hzWed, 23 Mar 2022 00:00:00 +0000No extremal square-free words over large alphabets
https://escholarship.org/uc/item/23b1m1rf
<p>A word is square-free if it does not contain any square (a word of the form \(XX\)), and is extremal square-free if it cannot be extended to a new square-free word by inserting a single letter at any position. Grytczuk, Kordulewski, and Niewiadomski proved that there exist infinitely many ternary extremal square-free words. We establish that there are no extremal square-free words over any alphabet of size at least \(17\).</p><p>Mathematics Subject Classifications: 05A05, 05D10, 68R15</p>https://escholarship.org/uc/item/23b1m1rfWed, 23 Mar 2022 00:00:00 +0000Toppleable permutations, excedances and acyclic orientations
https://escholarship.org/uc/item/08z5b229
<p>Recall that an excedance of a permutation \(\pi\) is any position \(i\) such that \(\pi_i > i\). Inspired by the work of Hopkins, McConville and Propp (Elec. J. Comb., 2017) on sorting using toppling, we say that a permutation is toppleable if it gets sorted by a certain sequence of toppling moves. One of our main results is that the number of toppleable permutations on \(n\) letters is the same as those for which excedances happen exactly at \(\{1,\dots, \lfloor (n-1)/2 \rfloor\}\). Additionally, we show that the above is also the number of acyclic orientations with unique sink (AUSOs) of the complete bipartite graph \(K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor + 1}\). We also give a formula for the number of AUSOs of complete multipartite graphs. We conclude with observations on an extremal question of Cameron et al. concerning maximizers of (the number of) acyclic orientations, given a prescribed number of vertices and edges for the graph.</p><p>Mathematics Subject Classifications:...https://escholarship.org/uc/item/08z5b229Wed, 23 Mar 2022 00:00:00 +0000Refined Catalan and Narayana cyclic sieving
https://escholarship.org/uc/item/20d9s4hn
<p>We prove several new instances of the cyclic sieving phenomenon (CSP) on Catalan objects of type \(A\) and type \(B\). Moreover, we refine many of the known instances of the CSP on Catalan objects. For example, we consider triangulations refined by the number of "ears", non-crossing matchings with a fixed number of short edges, and non-crossing configurations with a fixed number of loops and edges.</p><p>Keywords: Dyck paths, cyclic sieving, Narayana numbers, major index, q-analog.</p><p>Mathematics Subject Classifications: 05E18, 05A19, 05A30</p>https://escholarship.org/uc/item/20d9s4hnTue, 30 Nov 2021 00:00:00 +0000A combinatorial Schur expansion of triangle-free horizontal-strip LLT polynomials
https://escholarship.org/uc/item/88f1079r
<p>In recent years, Alexandersson and others proved combinatorial formulas for the Schur function expansion of the horizontal-strip LLT polynomial \(G_{\boldsymbol\lambda}(\boldsymbol x;q)\) in some special cases. We associate a weighted graph \(\Pi\) to \(\boldsymbol\lambda\) and we use it to express a linear relation among LLT polynomials. We apply this relation to prove an explicit combinatorial Schur-positive expansion of \(G_{\boldsymbol\lambda}(\boldsymbol x;q)\) whenever \(\Pi\) is triangle-free. We also prove that the largest power of \(q\) in the LLT polynomial is the total edge weight of our graph.</p><p>Keywords: Charge, chromatic symmetric function, cocharge, Hall--Littlewood polynomial, jeu de taquin, LLT polynomial, interval graph, Schur function, Schur-positive, symmetric function.</p><p>Mathematics Subject Classifications: 05E05, 05E10, 05C15</p>https://escholarship.org/uc/item/88f1079rFri, 12 Nov 2021 00:00:00 +0000Large hypergraphs without tight cycles
https://escholarship.org/uc/item/7hk9r04f
<p>An \(r\)-uniform tight cycle of length \(\ell>r\) is a hypergraph with vertices \(v_1,\dots,v_\ell\) and edges \(\{v_i,v_{i+1},\dots,v_{i+r-1}\}\) (for all \(i\)), with the indices taken modulo \(\ell\). It was shown by Sudakov and Tomon that for each fixed \(r\geq 3\), an \(r\)-uniform hypergraph on \(n\) vertices which does not contain a tight cycle of any length has at most \(n^{r-1+o(1)}\) hyperedges, but the best known construction (with the largest number of edges) only gives \(\Omega(n^{r-1})\) edges. In this note we prove that, for each fixed \(r\geq 3\), there are \(r\)-uniform hypergraphs with \(\Omega(n^{r-1}\log n/\log\log n)\) edges which contain no tight cycles, showing that the \(o(1)\) term in the exponent of the upper bound is necessary.</p><p>Mathematics Subject Classifications: 05C65, 05C38</p>https://escholarship.org/uc/item/7hk9r04fFri, 12 Nov 2021 00:00:00 +0000Hidden automatic sequences
https://escholarship.org/uc/item/75c3n0bc
<p>An automatic sequence is a letter-to-letter coding of a fixed point of a uniform morphism. More generally, morphic sequences are letter-to-letter codings of fixed points of arbitrary morphisms. There are many examples where an, a priori, morphic sequence with a non-uniform morphism happens to be an automatic sequence. An example is the Lysënok morphism \(a \to aca\), \(b \to d\), \(c \to b\), \(d \to c\), the fixed point of which is also a \(2\)-automatic sequence. Such an identification is useful for describing the dynamical systems generated by the fixed point. We give several ways to uncover such hidden automatic sequences, and present many examples. We focus in particular on morphisms associated with Grigorchuk groups.</p><p>Keywords: Morphic sequences, automatic sequences, Grigorchuk groups.</p><p>Mathematics Subject Classifications: 11B85, 68R15, 37B10</p>https://escholarship.org/uc/item/75c3n0bcFri, 12 Nov 2021 00:00:00 +0000Packings of partial difference sets
https://escholarship.org/uc/item/67b401k0
<p>A packing of partial difference sets is a collection of disjoint partial difference sets in a finite group \(G\). This configuration has received considerable attention in design theory, finite geometry, coding theory, and graph theory over many years, although often only implicitly. We consider packings of certain Latin square type partial difference sets in abelian groups having identical parameters, the size of the collection being either the maximum possible or one smaller. We unify and extend numerous previous results in a common framework, recognizing that a particular subgroup reveals important structural information about the packing. Identifying this subgroup allows us to formulate a recursive lifting construction of packings in abelian groups of increasing exponent, as well as a product construction yielding packings in the direct product of the starting groups. We also study packings of certain negative Latin square type partial difference sets of maximum possible...https://escholarship.org/uc/item/67b401k0Fri, 12 Nov 2021 00:00:00 +0000Symmetric edge polytopes and matching generating polynomials
https://escholarship.org/uc/item/5xf8d657
<p>Symmetric edge polytopes \(\mathcal{A}_G\) of type A are lattice polytopes arising from the root system \(A_n\) and finite simple graphs \(G\). There is a connection between \(\mathcal{A}_G\) and the Kuramoto synchronization model in physics. In particular, the normalized volume of \(\mathcal{A}_G\) plays a central role. In the present paper, we focus on a particular class of graphs. In fact, for any cactus graph \(G\), we give a formula for the \(h^*\)-polynomial of \(\mathcal{A}_{\widehat{G}}\) by using matching generating polynomials, where \(\widehat{G}\) is the suspension of \(G\). This gives also a formula for the normalized volume of \(\mathcal{A}_{\widehat{G}}\). Moreover, via methods from chemical graph theory, we show that for any cactus graph \(G\), the \(h^*\)-polynomial of \(\mathcal{A}_{\widehat{G}}\) is real-rooted. Finally, we extend the discussion to symmetric edge polytopes of type \(B\), which are lattice polytopes arising from the root system \(B_n\) and...https://escholarship.org/uc/item/5xf8d657Fri, 12 Nov 2021 00:00:00 +0000The combinatorics of normal subgroups in the unipotent upper triangular group
https://escholarship.org/uc/item/5c21s1xq
<p>Uniformly describing the conjugacy classes of the unipotent upper triangular groups \(\mathrm{UT}_{n}(\mathbb{F}_{q})\) (for all or many values of \(n\) and \(q\)) is a nearly impossible task. This paper takes on the related problem of describing the normal subgroups of \(\mathrm{UT}_{n}(\mathbb{F}_{q})\). For \(q\) a prime, a bijection will be established between these subgroups and pairs of combinatorial objects with labels from \(\mathbb{F}_{q}^{\times}\). Each pair comprises a loopless binary matroid and a tight splice, an apparently new kind of combinatorial object which interpolates between nonnesting set partitions and shortened polyominoes. For arbitrary \(q\), the same approach describes a natural subset of normal subgroups: those which correspond to the ideals of the Lie algebra \(\mathfrak{ut}_{n}(\mathbb{F}_{q})\) under an approximation of the exponential map.</p><p>Keywords: Unipotent group, normal subgroup, Lie algebra ideal, nonnesting set partition, matroid,...https://escholarship.org/uc/item/5c21s1xqFri, 12 Nov 2021 00:00:00 +0000Numerical semigroups, polyhedra, and posets I: the group cone
https://escholarship.org/uc/item/5b43h4dq
<p>Several recent papers have explored families of rational polyhedra whose integer points are in bijection with certain families of numerical semigroups. One such family, first introduced by Kunz, has integer points in bijection with numerical semigroups of fixed multiplicity, and another, introduced by Hellus and Waldi, has integer points corresponding to oversemigroups of numerical semigroups with two generators. In this paper, we provide a combinatorial framework from which to study both families of polyhedra. We introduce a new family of polyhedra called group cones, each constructed from some finite abelian group, from which both of the aforementioned families of polyhedra are directly determined but that are more natural to study from a standpoint of polyhedral geometry. We prove that the faces of group cones are naturally indexed by a family of finite posets, and illustrate how this combinatorial data relates to semigroups living in the corresponding faces of the other...https://escholarship.org/uc/item/5b43h4dqFri, 12 Nov 2021 00:00:00 +0000Crystal structures on FFLV polytopes
https://escholarship.org/uc/item/4g96d04z
<p>In this paper we formulate a conjecture about the crystal structures on Feigin--Fourier--Littelmann--Vinberg (FFLV) polytopes and prove it in small rank examples. In the case of multiples of a fundamental weight this approach recovers the crystal structures defined by Kus. A key step in this approach is the realisation of FFLV polytopes as Minkowski sums of Lusztig polytopes associated to different reduced words.</p><p>Keywords: Crystal structure, Lusztig polytope, FFLV polytope.</p><p>Mathematics Subject Classifications: 05E10, 17B10</p>https://escholarship.org/uc/item/4g96d04zFri, 12 Nov 2021 00:00:00 +0000The Pelletier--Ressayre hidden symmetry for Littlewood--Richardson coefficients
https://escholarship.org/uc/item/4321d4vh
<p>We prove an identity for Littlewood--Richardson coefficients conjectured by Pelletier and Ressayre. The proof relies on a novel birational involution defined over any semifield.</p><p>Keywords: Symmetric functions, Littlewood--Richardson coefficients, partitions, Schur functions, Schur polynomials, birational combinatorics, detropicalization, partitions.</p><p>Mathematics Subject Classifications: 05E05</p>https://escholarship.org/uc/item/4321d4vhFri, 12 Nov 2021 00:00:00 +0000\(P\)-strict promotion and \(B\)-bounded rowmotion, with applications to tableaux of many flavors
https://escholarship.org/uc/item/42v401d5
<p>We define \(P\)-strict labelings for a finite poset \(P\) as a generalization of semistandard Young tableaux and show that promotion on these objects is in equivariant bijection with a toggle action on \(B\)-bounded \(Q\)-partitions of an associated poset \(Q\). In many nice cases, this toggle action is conjugate to rowmotion. We apply this result to flagged tableaux, Gelfand--Tsetlin patterns, and symplectic tableaux, obtaining new cyclic sieving and homomesy conjectures. We also show \(P\)-strict promotion can be equivalently defined using Bender--Knuth and jeu de taquin perspectives.</p><p>Mathematics Subject Classifications: 05A19, 05E18</p>https://escholarship.org/uc/item/42v401d5Fri, 12 Nov 2021 00:00:00 +0000Barely lonely runners and very lonely runners: a refined approach to the Lonely Runner Problem
https://escholarship.org/uc/item/3wx931fh
<p>We introduce a sharpened version of the well-known Lonely Runner Conjecture of Wills and Cusick. Given a real number \(x\), let \(\Vert x \Vert\) denote the distance from \(x\) to the nearest integer. For each set of positive integer speeds \(v_1, \dots, v_n\), we define the associated maximum loneliness to be $$\operatorname{ML}(v_1, \dots, v_n)=\max_{t \in \mathbb{R}}\min_{1 \leq i \leq n} \Vert tv_i \Vert.$$</p><p>The Lonely Runner Conjecture asserts that \(\operatorname{ML}(v_1, \dots, v_n) \geq 1/(n+1)\) for all choices of \(v_1, \dots, v_n\). We make the stronger conjecture that for each choice of \(v_1, \dots, v_n\), we have either \(\operatorname{ML}(v_1, \dots, v_n)=s/(ns+1)\) for some \(s \in \mathbb{N}\) or \(\operatorname{ML}(v_1, \dots, v_n) \geq 1/n\). This view reflects a surprising underlying rigidity of the Lonely Runner Problem. Our main results are: confirming our stronger conjecture for \(n \leq 3\); and confirming it for \(n=4\) and \(n=6\) in the case...https://escholarship.org/uc/item/3wx931fhFri, 12 Nov 2021 00:00:00 +0000Intermediate symplectic characters and shifted plane partitions of shifted double staircase shape
https://escholarship.org/uc/item/12m158c5
<p>We use intermediate symplectic characters to give a proof and variations of Hopkins' conjecture, now proved by Hopkins and Lai, on the number of shifted plane partitions of shifted double staircase shape with bounded entries. In fact, we prove some character identities involving intermediate symplectic characters, and find generating functions for such shifted plane partitions. The key ingredients of the proof are a bialternant formula for intermediate symplectic characters, which interpolates between those for Schur functions and symplectic characters, and the Ishikawa--Wakayama minor-summation formula.</p><p>Keywords: Intermediate symplectic characters, shifted plane partitions, minor-summation formula, Pfaffian .</p><p>Mathematics Subject Classifications: 05A15, 05E05, 05E10</p>https://escholarship.org/uc/item/12m158c5Fri, 12 Nov 2021 00:00:00 +0000Resolving Stanley's conjecture on \(k\)-fold acyclic complexes
https://escholarship.org/uc/item/0d89b1cc
<p>In 1993 Stanley showed that if a simplicial complex is acyclic over some field, then its face poset can be decomposed into disjoint rank \(1\) boolean intervals whose minimal faces together form a subcomplex. Stanley further conjectured that complexes with a higher notion of acyclicity could be decomposed in a similar way using boolean intervals of higher rank. We provide an explicit counterexample to this conjecture. We also prove a version of the conjecture for boolean trees and show that the original conjecture holds when this notion of acyclicity is as high as possible.</p><p>Mathematics Subject Classifications: 05E45, 55U10</p>https://escholarship.org/uc/item/0d89b1ccFri, 12 Nov 2021 00:00:00 +0000Counting quadrant walks via Tutte's invariant method
https://escholarship.org/uc/item/7k6841md
<p>In the 1970s, William Tutte developed a clever algebraic approach, based on certain "invariants", to solve a functional equation that arises in the enumeration of properly colored triangulations. The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past 20 years to a rich collection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps, taken in \(\{-1, 0,1\}^2\).</p><p>We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic. This includes Gessel's famous model, and the first proof ever found for one model with weighted steps. To be applicable, the method requires the existence of two rational functions called invariant and decoupling function respectively. When they exist, algebraicity follows almost automatically.</p><p>Then, we move...https://escholarship.org/uc/item/7k6841mdThu, 11 Nov 2021 00:00:00 +0000Friends and strangers walking on graphs
https://escholarship.org/uc/item/7299j21s
<p>Given graphs \(X\) and \(Y\) with vertex sets \(V(X)\) and \(V(Y)\) of the same cardinality, we define a graph \(\mathsf{FS}(X,Y)\) whose vertex set consists of all bijections \(\sigma\colon V(X)\to V(Y)\), where two bijections \(\sigma\) and \(\sigma'\) are adjacent if they agree everywhere except for two adjacent vertices \(a,b \in V(X)\) such that \(\sigma(a)\) and \(\sigma(b)\) are adjacent in \(Y\). This setup, which has a natural interpretation in terms of friends and strangers walking on graphs, provides a common generalization of Cayley graphs of symmetric groups generated by transpositions, the famous \(15\)-puzzle, generalizations of the \(15\)-puzzle as studied by Wilson, and work of Stanley related to flag \(h\)-vectors. We derive several general results about the graphs \(\mathsf{FS}(X,Y)\) before focusing our attention on some specific choices of \(X\). When \(X\) is a path graph, we show that the connected components of \(\mathsf{FS}(X,Y)\) correspond to the...https://escholarship.org/uc/item/7299j21sThu, 11 Nov 2021 00:00:00 +0000Proof of the Kakeya set conjecture over rings of integers modulo square-free N
https://escholarship.org/uc/item/4324c8n4
<p>A Kakeya set \(S \subset (\mathbb{Z}/N\mathbb{Z})^n\) is a set containing a line in each direction. We show that, when \(N\) is any square-free integer, the size of the smallest Kakeya set in \((\mathbb{Z}/N\mathbb{Z})^n\) is at least \(C_{n,\epsilon} N^{n - \epsilon}\) for any \(\epsilon\) -- resolving a special case of a conjecture of Hickman and Wright. Previously, such bounds were only known for the case of prime \(N\). We also show that the case of general \(N\) can be reduced to lower bounding the \(\mathbb{F}_p\) rank of the incidence matrix of points and hyperplanes over \((\mathbb{Z}/p^k\mathbb{Z})^n\).</p><p>Mathematics Subject Classifications: 05B20, 05B25</p>https://escholarship.org/uc/item/4324c8n4Thu, 11 Nov 2021 00:00:00 +0000Families with no perfect matchings
https://escholarship.org/uc/item/1vc250fj
<p>We consider families of \(k\)-subsets of \(\{1, \dots, n\}\), where \(n\) is a multiple of \(k\), which have no perfect matching. An equivalent condition for a family \(\mathcal{F}\) to have no perfect matching is for there to be a blocking set, which is a set of \(b\) elements of \(\{1, \dots, n\}\) that cannot be covered by \(b\) disjoint sets in \(\mathcal{F}\). We are specifically interested in the largest possible size of a family \(\mathcal{F}\) with no perfect matching and no blocking set of size less than \(b\). Frankl resolved the case of families with no singleton blocking set (in other words, the \(b=2\) case) for sufficiently large \(n\) and conjectured an optimal construction for general \(b\). Though Frankl's construction fails to be optimal for \(k = 2, 3\), we show that the construction is optimal whenever \(k \ge 100\) and \(n\) is sufficiently large.</p><p>Mathematics Subject Classifications: 05D05</p>https://escholarship.org/uc/item/1vc250fjThu, 11 Nov 2021 00:00:00 +0000A canonical tree-of-tangles theorem for structurally submodular separation systems
https://escholarship.org/uc/item/1fg8b947
<p>We show that every structurally submodular separation system admits a canonical tree set which distinguishes its tangles.</p><p>Mathematics Subject Classifications: 05C40, 05C83, 06A07</p>https://escholarship.org/uc/item/1fg8b947Thu, 11 Nov 2021 00:00:00 +0000Editorial
https://escholarship.org/uc/item/4vb046p0
Editorialhttps://escholarship.org/uc/item/4vb046p0Fri, 5 Nov 2021 00:00:00 +0000