Stephanie van Willigenburg

Extremal problems, in general, ask for the optimal size of certain finite objects when some restrictions are imposed. In extremal combinatorics, a major field in combinatorics, one studies how global properties guarantee the existence of local substructures, or equivalently, how avoiding local substructures poses a constraint on global quantities. In this thesis, we study the following three problems in combinatorics.The first problem is related to the Brown–Erdos–Sos conjecture, which can bereformulated as a problem of finding a dense substructure, namely a large numberof triples, spanned by a given number of elements in a quasigroup. In the special case of finite groups, we show in Chapter 2 that in every dense set of triples, there exists a subset of m elements which spans 4m/3 (1 − o(1)) triples, as m tends to infinity, which is much higher than the conjectured amount m − 3 for a general quasigroup. Later in the chapter, we give an elementary proof that, in finite groups, the maximum number of triples spanned by m elements has order m².The second problem concerns planar polygons in the 3-space. The maximum possible number of polygons from a given number of points is controlled by their intersection properties. Two hexagons in the space are said to intersect badly if their intersection consists of at least one common vertex as well as an interior point. In Chapter 3, we show that the number of hexagons on n points in 3-space without bad intersections is o(n²), under a mild assumption that the hexagons are ‘fat’. The main tool we used is the triangle removal lemma.The last problem in this dissertation is about the sum-product conjecture of Erdos and Szemeredi. The sum-product estimate concerns the larger size of the sumset and productset in terms of the size of the set itself. In Chapter 4 we prove an estimate with exponent 4/3 for the ring of quaternions and a certain family of well-conditioned matrices, using the boundedness of the kissing numbers.

View record

In this thesis, we make progress on the problem of enumerating tableaux on non-classicalshapes by introducing a general family of P-partitions that we call periodic P-partitions.Such a family of P-partitions generalizes the parallelogramic shapes, which were analysedby L´opez, Mart´ınez, P´erez, P´erez, Basova, Sun, Tewari, and van Willigenburg, and certaintruncated shifted shapes, where truncated shifted shapes were investigated by Adin, King,Roichman, and Panova. By introducing a separation property for posets and by proving arelationship between this property and P-partitions, we prove that periodic P-partitions canbe enumerated with a homogeneous first-order matrix difference equation.Afterwards, we consider families of finite sets that we call shellable and that have beencharacterized by Chang and by Hirst and Hughes as being the families of sets that admitunique solutions to Hall’s marriage problem. By introducing constructions on families of setsthat satisfy Hall’s Marriage Condition, and by using a combinatorial analogue of a shellingorder, we prove that shellable families can be characterized by using a generalized notionof hook-lengths. Then, we introduce a natural generalization of standard skew tableauxand Edelman and Greene’s balanced tableaux, then prove an existence result about such ageneralization using our characterization of shellable families.

View record

In this thesis, we study a natural noncommutative lift of the ubiquitous Schur functions, called noncommutative Schur functions. These functions were introduced by Bessenrodt, Luoto and van Willigenburg and resemble Schur functions in many regards. We prove some new results for noncommutative Schur functions that are analogues of classical results, and demonstrate that the resulting combinatorics in this setting is equally rich. First we prove a Murnaghan-Nakayama rule for noncommutative Schur functions. In other words, we give an explicit combinatorial formula for expanding the product of a noncommutative power sum symmetric function and a noncommutative Schur function in terms of noncommutative Schur functions. In direct analogy to the classical Murnaghan-Nakayama rule, the summands are computed using a noncommutative analogue of border strips, and have coefficients ±1 determined by the height of these border strips. The rule is proved by interpreting the noncommutative Pieri rules for noncommutative Schur functions in terms of box adding operators on compositions. We proceed to give a backward jeu de taquin slide analogue on semistandard reverse composition tableaux. These tableaux were first studied by Haglund, Luoto, Mason and van Willigenburg when defining quasisymmetric Schur functions. Our algorithm for performing backward jeu de taquin slides on semistandard reverse composition tableaux results in a natural operator on compositions that we call the jdt operator. This operator in turn gives rise to a new poset structure on compositions whose maximal chains we enumerate. As an application, we also give new right Pieri rules for noncommutative Schur functions that use the jdt operators, in contrast to the left Pieri rules given by Bessenrodt, Luoto and van Willigenburg.

View record

The Schur functions {s_lambda} and ubiquitous Littlewood-Richardson coefficients are instrumental in describing representation theory, symmetric functions,and even certain areas of algebraic geometry. Determining when two skewdiagrams D₁, D₂ have the same skew Schur function or determining when the difference of two such skew Schur functions SD₁ - SD₂ is Schur-positivereveals information about the structures corresponding to these functions.By defining a set of staircase diagrams that we can augment with other (skew) diagrams, we discover collections of skew diagrams for which the question of Schur-positivity among each difference can be resolved. Furthermore, for certain Schur-positive differences we give explicit formulas for computing the coefficients of the Schur functions in the difference.We extend from simple staircases to fat staircases, and carry on to diagrams called sums of fat staircases. These sums of fat staircases can also be augmented with other (skew) diagrams to obtain many instances of Schur positivity.We note that several of our Schur-positive differences become equalities of skew Schur functions when the number of variables is reduced. Finally, we give a factoring identity which allows one to obtain many of the non-trivial finite-variable equalities of skew Schur functions.

View record