arXiv:2510.01100

The elementary symmetric partition function is a map on the set of partitions. It sends a partition lambda to the partition whose parts are the summands in the evaluation of the elementary symmetric function on the parts of lambda. These elementary symmetric partition functions have been studied before, and are related to plethysm. In this note, we study properties of the elementary symmetric partition functions, particularly related to injectivity and the number of parts appearing in their image partitions.

arXiv:2509.19614

Condorcet domains are subsets of permutations arising in voting theory: regarding their permutations as preference orders on a list of candidates, one avoids Condorcet's paradox when aggregating the preferences via a simple majority relation. We use poset theory to show that, for the subclass of Condorcet domains of tiling type, the majority rule has stronger properties. We then develop techniques to predict the majority rule explicitly for the uniform vote tally on Condorcet domains of tiling type, and apply this to several well-known examples.

arXiv:2504.13108

Global permutation patterns have recently been shown to characterize important properties of a Coxeter group. Here we study global patterns in the context of signed permutations, with both characterizing and enumerative results. Surprisingly, many properties of signed permutations may be characterized by avoidance of the same set of patterns as the corresponding properties in the symmetric group. We also extend previous enumerative work of Egge, and our work has connections to the Garfinkle—Barbasch—Vogan correspondence, the Erdős—Szekeres theorem, and well-known integer sequences.

arXiv:2404.06379

Previous work has shown that the disarray (or displacement) of an (affine) (signed) permutation is bounded in terms of its Coxeter length. Here, we characterize the permutations for which the bound is sharp in two ways: in terms of a natural property of their reduced words, and by "globally" avoiding the pattern 321.

arXiv:2306.12158

Given a Stirling permutation w, we introduce the mesa set of w as the natural generalization of the pinnacle set of a permutation. Our main results characterize admissible mesa sets and give closed enumerative formulas in terms of rational Catalan numbers by providing an explicit bijection between mesa sets and rational Dyck paths.

arXiv:2407.09666

We study algebras satisfying a two-term multilinear identity, namely one of the form x1 ... xn = qxσ(1) ... xσ(n), where q is a parameter from the base field. We show that such algebras with q=1 and σ not fixing 1 or n are eventually commutative in the sense that the equality x1 ... xk = xτ(1) ... xτ(k) holds for k large enough and all permutations τ in Sk. Calling the minimal such k the degree of eventual commutativity, we prove that k is never more than 2n-3, and that this bound is sharp. For various natural examples, we prove that k can be taken to be n+1 or n+2. In the case when q≠1, we establish that the algebra must be nilpotent.

We, moreover, demonstrate that if an algebra is eventually commutative of arbitrary characteristic, then it has a finite basis of its polynomial identities, thus confirming the Specht conjecture in this particular case.

arXiv:2207.05119

We define and construct the "canonical reduced word" of a boolean permutation, and show that the RSK tableaux for that permutation can be read off directly from this reduced word. We also describe those tableaux that can correspond to boolean permutations, and enumerate them. In addition, we generalize a result of Mazorchuk and Tenner, showing that the "run" statistic influences the shape of the RSK tableau of arbitrary permutations, not just of those that are boolean.

arXiv:2405.08943

We define a partial order Pn on permutations of any given size n, which is the image of a natural partial order on inversion sequences. We call this the "middle order." We demonstrate that the poset Pn refines the weak order on permutations and admits the Bruhat order as a refinement, justifying the terminology. These middle orders are distributive lattices and we establish some of their combinatorial properties, including characterization and enumeration of intervals and boolean intervals (in general, or of any given rank), and a combinatorial interpretation of their Euler characteristic. We further study the (not so well-behaved) restriction of this poset to involutions, obtaining a simple formula for the Möbius function of principal order ideals there. Finally, we offer further directions of research, initiating the study of the canonical Heyting algebra associated with Pn, and defining a parking function analogue of Pn.

arXiv:2401.11680

In this paper we study a variant of the Malicious Maître d' problem. This problem, attributed to computer scientist Rob Pike in Peter Winkler's book Mathematical Puzzles: A Connoisseur's Collection, involves seating diners around a circular table with napkins placed between each pair of adjacent settings. The goal of the maître d' is to seat the diners in a way that maximizes the number of diners who arrive at the table to find the napkins on both the left and right of their place already taken by their neighbors. Previous work described a seating algorithm in which the maître d' expects to force about 18% of the diners to be napkinless. In this paper, we show that if the maître d' learns each diner's preference for the right or left napkin before they are placed at the table, this expectation jumps to nearly 1/3 (and converges to 1/3 as the table size gets large). Moreover, our strategy is optimal for every sequence of diners' preferences.

Inspired by many discussions among participants at GEMS of Combinatorics, we have assembled a dynamic and non-exhaustive list of ways to apply a "curbs, not tickets" strategy to conference organization. Namely, we encourage all organizers to consider, for all aspects of planning a conference, how to create initial conditions under which conference participants are treated equitably, rather than responding to situations as (or after!) they arise. We challenge the reader with the following questions: If you are organizing a conference, have you considered the issues outlined below? Have you, as an organizer, been deliberate in your choices? As either a participant or an organizer, can you identify any issues we have missed? If so, can you get those ideas into the hands and planning sessions of our broader community so that, together, we can ensure that conferences are what they should be: positive mathematical gatherings of ideas, perspectives, and people.

arXiv:2212.02480

For any permutation w, we characterize the reduced words of w that are their own commutation class. When w is the long element n(n-1)...321 and n ≥ 4, there are exactly four such words.

arXiv:2403.03280

Stirling permutations are parking functions, and we investigate two parking function statistics in the context of these objects: lucky cars and displacement. Among our results, we consider two extreme cases: extremely lucky Stirling permutations (those with maximally many lucky cars) and extremely unlucky Stirling permutations (those with exactly one lucky car). We show that the number of extremely lucky Stirling permutations of order n is the Catalan number Cn, and the number of extremely unlucky Stirling permutations is (n-1)!. We also give some results for luck that lies between these two extremes. Further, we establish that the displacement of any Stirling permutation of order n is n2, and we prove several results about displacement composition vectors. We conclude with directions for further study.

arXiv:2307.04631

The boolean elements of a Coxeter group have been characterized and shown to possess many interesting properties and applications. Here we introduce "prism permutations," a generalization of those elements, characterizing the prism permutations equivalently in terms of their reduced words and in terms of pattern containment. As part of this work, we introduce the notion of "calibration" to permutation patterns.

arXiv:2302.04404

Petersen and Tenner defined the depth statistic for Coxeter group elements which, in the symmetric group, can be described in terms of a cost function on transpositions. We generalize that cost function to the other classical (finite and affine) Weyl groups, letting the cost of an individual reflection t be the distance between the integers transposed by t in the combinatorial representation of the group (à la Eriksson and Eriksson). Arbitrary group elements then have a well-defined cost, obtained by minimizing the sum of the transposition costs among all factorizations of the element. We show that the cost of arbitrary elements can be computed directly from the elements themselves using a simple, intrinsic formula.

arXiv:1808.05860

"Compactness," or the use of shape as a proxy for fairness, has been a long-running theme in the scrutiny of electoral districts; badly-shaped districts are often flagged as examples of the abuse of power known as gerrymandering. The most popular compactness metrics in the redistricting literature belong to a class of scores that we call contour-based, making heavy use of area and perimeter. This entire class of district scores has some common drawbacks, outlined here. We make the case for discrete shape scores and offer two promising examples: a cut score and a spanning tree score.

No shape metric can work alone as a seal of fairness, but we argue that discrete metrics are better aligned both with the grounding of the redistricting problem in geography and with the computational tools that have recently gained significant traction in the courtroom.

arXiv:2212.05002

For each fully commutative permutation, we construct a "boolean core," which is the maximal boolean permutation in its principal order ideal under the right weak order. We partition the set of fully commutative permutations into the recently defined crowded and uncrowded elements, distinguished by whether or not their RSK insertion tableaux satisfy a sparsity condition. We show that a fully commutative element is uncrowded exactly when it shares the RSK insertion tableau with its boolean core. We present the dynamics of the right weak order on fully commutative permutations, with particular interest in when they change from uncrowded to crowded. In particular, we use consecutive permutation patterns and descents to characterize the minimal crowded elements under the right weak order.

arXiv:2208.14428

Hitomezashi, a form of traditional Japanese embroidery, gives rise to intricate arrangements of axis-parallel unit-length stitches in the plane. Pete studied these patterns in the context of percolation theory, and the first two authors recently investigated additional structural properties of them. In this paper, we establish several optimization-style results on hitomezashi patterns and provide a complete classification of "long-stitch" hitomezashi patterns in which stitches have length greater than 1. We also study variants in which stitches can have directions not parallel to the coordinate axes.

arXiv:2301.02628

Pinnacle sets record the values of the local maxima for a given family of permutations. They were introduced by Davis-Nelson-Petersen-Tenner as a dual concept to that of peaks, previously defined by Billey-Burdzy-Sagan. In recent years pinnacles and admissible pinnacles sets for the type A symmetric group have been widely studied. In this article we define the pinnacle set of signed permutations of types B and D. We give a closed formula for the number of type B/D admissible pinnacle sets and answer several other related enumerative questions.

arXiv:2110.11146

We study relationships between permutation statistics and pattern-functions, counting the number of times particular patterns occur in a permutation. This allows us to write several familiar statistics as linear combinations of pattern counts, both in terms of a permutation and in terms of its image under the fundamental bijection. We use these enumerations to resolve the question of characterizing so-called "shallow" permutations, whose depth (equivalently, disarray/displacement) is minimal with respect to length and reflection length. We present this characterization in several ways, including vincular patterns, mesh patterns, and a new object that we call "arrow patterns." Furthermore, we specialize to characterizing and enumerating shallow involutions and shallow cycles, encountering the Motzkin and large Schröder numbers, respectively.

arXiv:2007.06142

The interval poset of a permutation catalogues the intervals that appear in its one-line notation, according to set inclusion. We study this poset, describing its structural, characterizing, and enumerative properties.

arXiv:2107.12844

Motivated by recent work with Mazorchuk, we characterize the conditions under which the intersection of two principal order ideals in the Bruhat order is boolean. That characterization is presented in three versions: in terms of reduced words, in terms of permutation patterns, and in terms of permutation support. The equivalence of these properties follows from an analysis of what it means to have a specific letter repeated in a permutation's reduced words; namely, that a specific 321-pattern appears.

arXiv:2106.08169

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 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.

arXiv:2009.08865

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.

arXiv:2001.05011

We study the appearance of notable interval structures - lattices, modular lattices, distributive lattices, and boolean lattices - in both the Bruhat and weak orders of Coxeter groups. We collect and expand upon known results for principal order ideals, including pattern characterizations and enumerations for the symmetric group. This segues naturally into a similar analysis for arbitrary intervals, although the results are less characterizing for the Bruhat order at this generality. In counterpoint, however, we obtain a full characterization for intervals starting at rank one in the symmetric group, for each of the four structure types, in each of the two posets. Each category can be enumerated, with intriguing connections to Fibonacci and Catalan numbers. We conclude with suggestions for further directions and questions, including an interesting analysis of the intervals formed between a permutation and each generator in its support.

arXiv:2001.08185

A pinnacle of a permutation is a value that is larger than its immediate neighbors when written in one-line notation. In this paper, we build on previous work that characterized admissible pinnacle sets of permutations. For these sets, there can be specific orderings of the pinnacles that are not admissible, meaning that they are not realized by any permutation. Here we characterize admissible orderings, using the relationship between a pinnacle x and its rank in the pinnacle set to bound the number of times that the pinnacles less than or equal to x can be interrupted by larger values.

arXiv:2007.01132

Let f(x) = αx + β mod 1 for fixed real parameters α and β. For any positive integer n, define the Sós permutation π to be the lexicographically first permutation such that 0 ≤ f(π(0)) ≤ f(π(1)) ≤ ... ≤ f(π(n)) < 1. In this article we give a bijection between Sós permutations and regions in a partition of the parameter space (α,β) ∈ [0,1)^2. This allows us to enumerate these permutations and to obtain the following "three areas" theorem: in any vertical strip (a/b,c/d)×[0,1), with (a/b,c/d) a Farey interval, there are at most three distinct areas of regions, and one of these areas is the sum of the other two.

arXiv:2004.03286

We develop the relationship between minimal transitive star factorizations and noncrossing partitions. This gives a new combinatorial proof of a result by Irving and Rattan, and a specialization of a result of Kreweras. It also arises in a poset on the symmetric group whose definition is motivated by the Subword Property of the Bruhat order.

arXiv:2008.05347

We study tiling-based perimeter and characterize when a given perimeter tile appears in all rhombic tilings of an Elnitsky polygon. Regardless of where on the perimeter this tile appears, its forcing can be described in terms of 321-patterns. We characterize the permutations with maximally many forced right-perimeter tiles, and show that they are enumerated by the Catalan numbers.

arXiv:2002.10503

Given a permutation w, we look at the range of how often a simple reflection σk appears in reduced decompositions of w. We compute the minimum and give a sharp upper bound on the maximum. That bound is in terms of 321- and 3412-patterns in w, specifically as they relate in value and position to k. We also characterize when that minimum and maximum are equal, refining a previous result that braid moves are equivalent to 321-patterns.

Coxeter groups are of significant interest to communities in combinatorics, algebra, and geometry. Their structures and properties are both deeply beautiful and still not entirely understood. We explore some of the many enumerative aspects of these objects. We count elements with desirable properties, we give size orderings to certain features of all group elements, and we relate some of these statistics in ways that give bounds and rankings---if not exact values---to their sizes. Our primary tools come from leveraging different group presentations against each other, and interpreting element properties at the level of generator representations. In this article, we present a sampling of results in this area, putting them into context and hopefully inspiring future research.

arXiv:1906.10237

We generalize the well-known broken stick problem in several ways, including a discrete "brick" analogue and a sequential "pick-up sticks/bricks" version. The limit behavior of the broken brick problem gives a combinatorial proof of the broken stick problem. The pick-up version gives a variation on those scenarios, and we conclude by showing a greater context---namely, that the broken stick/brick problem and the pick-up sticks/bricks problem are two extremes in a family of interesting, and largely open, questions.

arXiv:1811.00082

We consider polygonal tilings of certain regions and use these to give intuitive definitions of tiling-based perimeter and area. We apply these definitions to rhombic tilings of Elnitsky polygons, computing sharp bounds and average values for perimeter tiles in convex centrally symmetric 2n-gons. These bounds and values have implications for the combinatorics of reduced decompositions of permutations. We also classify the permutations whose polygons gave minimal perimeter, defined in two different ways. We conclude by looking at some of these questions in the context of domino tilings, giving a recursive formula and generating function for one family, and describing a family of minimal-perimeter regions.

arXiv:1903.06095

We propose a new graphical format for instant-runoff voting election results. We call this proposal an "accumulation chart." This model, a modification of standard bar charts, is easy to understand, clearly indicates the winner, depicts the instant-runoff algorithm, and summarizes the votes cast. Moreover, it includes the pedigree of each accumulated vote and gives a clear depiction of candidates' coalitions.

arXiv:1704.05494

The peak set of a permutation records the indices of its peaks. These sets have been studied in a variety of contexts, including recent work by Billey, Burdzy, and Sagan, which enumerated permutations with prescribed peak sets. In this article, we look at a natural analogue of the peak set of a permutation, instead recording the values of the peaks. We define the "pinnacle set" of a permutation w to be the set {w(i) : i is a peak of w}. Although peak sets and pinnacle sets mark the same phenomenon for a given permutation, the behaviors of these sets differ in notable ways as distributions over the symmetric group. In the work below, we characterize admissible pinnacle sets and study various enumerative questions related to these objects.

arXiv:1708.04372

We obtain an upper and lower bound for the number of reduced words for a permutation in terms of the number of braid classes and the number of commutation classes of the permutation. We classify the permutations that achieve each of these bounds, and enumerate both cases.

arXiv:1603.09589

In certain finite posets, the expected down-degree of their elements is the same whether computed with respect to either the uniform distribution or the distribution weighting an element by the number of maximal chains passing through it. We show that this coincidence of expectations holds for Cartesian products of chains, connected minuscule posets, weak Bruhat orders on finite Coxeter groups, certain lower intervals in Young's lattice, and certain lower intervals in the weak Bruhat order below dominant permutations. Our tools involve formulas for counting nearly reduced factorizations in 0-Hecke algebras; that is, factorizations that are one letter longer than the Coxeter group length.

arXiv:1612.00736

Parabolic subgroups WI of Coxeter systems (W,S), as well as their ordinary and double quotients W/WI and WI\W/WJ, appear in many contexts in combinatorics and Lie theory, including the geometry and topology of generalized flag varieties and the symmetry groups of regular polytopes. The set of ordinary cosets wWI, for I ⊂ S, forms the Coxeter complex of W, and is well-studied. In this article we look at a less studied object: the set of all double cosets WIwWJ for I, J ⊂ S. Double coset are not uniquely presented by triples (I,w,J). We describe what we call the lex-minimal presentation, and prove that there exists a unique such object for each double coset. Lex-minimal presentations are then used to enumerate double cosets via a finite automaton depending on the Coxeter graph for (W,S). As an example, we present a formula for the number of parabolic double cosets with a fixed minimal element when W is the symmetric group Sn (in this case, parabolic subgroups are also known as Young subgroups). Our formula is almost always linear time computable in n, and we show how it can be generalized to any Coxeter group with little additional work. We spell out formulas for all finite and affine Weyl groups in the case that w is the identity element.

arXiv:1605.05613

S. Elnitsky (1997) gave an elegant bijection between rhombic tilings of 2n-gons and commutation classes of reduced words in the symmetric group on n letters. P. Magyar (1998) found an important construction of the Bott-Samelson varieties introduced by H.C. Hansen (1973) and M. Demazure (1974). We explain a natural connection between S. Elnitsky's and P. Magyar's results. This suggests using tilings to encapsulate Bott-Samelson data (in type A). It also indicates a geometric perspective on S. Elnitsky's combinatorics. We also extend this construction by assigning desingularizations to the zonotopal tilings considered by B. Tenner (2006).

arXiv:1608.06931

A permutation of n letters is k-prolific if each (n-k)-subset of the letters in its one-line notation forms a unique pattern. We present a complete characterization of k-prolific permutations for each k, proving that k-prolific permutations of m letters exist for every m ≥ k2/2+2k+1, and that none exist of smaller size. Key to these results is a natural bijection between k-prolific permutations and certain "permuted" packings of diamonds.

arXiv:1410.2353

It has been postulated that the decryption of micronuclear precursors of somatic genes in certain ciliate species occurs by constrained reversals and block interchanges. Not all permutations are sortable by these constrained sorting operations. We find a linear time criterion for determining which permutations are sortable by constrained block interchanges. For permutations not sortable by constrained block interchanges, we find a linear time criterion for determining which permutations are the final results of attempted sorting by constrained block interchanges. The corresponding theory for constrained reversals appears more complicated and we present partial results for this operation. The constrained sorting operations suggest natural two-player games. By a classical theorem of Zermelo, these games are determined -- that is, some player has a winning strategy. We consider the decision problem of determining which player has a winning strategy in a specific instance of a game. For normal play and misere play games based on constrained block interchanges, we give a complete linear time solution. For another class of games, we give partial results for the constrained block interchange based games.

arXiv:1503.05205

We develop the technique of reduced word manipulation to give a range of results concerning reduced words and permutations more generally. We prove a broad connection between pattern containment and reduced words, which specializes to our previous work for vexillary permutations. We also analyze general tilings of Elnitsky's polygon, and demonstrate that these are closely related to the patterns in a permutation. Building on previous work for commutation classes, we show that reduced word enumeration is monotonically increasing with respect to pattern containment. Finally, we give several applications of this work. We show that a permutation and a pattern have equally many reduced words if and only if they have the same length (equivalently, the same number of 21-patterns), and that they have equally many commutation classes if and only if they have the same number of 321-patterns. We also apply our techniques to enumeration problems of pattern avoidance, and give a bijection between 132-avoiding permutations of a given length and partitions of that same size.

Parabolic subgroups WI of Coxeter systems (W,S) and their ordinary and double cosets W / WI and WI \ W / WJ appear in many contexts in combinatorics and Lie theory, including the geometry and topology of generalized flag varieties and the symmetry groups of regular polytopes. The set of ordinary cosets w WI, for I ⊆ S, forms the Coxeter complex of W, and is well-studied. In this extended abstract, we look at a less studied object: the set of all double cosets WI w WJ for I, J ⊆ S. Each double coset can be presented by many different triples (I,w,J). We describe what we call the lex-minimal presentation and prove that there exists a unique such choice for each double coset. Lex-minimal presentations can be enumerated via a finite automaton depending on the Coxeter graph for (W,S). In particular, we present a formula for the number of parabolic double cosets with a fixed minimal element when W is the symmetric group Sn. In that case, parabolic subgroups are also known as Young subgroups. Our formula is almost always linear time computable in n, and the formula can be generalized to any Coxeter group.

We present a design for a seven game tournament of the 7-player board game Diplomacy, in which each player plays each country one time and each pair of players shares a border either 4 or 5 times. It is impossible for each pair of players to share a border the same number of times in such a tournament, and so the tournament presented is the most "balanced" possible in this sense. A similarly balanced tournament can be constructed for a generalized version of the game involving an arbitrary number of countries. The question of whether a balanced tournament can be found for any number of countries and any border configuration is considered. Such tournaments are found for some infinite families, but most cases remain open.

arXiv:1412.0703

Two mesh patterns are coincident if they are avoided by the same set of permutations. In this paper, we provide necessary conditions for this coincidence, which include having the same set of enclosed diagonals. This condition is sufficient to prove coincidence of vincular patterns, although it is not enough to guarantee coincidence of bivincular patterns. In addition, we provide a generalization of the Shading Lemma (Hilmarsson et al.), a result that examined when a square could be added to the mesh of a pattern.

arXiv:1303.3852

In this paper we study those generic intervals in the Bruhat order of the symmetric group that are isomorphic to the principal order ideal of a permutation w, and consider when the minimum and maximum elements of those intervals are related by a certain property of their reduced words. We show that the property does not hold when w is a decomposable permutation, and that the property always holds when w is the longest permutation.

arXiv:1202.4765

For the elements of a Coxeter group, we present a statistic called depth, defined in terms of factorizations of the elements into products of reflections. Depth is bounded above by length and below by reflection length. In this article, we focus on the case of the symmetric group, where we show that depth is equal to Σi max{w(i)-i, 0}. We characterize those permutations for which depth equals length: these are the 321-avoiding permutations (and hence are enumerated by the Catalan numbers). We also characterize those permutations for which depth equals reflection length: these are permutations avoiding both 321 and 3412 (also known as boolean permutations, which we can hence also enumerate). In this case, it also happens that length equals reflection length, leading to a new perspective on a result of Edelman.

arXiv:1407.5636

We compute the expected number of commutations appearing in a reduced word for the longest element in the symmetric group. The asymptotic behavior of this value is analyzed and shown to approach the length of the permutation, meaning that nearly all positions in the reduced word are expected to support commutations. Finally, we calculate the asymptotic frequencies of commutations, consecutive noncommuting pairs, and long braid moves.

arXiv:1202.5319

It is well-known that any permutation can be written as a product of two involutions. We provide an explicit formula for the number of ways to do so, depending only on the cycle type of the permutation. In many cases, these numbers are sums of absolute values of irreducible characters of the symmetric group evaluated at the same permutation, although apart from the case where all cycles are the same size, we have no good explanation for why this should be so.

arXiv:1302.1883

Mesh patterns are a generalization of classical permutation patterns that encompass classical, bivincular, Bruhat-restricted patterns, and some barred patterns. In this paper, we describe all mesh patterns whose avoidance is coincident with classical avoidance, in a sense declaring that the additional data of a mesh was unnecessary for these patterns. We also describe the permutations having the fewest superfluous meshes, and the permutations having the most, enumerating the superfluous meshes in each case.

arXiv:1301.6096

There are several versions of permutation pattern avoidance that have arisen in the literature, and some known examples of two different types of pattern avoidance coinciding. In this paper, we examine barred patterns and vincular patterns. Answering a question of Steingrímsson, we determine when barred pattern avoidance coincides with avoiding a finite set of vincular patterns, and when vincular pattern avoidance coincides with avoiding a finite set of barred patterns. There are 720 barred patterns with this property, each having between 3 and 7 letters, of which at most 2 are barred, and there are 48 vincular patterns with this property, each having between 2 and 4 letters and exactly one bond.

arXiv:1304.3866

We discuss the advantages of searchable, collaborative, language-independent databases of mathematical results, indexed by "fingerprints" of small and canonical data. Our motivating example is Neil Sloane's massively influential On-Line Encyclopedia of Integer Sequences. We hope to encourage the greater mathematical community to search for the appropriate fingerprints within each discipline, and to compile fingerprint databases of results wherever possible. The benefits of these databases are broad -- advancing the state of knowledge, enhancing experimental mathematics, enabling researchers to discover unexpected connections between areas, and even improving the refereeing process for journal publication.

arXiv:1109.4642

The number of minimal transitive star factorizations of a permutation was shown by Irving and Rattan to depend only on the conjugacy class of the permutation, a surprising result given that the pivot plays a very particular role in such factorizations. Here, we explain this symmetry and provide a bijection between minimal transitive star factorizations of a permutation π having pivot k and those having pivot k'.

arXiv:1106.2839

Given a permutation w, we show that the number of repeated letters in a reduced decomposition of w is always less than or equal to the number of 321- and 3412-patterns appearing in w. Moreover, we prove bijectively that the two quantities are equal if and only if w avoids the ten patterns 4321, 34512, 45123, 35412, 43512, 45132, 45213, 53412, 45312, and 45231.

arXiv:1104.0674

In previous work, we associated to any finite simple graph a particular set of derangements of its vertices. These derangements are in bijection with the spheres in the wedge sum describing the homotopy type of the boolean complex for this graph. Here we study the frequency with which a given derangement appears in this set.

arXiv:1009.4201

A poset has the non-messing-up property if it has two covering sets of disjoint saturated chains so that for any labeling of the poset, sorting the labels along one set of chains and then sorting the labels along the other set yields a linear extension of the poset. The linear extension yielded by thus twice sorting a labeled non-messing-up poset may be independent of which sort was performed first. Here we characterize such sort-invariant labelings for convex subposets of a cylinder. They are completely determined by avoidance of a particular subpattern: a diamond of four elements whose smallest two labels appear at opposite points.

arXiv:1005.4411

We construct and analyze an explicit basis for the homology of the boolean complex of a Coxeter system. This gives combinatorial meaning to the spheres in the wedge sum describing the homotopy type of the complex. We assign a set of derangements to any finite simple graph. For each derangement, we construct a corresponding element in the homology of the complex, and the collection of these elements forms a basis for the homology of the boolean complex. In this manner, the spheres in the wedge sum describing the homotopy type of the complex can be represented by a set of derangements. We give an explicit, closed-form description of the derangements that can be obtained from any graph, and compute this set for several families of graphs. In the cases of complete graphs and Ferrers graphs, these calculations give bijective proofs of previously obtained enumerative results.

arXiv:0711.1819

This article introduces spotlight tiling, a type of covering which is similar to tiling. The distinguishing aspects of spotlight tiling are that the "tiles" have elastic size, and that the order of placement is significant. Spotlight tilings are decompositions, or coverings, and can be considered dynamic as compared to typical static tiling methods. A thorough examination of spotlight tilings of rectangles is presented, including the distribution of such tilings according to size, and how the directions of the spotlights themselves are distributed. The spotlight tilings of several other regions are studied, and suggest that further analysis of spotlight tilings will continue to yield elegant results and enumerations.

arXiv:1003.2544

We prove that the γ-vector of the barycentric subdivision of a simplicial sphere is the f-vector of a balanced simplicial complex. The combinatorial basis for this work is the study of certain refinements of Eulerian numbers used by Brenti and Welker to describe the h-vector of the barycentric subdivision of a boolean complex.

arXiv:0808.2307

In this paper we provide an explicit formula for calculating the boolean number of a Ferrers graph. By previous work of the last two authors, this determines the homotopy type of the boolean complex of the graph. Specializing to staircase shapes, we show that the boolean numbers of the associated Ferrers graphs are the Genocchi numbers of the second kind, and obtain a relation between the Legendre-Stirling numbers and the Genocchi numbers of the second kind. In another application, we compute the boolean number of a complete bipartite graph, corresponding to a rectangular Ferrers shape, which is expressed in terms of the Stirling numbers of the second kind. Finally, we analyze the complexity of calculating the boolean number of a Ferrers graph using these results and show that it is a significant improvement over calculating by edge recursion.

The Bruhat order gives a poset structure to any Coxeter group. The ideal of elements in this poset having boolean principal order ideals forms a simplicial poset. This simplicial poset defines the boolean complex for the group. In a Coxeter system of rank n, we show that the boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of these spheres is the boolean number, which can be computed inductively from the unlabeled Coxeter system, thus defining a graph invariant. For certain families of graphs, the boolean numbers have intriguing combinatorial properties. This work involves joint efforts with Claesson, Kitaev, and Ragnarsson.

arXiv:0902.4011

A permutation τ contains another permutation σ as a pattern if τ has a subsequence whose elements are in the same order with respect to size as the elements in σ. This defines a partial order on the set of all permutations, and gives a graded poset P. We give a large class of pairs of permutations whose intervals in P have Möbius function 0. Also, we give a solution to the problem when σ occurs precisely once in τ, and σ and τ satisfy certain further conditions, in which case the Möbius function is shown to be either -1, 0 or 1. We conjecture that for intervals [σ,τ] consisting of permutations avoiding the pattern 132, the magnitude of the Möbius function is bounded by the number of occurrences of σ in τ. We also conjecture that the Möbius function of the interval [1,τ] is -1, 0 or 1.

We prove that any finite planar graph with girth at least ten can have its edges partitioned to form two graphs on the same vertices, one of which is a forest, and the other of which is a matching. Several related results are also demonstrated.

arXiv:0802.2550

We study the smallest possible number of points in a topological space having k open sets. Equivalently, this is the smallest possible number of elements in a poset having k order ideals. Using efficient algorithms for constructing a topology with a prescribed size, we show that this number has a logarithmic upper bound. We deduce that there exists a topology on n points having k open sets, for all k in an interval which is exponentially large in n. The construction algorithms can be modified to produce topologies where the smallest neighborhood of each point has a minimal size, and we give a range of obtainable sizes for such topologies.

arXiv:0705.1300

The number of domino tilings of a region with reflective symmetry across a line is combinatorially shown to depend on the number of domino tilings of particular subregions, modulo 4. This expands upon previous congruency results for domino tilings, modulo 2, and leads to a variety of corollaries, including that the number of domino tilings of a k-by-2k rectangle is congruent to 1 mod 4.

arXiv:0905.1688

The minimum number of elements needed for a poset to have exactly n linear extensions is at most 2√n. In a special case, the bound can be improved to √n.

arXiv:0806.0906

In any Coxeter group, the set of elements whose principal order ideals are boolean forms a simplicial poset under the Bruhat order. This simplicial poset defines a cell complex, called the boolean complex. In this paper it is shown that, for any Coxeter system of rank n, this boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of such spheres can be computed recursively from the unlabeled Coxeter graph, and defines a new graph invariant called the boolean number. Specific calculations of this number are given for all finite and affine irreducible Coxeter systems, as well as for systems with graphs that are disconnected, complete, or stars. One implication of these results is that the boolean complex is contractible if and only if a generator of the Coxeter system is in the center of the group.

arXiv:0806.0906

In any Coxeter group, the set of elements whose principal order ideals are boolean forms a simplicial poset under the Bruhat order. This simplicial poset defines a cell complex, called the boolean complex. In this paper it is shown that, for any Coxeter system of rank n, this boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of such spheres can be computed recursively from the unlabeled Coxeter graph, and defines a new graph invariant called the boolean number. Specific calculations of this number are given for all finite and affine irreducible Coxeter systems, as well as for systems with graphs that are disconnected, complete, or stars. One implication of these results is that the boolean complex is contractible if and only if a generator of the Coxeter system is in the center of the group.

arXiv:math/0604322

The structure of order ideals in the Bruhat order for the symmetric group is elucidated via permutation patterns. The permutations with boolean principal order ideals are characterized. These form an order ideal which is a simplicial poset, and its rank generating function is computed. Moreover, the permutations whose principal order ideals have a form related to boolean posets are also completely described. It is determined when the set of permutations avoiding a particular set of patterns is an order ideal, and the rank generating functions of these ideals are computed. Finally, the Bruhat order in types B and D is studied, and the elements with boolean principal order ideals are characterized and enumerated by length.

arXiv:math/0404396

We characterize all posets with a particular sorting property, generalizing a well known result for rectangular arrays of real numbers. This property is the existence of two sets of disjoint saturated chains each covering the poset such that for any labeling of the poset elements, sorting the labels along one of the sets of chains and then sorting along the other set of chains leaves the labels sorted along the chains in the first set. We use this classification to characterize posets with more restrictive sorting properties as well.

arXiv:math/0508153

The expected number of Yang-Baxter moves appearing in a reduced decomposition of the longest element of the Coxeter group of type Bn is computed to be 2 - 4/n. For the same element, the expected number of 0101 or 1010 factors appearing in a reduced decomposition is 2/(n2 - 2).

arXiv:math/0506242

Billey, Jockusch, and Stanley characterized 321-avoiding permutations by a property of their reduced decompositions. This paper generalizes that result with a detailed study of permutations via their reduced decompositions and the notion of pattern containment. These techniques are used to prove a new characterization of vexillary permutations in terms of their principal dual order ideals in a particular poset. Additionally, the combined frameworks yield several new results about the commutation classes of a permutation. In particular, these describe structural aspects of the corresponding graph of the classes and the zonotopal tilings of a polygon defined by Elnitsky that is associated with the permutation.

This thesis examines several aspects of reduced decompositions in finite Coxeter groups. Effort is primarily concentrated on the symmetric group, although some discussions are subsequently expanded to finite Coxeter groups of types B and D. In the symmetric group, the combined frameworks of permutation patterns and reduced decompositions are used to prove a new characterization of vexillary permutations. This characterization and the methods used yield a variety of new results about the structure of several objects relating to a permutation. These include its commutation classes, the corresponding graph of the classes, the zonotopal tilings of a particular polygon, and a poset defined in terms of these tilings. The class of freely braided permutations behaves particularly well, and its graphs and posets are explicitly determined. The Bruhat order for the symmetric group is examined, and the permutations with boolean principal order ideals are completely characterized. These form an order ideal which is a simplicial poset, and its rank generating function is computed. Moreover, it is determined when the set of permutations avoiding a particular set of patterns is an order ideal, and the rank generating functions of these ideals are computed. The structure of the intervals and order ideals in this poset is elucidated via patterns, including progress towards understanding the relationship between pattern containment and subintervals in principal order ideals. The final discussions of the thesis are on reduced decompositions in the finite Coxeter groups of types B and D. Reduced decompositions of the longest element in the hyperoctahedral group are studied, and expected values are calculated, expanding on previous work for the symmetric group. These expected values give a quantitative interpretation of the effects of the Coxeter relations on reduced decompositions of the longest element in this group. Finally, the Bruhat order in types B and D is studied, and the elements in these groups with boolean principal order ideals are characterized and enumerated by length.

arXiv:math/0409105

We prove combinatorially that the parity of the number of domino tilings of a region is equal to the parity of the number of domino tilings of a particular subregion. Using this result we can resolve the holey square conjecture. We furthermore give combinatorial proofs of several other tiling parity results, including that the number of domino tilings of a particular family of rectangles is always odd.