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.
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.
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).
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.
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.
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.
Ferrers graphs are bipartite graphs that correspond naturally to Ferrers shapes. In this paper, we determine the homotopy type of the boolean complex of Ferrers graphs. Previous work of the last two authors shows that the boolean complex of a graph is a wedge of spheres of maximal dimension. Thus the homotopy type of this complex depends entirely on the number of spheres in the wedge sum, called the boolean number of the Ferrers graph. Applying the results 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.
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, and the number of such spheres can be computed recursively. 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.
We study degree sequences for simplicial and cubical posets, generalizing the well studied graphical degree sequences. Here we extend the more common generalization of vertex-to-facet degree sequences, by considering arbitrary face-to-flag and flag-to-flag degree sequences. In particular, these may be viewed as natural refinements of the flag f-vector of the poset. We investigate properties and relations of these generalized degree sequences, proving linear relations between flag degree sequences in terms of the composition of rank jumps of the flag.
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.
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.
This is an online database of phenomena charaterized by the avoidance of finitely many permutation patterns. Patterns, phenomena, references, and any enumeration are all cross-listed and searchable.