Abstract: The Lucas sequence is a sequence of polynomials in s, t defined recursively by \(\{0\}=0\) , \(\{1\}=1\) , and \(\{n\}=s\{n-1\}+t\{n-2\}\) for \(n\ge 2\) . On specialization of s and t one can recover the Fibonacci numbers, the nonnegative integers, and the q-integers \([n]_q\) . Given a quantity which is expressed in terms of products and quotients of nonnegative integers, one obtains a Lucas analogue by replacing each factor of n in the expression with \(\{n\}\) . It is then natural to ask if the resulting rational function is actually a polynomial in s, t with nonnegative integer coefficients and, if so, what it counts. The first simple combinatorial interpretation for this polynomial analogue of the binomial coefficients was given by Sagan and Savage, although their model resisted being used to prove identities for these Lucasnomials or extending their ideas to other combinatorial sequences. The purpose of this paper is to give a new, even more natural model for these Lucasnomials using lattice paths which can be used to prove various equalities as well as extending to Catalan numbers and their relatives, such as those for finite Coxeter groups. PubDate: 2020-07-02

Abstract: By an oval in \({\mathbb {Z}}^2_{2p},\) p odd prime, we mean a set of \(2p+2\) points, such that no three of them are on a line. It is shown that ovals in \({\mathbb {Z}}^2_{2p}\) only exist for \(p=3,5\) and they are unique up to an isomorphism. PubDate: 2020-07-02

Abstract: An inversion triple of an element w of a simply laced Coxeter group W is a set \(\{ \alpha , \beta , \alpha + \beta \}\) , where each element is a positive root sent negative by w. We say that an inversion triple of w is contractible if there is a root sequence for w in which the roots of the triple appear consecutively. Such triples arise in the study of the commutation classes of reduced expressions of elements of W, and have been used to define or characterize certain classes of elements of W, e.g., the fully commutative elements and the freely braided elements. Also, the study of inversion triples is connected with the representation theory of affine Hecke algebras and double affine Hecke algebras. In this paper, we describe the inversion triples that are contractible, and we give a new, simple characterization of the groups W with the property that all inversion triples are contractible. We also study the natural action of W on the set of all triples of (not necessarily positive) roots of the form \(\{ \alpha , \beta , \alpha + \beta \}\) . This enables us to prove rather quickly that every triple of positive roots \(\{ \alpha , \beta , \alpha + \beta \}\) is contractible for some w in W and, moreover, when W is finite, w may be taken to be the longest element of W. At the end of the paper, we pose a problem concerning the aforementioned action. PubDate: 2020-07-02

Abstract: Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most \(15k-9\) taxa where k is the TBR (Tree Bisection and Reconnection) distance between the two trees, and that this bound is tight. Here, we propose five new reduction rules and show that these further reduce the bound to \(11k-9\) . The new rules combine the “unrooted generator” approach introduced in Kelk and Linz (SIAM J Discrete Math 33(3):1556–1574, 2019) with a careful analysis of agreement forests to identify (i) situations when chains of length 3 can be further shortened without reducing the TBR distance, and (ii) situations when small subtrees can be identified whose deletion is guaranteed to reduce the TBR distance by 1. To the best of our knowledge these are the first reduction rules that strictly enhance the reductive power of the subtree and chain reduction rules. PubDate: 2020-07-01

Abstract: Kostant’s partition function is a vector partition function that counts the number of ways one can express a weight of a Lie algebra \(\mathfrak {g}\) as a nonnegative integral linear combination of the positive roots of \(\mathfrak {g}\) . Multiplex juggling sequences are generalizations of juggling sequences that specify an initial and terminal configuration of balls and allow for multiple balls at any particular discrete height. Magic multiplex juggling sequences generalize further to include magic balls, which cancel with standard balls when they meet at the same height. In this paper, we establish a combinatorial equivalence between positive roots of a Lie algebra and throws during a juggling sequence. This provides a juggling framework to calculate Kostant’s partition functions, and a partition function framework to compute the number of juggling sequences. From this equivalence we provide a broad range of consequences and applications connecting this work to polytopes, posets, positroids, and weight multiplicities. PubDate: 2020-06-29

Abstract: Weights of permutations were originally introduced by Dugan et al. (Journal of Combinatorial Theory, Series A 164:24–49, 2019) in their study of the combinatorics of tiered trees. Given a permutation \(\sigma \) viewed as a sequence of integers, computing the weight of \(\sigma \) involves recursively counting descents of certain subpermutations of \(\sigma \). Using this weight function, one can define a q-analog \(E_n(x,q)\) of the Eulerian polynomials. We prove two main results regarding weights of permutations and the polynomials \(E_n(x,q)\). First, we show that the coefficients of \(E_n(x, q)\) stabilize as n goes to infinity, which was conjectured by Dugan et al. (Journal of Combinatorial Theory, Series A 164:24–49, 2019), and enables the definition of the formal power series \(W_d(t)\), which has interesting combinatorial properties. Second, we derive a recurrence relation for \(E_n(x, q)\), similar to the known recurrence for the classical Eulerian polynomials \(A_n(x)\). Finally, we give a recursive formula for the numbers of certain integer partitions and, from this, conjecture a recursive formula for the stabilized coefficients mentioned above. PubDate: 2020-06-06

Abstract: Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are Cayley graphs of abelian groups. Such groups can be constructed using a generalization to \(\mathbb {Z}^n\) of the concept of congruence in \(\mathbb {Z}\). Here we use this approach to present some families of mixed graphs, which, for every fixed value of the degree, have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal. PubDate: 2020-06-06

Abstract: We present new applications of q-binomials, also known as Gaussian binomial coefficients. Our main theorems determine cardinalities of certain error-correcting codes based on Varshamov–Tenengolts codes and prove a curious phenomenon relating to deletion spheres. PubDate: 2020-06-03

Abstract: Ramanujan’s modular equations of degrees 3, 5, 7, 11 and 23 yield beautiful colored partition identities. Warnaar analytically generalized the modular equations of degrees 3 and 7, and thereafter, the author found bijective proofs of those partitions identities and recently, established an analytic generalization of the modular equations of degrees 5, 11 and 23. The partition identities of degrees 5 and 11 were combinatorially proved by Sandon and Zanello, and it remains open to find a combinatorial proof of the partition identity of degree 23. In this paper, we prove general colored partition identities with a restriction on the number of parts, which are connected to the partition identities arising from those modular equations. We also provide bijective proofs of these partition identities. In particular, one of these proofs gives bijective proofs of the partition identity of degree 23 for some cases, which also work for the identities of degrees 5 and 11 for the same cases. PubDate: 2020-06-03

Abstract: The monopole-dimer model introduced recently is an exactly solvable signed generalisation of the dimer model. We show that the partition function of the monopole-dimer model on a graph invariant under a fixed-point free involution is a perfect square. We give a combinatorial interpretation of the square root of the partition function for such graphs in terms of a monopole-dimer model on a new kind of graph with two types of edges which we call a dicot. The partition function of the latter can be written as a determinant, this time of a complex adjacency matrix. This formulation generalises Wu’s assignment of imaginary orientation for the grid graph to planar dicots. As an application, we compute the partition function for a family of non-planar dicots with positive weights. PubDate: 2020-06-01

Abstract: Complete partitions are a generalization of MacMahon’s perfect partitions; we further generalize these by defining k-step partitions. A matrix equation shows an unexpected connection between k-step partitions and distinct part partitions. We provide two proofs of the corresponding theorem, one using generating functions and one combinatorial. The algebraic proof relies on a generalization of a conjecture made by Paul Hanna in 2012. PubDate: 2020-06-01

Abstract: A matroid is Gorenstein if its toric variety is. Hibi, Lasoń, Matsuda, Michałek, and Vodička provided a full graph-theoretic classification of Gorenstein matroids associated to simple graphs. We extend this classification to multigraphs. PubDate: 2020-05-30

Abstract: Let \({{\mathfrak {S}}}_n\) be the nth symmetric group. Given a set of permutations \(\Pi \), we denote by \({{\mathfrak {S}}}_n(\Pi )\) the set of permutations in \({{\mathfrak {S}}}_n\) which avoid \(\Pi \) in the sense of pattern avoidance. Consider the generating function \(Q_n(\Pi )=\sum _\sigma F_{{{\,\mathrm{Des}\,}}\sigma }\) where the sum is over all \(\sigma \in {{\mathfrak {S}}}_n(\Pi )\) and \(F_{{{\,\mathrm{Des}\,}}\sigma }\) is the fundamental quasisymmetric function corresponding to the descent set of \(\sigma \). Hamaker, Pawlowski, and Sagan introduced \(Q_n(\Pi )\) and studied its properties, in particular, finding criteria for when this quasisymmetric function is symmetric or even Schur nonnegative for all \(n\ge 0\). The purpose of this paper is to continue their investigation by answering some of their questions, proving one of their conjectures, as well as considering other natural questions about \(Q_n(\Pi )\). In particular, we look at \(\Pi \) of small cardinality, superstandard hooks, partial shuffles, Knuth classes, and a stability property. PubDate: 2020-05-13

Abstract: In this paper, we utilize the machinery of cluster algebras, quiver mutations, and brane tilings to study a variety of historical enumerative combinatorics questions all under one roof. Previous work (Zhang in Cluster variables and perfect matchings of subgraphs of the \(dP_{3}\) lattice, http://www.math.umn.edu/~reiner/REU/Zhang2012.pdf. arXiv:1511.0655, 2012; Leoni et al. in J Phys A Math Theor 47:474011, 2014), which arose during the second author’s mentoriship of undergraduates, and more recently of both authors (Lai and Musiker in Commun Math Phys 356(3):823–881, 2017), analyzed the cluster algebra associated with the cone over \(\mathbf {dP_3}\), the del Pezzo surface of degree 6 (\({\mathbb {C}}{\mathbb {P}}^2\) blown up at three points). By investigating sequences of toric mutations, those occurring only at vertices with two incoming and two outgoing arrows, in this cluster algebra, we obtained a family of cluster variables that could be parameterized by \({\mathbb {Z}}^3\) and whose Laurent expansions had elegant combinatorial interpretations in terms of dimer partition functions (in most cases). While the earlier work (Lai and Musiker 2017; Zhang 2012; Leoni et al. 2014) focused exclusively on one possible initial seed for this cluster algebra, there are in total four relevant initial seeds (up to graph isomorphism). In the current work, we explore the combinatorics of the Laurent expansions from these other initial seeds and how this allows us to relate enumerations of perfect matchings on Dungeons to Dragons. PubDate: 2020-02-25

Abstract: The Murnaghan–Nakayama rule is a combinatorial rule for the character values of symmetric groups. We give a new combinatorial proof by explicitly finding the trace of the representing matrices in the standard basis of Specht modules. This gives an essentially bijective proof of the rule. A key lemma is an extension of a straightening result proved by the second author to skew tableaux. Our module theoretic methods also give short proofs of Pieri’s rule and Young’s rule. PubDate: 2020-02-20

Abstract: In a series of papers, Dartyge and Sárközy (partly with other coauthors) studied pseudorandom subsets. In this paper, we study the minimal values of correlation measures of pseudorandom subsets by extending the methods introduced in Alon et al. (Comb Probab Comput 15:1–29, 2006), Anantharam (Discrete Math 308:6203–6209, 2008), Gyarmati (Stud Sci Math Hung 42:79–93, 2005) and Gyarmati and Mauduit (Discrete Math 312:811–818, 2012). PubDate: 2020-02-20

Abstract: A famous theorem of Euler asserts that there are as many partitions of n into distinct parts as there are partitions into odd parts. The even parts in partitions of n into distinct parts play an important role in the Euler–Glaisher bijective proof of this result. In this paper, we investigate the number of even parts in all partitions of n into distinct parts providing new combinatorial interpretations for this number. PubDate: 2020-01-14

Abstract: In this article, we prove a tableau formula for the double Grothendieck polynomials associated to 321-avoiding permutations. The proof is based on the compatibility of the formula with the K-theoretic divided difference operators. Our formula specializes to the one obtained by Chen et al. (Eur J Combin 25(8):1181–1196, 2004) for the (double) skew Schur polynomials. PubDate: 2020-01-14

Abstract: Let \({\mathcal {P}}\) be a set of n points in the Euclidean plane. We prove that, for any \(\varepsilon > 0\), either a single line or circle contains n/2 points of \({\mathcal {P}}\), or the number of distinct perpendicular bisectors determined by pairs of points in \({\mathcal {P}}\) is \(\Omega (n^{52/35 - \varepsilon })\), where the constant implied by the \(\Omega \) notation depends on \(\varepsilon \). This is progress toward a conjecture of Lund, Sheffer, and de Zeeuw, that either a single line or circle contains n/2 points of \({\mathcal {P}}\), or the number of distinct perpendicular bisectors is \(\Omega (n^2)\). The proof relies bounding the size of a carefully selected subset of the quadruples \((a,b,c,d) \in {\mathcal {P}}^4\) such that the perpendicular bisector of a and b is the same as the perpendicular bisector of c and d. PubDate: 2020-01-14