Bridget Eileen Tenner

1. The Möbius Function of the Permutation Pattern Poset (with Einar Steingrímsson)
   to appear in Journal of Combinatorics
   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.

2. Partitioning a Planar Graph of Girth Ten into a Forest and a Matching (with A. Bassa, J. Burns, J. Campbell, A. Deshpande, J. Farley, M. Halsey, S.-Y. Ho, D. J. Kleitman, S. Michalakis, P.-O. Persson, P. Pylyavskyy, L. Rademacher, A. Riehl, M. Rios, J. Samuel, A. Vijayasarathy, and L. Zhao)
   to appear in Studies in Applied Mathematics

   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.

3. Spotlight Tiling
   to appear in Annals of Combinatorics
   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.

4. Obtainable Sizes of Topologies on Finite Sets (with Kári Ragnarsson)
   Journal of Combinatorial Theory, Series A 117 (2010), 138-151
   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.

5. Domino Tiling Congruence Modulo 4
   Graphs and Combinatorics 25 (2009), 625-638
   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.

6. Optimizing Linear Extensions
   SIAM Journal on Discrete Mathematics 23 (2009), 1450-1454
   arXiv: 0905.1688

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

7. Homotopy Type of the Boolean Complex of a Coxeter System (with Kári Ragnarsson)
   Advances in Mathematics 222 (2009), 409-430
   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.

8. Relations on Generalized Degree Sequences (with Caroline J. Klivans and Kathryn L. Nyman)
   Discrete Mathematics 309 (2009), 4377-4383
   arXiv: 0806.4012

   We study degree sequences for simplicial posets and polyhedral complexes, 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 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. As a corollary, we recover an f-vector inequality on simplicial posets first shown by Stanley.

9. Pattern Avoidance and the Bruhat Order
   Journal of Combinatorial Theory, Series A 114 (2007), 888-905
   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.

10. A Non-Messing-Up Phenomenon for Posets
    Annals of Combinatorics 11 (2007), 101-114
    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.

11. On Expected Factors in Reduced Decompositions in Type B
    European Journal of Combinatorics 28 (2007), 1144-1151
    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/(n² - 2).

12. Reduced Decompositions and Permutation Patterns
    Journal of Algebraic Combinatorics 24 (2006), 263-284
    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.

13. The Combinatorics of Reduced Decompositions
    Ph.D. Thesis, Massachusetts Institute of Technology, 2006
    

    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.

14. Tiling Parity Results and the Holey Square Solution
    Electronic Journal of Combinatorics 11(2) (2005), R17
    arXiv: 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.

15. Doubly Symmetric Functions (with Allan Berele)
    submitted
    arXiv: 0903.5306

    In this paper we introduce doubly symmetric functions, arising from the equivalence of particular linear combinations of Schur functions and hook Schur functions. We study algebraic and combinatorial aspects of doubly symmetric functions, in particular as they form a subalgebra of the algebra of symmetric functions. This subalgebra is generated by the odd power sum symmetric functions. One consequence is that a Schur function itself is doubly symmetric if and only if it is the Schur function of a staircase shape.

16. Boolean Complexes for Ferrers Graphs (with Anders Claesson, Sergey Kitaev, and Kári Ragnarsson)
    submitted
    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.

17. Database of Permutation Pattern Avoidance

    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.