79 research outputs found
Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
No full textWe give three applications of a recently-proven "Decomposition Lemma," which
allows one to count preimages of certain sets of permutations under West's
stack-sorting map . We first enumerate the permutation class
, finding a new example
of an unbalanced Wilf equivalence. This result is equivalent to the enumeration
of permutations sortable by , where is the bubble
sort map. We then prove that the sets ,
,
and are
counted by the so-called "Boolean-Catalan numbers," settling a conjecture of
the current author and another conjecture of Hossain. This completes the
enumerations of all sets of the form
for
with the exception of the set
. We also find an explicit formula for
, where
is the set of permutations in with descents.
This allows us to prove a conjectured identity involving Catalan numbers and
order ideals in Young's lattice
Binary Codes and Period-2 Orbits of Sequential Dynamical Systems
No full textLet be the (global) SDS map of a sequential dynamical system
(SDS) defined over the complete graph using the update order
in which all vertex functions are equal to the same function . Let denote the maximum number of periodic
orbits of period that an SDS map of the form can have. We
show that is equal to the maximum number of codewords in a binary code
of length with minimum distance at least . This result is significant
because it represents the first interpretation of this fascinating
coding-theoretic sequence other than its original definition
Postorder Preimages
No full textGiven a set of decreasing plane trees and a permutation , how many
trees in have as their postorder? Using combinatorial and geometric
constructions, we provide a method for answering this question for certain sets
and all permutations . We then provide applications of our results to
the study of the deterministic stack-sorting algorithm
Proofs of Conjectures about Pattern-Avoiding Linear Extensions
No full textAfter fixing a canonical ordering (or labeling) of the elements of a finite
poset, one can associate each linear extension of the poset with a permutation.
Some recent papers consider specific families of posets and ask how many linear
extensions give rise to permutations that avoid certain patterns. We build off
of two of these papers. We first consider pattern avoidance in -ary heaps,
where we obtain a general result that proves a conjecture of Levin, Pudwell,
Riehl, and Sandberg in a special case. We then prove some conjectures that
Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoiding
linear extensions of rectangular posets
Boolean, Free, and Classical Cumulants as Tree Enumerations
No full textDefant found that the relationship between a sequence of (univariate) classical cumulants and the corresponding sequence of (univariate) free cumulants can be described combinatorially in terms of families of binary plane trees called troupes. Using a generalization of troupes that we call weighted troupes, we generalize this result to allow for multivariate cumulants. Our result also gives a combinatorial description of the corresponding Boolean cumulants. This allows us to answer a question of Defant regarding his troupe transform. We also provide explicit distributions whose cumulants correspond to some specific weighted troupes.18 pages, 7 figure
Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets
No full textThough iterated maps and dynamical systems are not new to combinatorics, they have enjoyed a renewed prominence over the past decade through the elevation of the subfield that has become known as dynamical algebraic combinatorics. Some of the problems that have gained popularity can also be cast and analyzed as finite asynchronous cellular automata (CA). However, these two fields are fairly separate, and while there are some individuals who work in both, that is the exception rather than the norm. In this article, we will describe our ongoing work on toggling independent sets on graphs. This will be preceded by an overview of how this project arose from new combinatorial problems involving homomesy, toggling, and resonance. Though the techniques that we explore are directly applicable to ECA rule 1, many of them can be generalized to other cellular automata. Moreover, some of the ideas that we borrow from cellular automata can be adapted to problems in dynamical algebraic combinatorics. It is our hope that this article will inspire new problems in both fields and connections between them
Convergence of monomial expansions in banach spaces
No full text[EN] If E is a Banach sequence space, then each holomorphic function defines a formal power series ¿ ¿ c ¿(f) z ¿. The problem of when such an expansion converges absolutely and actually represents the function goes back to the very beginning of the theory of holomorphic functions on infinite-dimensional spaces. Several very deep results have been given for scalar-valued functions by Ryan, Lempert and Defant, Maestre and Prengel. We go on with this study, looking at monomial expansions of vector-valued holomorphic functions on Banach spaces. Some situations are very different from the scalar-valued case. © 2011 Published by Oxford University Press. All rights reserved.Both authors were supported by the MEC Project MTM2008-03211. The second cited author was partially supported by grants PR2007-0384 (MEC) and UPV-PAID-00-07.Defant, A.; Sevilla Peris, P. (2012). Convergence of monomial expansions in banach spaces. Quarterly Journal of Mathematics. 63(3):569-584. https://doi.org/10.1093/qmath/haq053S56958463
Recommended from our members
Permutoric promotion: gliding globs, sliding stones, and colliding coins
No full textDefant recently introduced toric promotion, an operator that acts on the labelings of a graph and serves as a cyclic analogue of Schützenberger's promotion operator. Toric promotion is defined as the composition of certain toggle operators, listed in a natural cyclic order. We consider more general permutoric promotion operators, which are defined as compositions of the same toggles, but in permuted orders. We settle a conjecture of Defant by determining the orders of all permutoric promotion operators when is a path graph. In fact, we completely characterize the orbit structures of these operators, showing that they satisfy the cyclic sieving phenomenon. The first half of our proof requires us to introduce and analyze new broken promotion operators, which can be interpreted via globs of liquid gliding on a path graph. For the latter half of our proof, we reformulate the dynamics of permutoric promotion via stones sliding along a cycle graph and coins colliding with each other on a path graph.Mathematics Subject Classifications: 05E18Keywords: Promotion, toric promotion, Coxeter element, cyclic sieving phenomeno
Unitary Cayley graphs of Dedekind domain quotients
No full textAbstractIf X is a commutative ring with unity, then the unitary Cayley graph of X, denoted GX, is defined to be the graph whose vertex set is X and whose edge set is {{a,b}:a−b∈X×}. When R is a Dedekind domain and I is an ideal of R such that R/I is finite and nontrivial, we refer to GR/I as a generalized totient graph. We study generalized totient graphs as generalizations of the graphs GZ/(n), which have appeared recently in the literature, sometimes under the name Euler totient Cayley graphs. We begin by generalizing to Dedekind domains the arithmetic functions known as Schemmel totient functions, and we use one of these generalizations to provide a simple formula, for any positive integer m, for the number of cliques of order m in a generalized totient graph. We then proceed to determine many properties of generalized totient graphs such as their clique numbers, chromatic numbers, chromatic indices, clique domination numbers, and (in many, but not all cases) girths. We also determine the diameter of each component of a generalized totient graph. We correct one erroneous claim about the clique domination numbers of Euler totient Cayley graphs that has appeared in the literature and provide a counterexample to a second claim about the strong domination numbers of these graphs
Tilings of Benzels via Generalized Compression
No full textDefant, Li, Propp, and Young recently resolved two enumerative conjectures of
Propp concerning the tilings of regions in the hexagonal grid called benzels
using two types of prototiles called stones and bones (with varying constraints
on allowed orientations of the tiles). Their primary tool, a bijection called
compression that converts certain -ribbon tilings to -ribbon tilings,
allowed them to reduce their problems to the enumeration of dimers (i.e.,
perfect matchings) of certain graphs. We present a generalized version of
compression that no longer relies on the perspective of partitions and skew
shapes. Using this strengthened tool, we resolve three more of Propp's
conjectures and recast several others as problems about perfect matchings.Comment: 16 pages, 19 figure
- …
