# Talks

• From Dyck paths to standard Young tableaux. Brandeis Combinatorics Seminar, March 17, 2017.
• In what ways can we add extra structure or restrictions to Dyck paths and standard Young tableaux to yield equinumerous sets? Perhaps the most famous answer is the bijection between Dyck paths of semilength n and standard Young tableaux of shape (n,n). In this talk we will present two newer answers. In particular, we will attach a connected matching to each ascent in our Dyck paths and give a bijection from these structures to all standard Young tableaux. Also, we will give a bijection between Dyck paths without singleton ascents and standard Young tableaux of flag shape.
• Catalan numbers and generating functions. Center for Women in Mathematics, Smith College, February 16, 2017.
• Catalan numbers are one of the most ubiquitous sequences in enumerative combinatorics. They appear as the solution of hundreds of counting problems. Why are so many different objects enumerated by the same sequence of numbers? In this talk, we will start to answer this question by looking at their simple generating function.
• Combinatorics of Orthogonal Polynomials and Enumeration of Young Tableaux. Alg/Comb/Geom Seminar, Smith College, October 25, 2016.
• We will introduce the combinatorial theory of orthogonal polynomials developed by Viennot (1985) and Flajolet (1980) and then see how it can be applied to the enumeration of skew Young tableaux with at most three rows. In particular, a sequence is the moment sequence for some orthogonal polynomials if and only if it enumerates Motzkin paths with certain weights. In the simple unweighted case, the polynomials are a variant of the Chebyshev polynomials. We will use insights from the combinatorial theory of orthogonal polynomials to give a combinatorial enumeration of skew Young tableaux with at most three rows and fixed skew part as a linear combination of Motzkin numbers. We obtain a simple combinatorial proof of a refinement of earlier results. This follows work by Zeilberger (2006), Regev (2009), Sen-Peng Eu (2010) and Jong Hyun Kim (2011).
• Orthogonal polynomials, lattice paths, and skew Young tableaux. PhD Defense, July 14, 2016.
• We give two applications of the combinatorial theory of orthogonal polynomials developed by Viennot and Flajolet.
Motzkin paths are in bijection with Young tableaux with at most three rows. We want to extend this to skew Young tableau. Regev conjectured (2009), and Zeilberger proved (2006) that when the skew part is (2,1), the number of skew Young tableaux of fixed size is a difference of two Motzkin numbers. Sen-Peng Eu showed (2010) that for any fixed skew part and total size, the number can be written as a linear combination of Motzkin numbers. Jong Hyun Kim found (2011) an explicit formula for this general case which had an unexpected connection with the Chebyshev polynomials. We use insights from the combinatorial theory of orthogonal polynomials to give a combinatorial proof for skew-reduced Young tableau. The regular skew case follows. Moreover, we obtain a refinement of previous known formulas.
We will then discuss the classic Chung-Feller theorem for flawed Dyck paths, and an analog for flawed Motzkin paths by Eu, Liu, and Yeh (2002). Their result states that the number of flawed Motzkin paths of length \$n\$ with a fixed number of flaws can be expressed as a linear combination of Motzkin numbers. We will give a generalization that unifies the classic Chung-Feller theorem and the Motzkin path analog. Using orthogonal polynomials again, we will give a combinatorial interpretation for the coefficients in these linear combinations of Motzkin numbers.
• Skew Young tableaux with at most three rows, Chebyshev polynomials, and Motzkin paths. Dartmouth Combinatorics Seminar, April 14, 2016.
• Amitai Regev showed in 1981 that standard Young tableaux with at most three rows are enumerated by Motzkin numbers. More recently, he conjectured that the number of skew Young tableaux with at most three rows and skew shape (2,1) is given by a difference of two Motzkin numbers. Zeilberger proved this conjecture in 2006. In 2010, Sen-Peng Eu showed that the number of skew standard Young tableaux with at most three rows and any fixed skew part can be expressed as a linear combination of Motzkin numbers. Jong Hyun Kim found an explicit formula using Chebyshev polynomials in 2011. We will give a generalization and a combinatorial proof that explains the connection to Chebyshev polynomials by interpreting them in terms of restricted Motzkin paths and then applying a bijection to skew standard Young tableaux with at most three rows.
• Skew Young tableaux with at most three rows, Chebyshev polynomials, and Motzkin paths. MIT Combinatorics Seminar, April 6, 2016.
• Amitai Regev showed in 1981 that standard Young tableaux with at most three rows are enumerated by Motzkin numbers. More recently, he conjectured that the number of skew Young tableaux with at most three rows and skew shape (2,1) is given by a difference of two Motzkin numbers. Zeilberger proved this conjecture in 2006. In 2010, Sen-Peng Eu showed that the number of skew standard Young tableaux with at most three rows and any fixed skew part can be expressed as a linear combination of Motzkin numbers. Jong Hyun Kim found an explicit formula using Chebyshev polynomials in 2011. We will give a generalization and a combinatorial proof that explains the connection to Chebyshev polynomials by interpreting them in terms of restricted Motzkin paths and then applying a bijection to skew standard Young tableaux with at most three rows.
• Skew Young tableaux with at most three rows with Chebyshev polynomials and Motzkin paths. Graduate Student Combinatorics Conference, Clemson University, April 1-3, 2016.
• Amitai Regev showed in 1981 that standard Young tableaux with at most three rows are enumerated by Motzkin numbers. In 2010, Sen-Peng Eu showed that the number of skew standard Young tableaux with at most three rows (with fixed skew part) can be expressed as a linear combination of Motzkin numbers. Jong Hyun Kim found an explicit formula using Chebyshev polynomials. We will give a generalization and a combinatorial proof that explains the connection to Chebyshev polynomials by interpreting them in terms of restricted Motzkin paths and then applying a bijection to skew standard Young tableaux with at most three rows.
• Orthogonal polynomials and skew standard Young tableaux with at most three rows. Brandeis Combinatorics Seminar, January 19, 2016.
• Abstract: Amitai Regev showed in 1981 that standard Young tableaux with at most three rows are enumerated by Motzkin numbers. In 2010, Sen-Peng Eu showed that the number of skew standard Young tableaux with at most three rows (with fixed skew part) can be expressed as a linear combination of Motzkin numbers. Jong Hyun Kim found an explicit formula for this general case and noted a surprising connection to Chebyshev polynomials. In this talk, we will give a combinatorial proof which illuminates the connection to Chebyshev polynomials by enumerating Motzkin paths with certain restrictions and then applying a particularly nice bijection to skew standard Young tableaux with at most three rows.
• Robinson-Schensted for Lattice Paths. Penn State Altoona Colloquium, November 24, 2015.
• Abstract: The Robinson-Schensted (RS) correspondence between permutation matrices and pairs of standard Young Tableaux was first described in 1938. Knuth gave a generalization in 1970 for integer matrices. Fomin and Viennot later gave different interpretations which applied to other shapes, such as the space under a lattice path. We will use Viennot’s geometric interpretation of RS to give a short proof of Eu, Fu, Hou, and Hsu’s 2013 bijection between colored Motzkin paths and standard Young tableaux of bounded height. We can restate their result as a general property of differential lattices.
• Chain Decompositions of LYM Posets. Brandeis Combinatorics Seminar, November 3, 2015.
• Abstract: Griggs conjectured in 1975 that unimodal graded posets which satisfy the LYM inequality must have a nested chain decomposition. This would generalize symmetric chain decompositions for symmetric posets. While the conjecture remains open, several partial results have been proven. In particular, we will discuss results for posets of rank 3. This is joint work from a 2007 REU with Escamilla, Nicolae, Salerno, and Shahriari. I will reflect on the progress that we made and then open up the seminar for discussion.
• Orthogonal Polynomials and Motzkin Paths with Peak and Flat Restrictions. 8th International Conference on Lattice Path Combinatorics & Applications, August 17-20, 2015. (announcement)
• Abstract: We will look at a sequence of orthogonal polynomials related to the Chebyshev polynomials of the second kind. They can be used to count Motzkin paths with restrictions on peaks and flats as a linear combination of Motzkin numbers. We will then use these to give a combinatorial interpretation of a 2002 result by Eu, Liu, and Yeh which gave a Motzkin path generalization of Chung and Feller’s 1949 theorem stating that the number of Dyck paths with any given number of flaws (steps below zero) is independent of that number. Next, we will look at a 2011 formula from Kim for counting skew standard Young tableux with at most three rows as a linear combination of Motzkin numbers, and give a combinatorial interpretation using a bijection with Motzkin paths based on the Robinson-Schensted-Knuth algorithm.
• Counting flawed Motzkin paths by Motzkin numbers. Graduate Student Combinatorics Conference, March 27-29, 2015. (announcement)
• Abstract: Chung and Feller showed in 1949 that the number of Dyck paths with any given number of flaws (steps below zero) is independent of that number. In 2002, Eu, Liu, and Yeh showed that the number of Motzkin paths with a given number of flaws can be enumerated as an alternating linear combination of Motzkin numbers. We give a combinatorial proof of their result using the language of umbral calculus and orthogonal polynomials.
• Counting flawed Motzkin paths by Motzkin paths. Combinatorics Seminar, Brandeis University, February 24, 2015.
• Abstract: We’ll look at paths which start and end at zero and take up, down and flat steps. These are called Motzkin paths if they contain no flaws, or steps below zero. Otherwise we call them flawed Motzkin paths. Eu, Liu, and Yeh showed in 2002 that the number of flawed Motzkin paths with a fixed number of flaws can be enumerated as an alternating linear combination of Motzkin numbers. We give a combinatorial interpretation of this result.
• The Robinson-Schensted Correspondence. Graduate Student Seminar, Brandeis University, January 30, 2015.
• Abstract: The Robinson-Schensted (RS) correspondence between permutations and pairs of standard Young Tableaux was first described in 1938. Knuth generalized it in 1970 to what is commonly called the RSK correspondence, which gives a bijection between nonnegative integer matrices and pairs of semi-standard Young Tableaux of the same shape. We will introduce the RS and RSK correspondences and discuss some different perspectives such as Fomin growth. We will also look at dual RSK and the generalization to differential posets. This talk should be accessible for all graduate students.
• Enumerative Combinatorics – Multivariate Power Series. Jsoftware Conference, July 24-25 2014.
• Abstract: We introduce the use of formal power series in enumerative combinatorics and discuss how to work with infinite series in J. We show how J can be used effectively for manipulating multivariate power series, particularly in identifying patterns in series with many formal variables.
• Counting Non-crossing Trees by Descents. Combinatorics Seminar, Brandeis University, March 31, 2014.
• Abstract: A non-crossing graph is a (rooted) graph with its vertices drawn on the boundary of a disk and its edges drawn in the interior without crossing. We will count non-crossing trees by their ascent and descent edges and then find some nice bijections, in particular to connected non-crossing graphs. We will also look at a symmetrization of these numbers and the corresponding combinatorial interpretations.
• Automaticity of the Braid Group. Graduate Student Seminar, Brandeis University, March 13, 2014.
• Abstract: An automatic structure gives us finite state machines that can identify certain words and relationships between them in our group. In particular, an automatic structure gives a solution to the word problem in quadratic time. In this talk we will focus on the braid group and sketch out a construction of an automatic structure for it. This relies heavily on the intimate relationship between the braid group and the symmetric group.
• Counting Binary Trees and Hyperplane Arrangements. Combinatorics Seminar, Brandeis University, October 24, 2013.
• Abstract: Binary trees and regions of the Catalan hyperplane arrangement are among many objects counted by the Catalan numbers. When we count labelled binary trees by their number of left/right ascents/descents, we obtain a more general generating function which can be used to count certain subsets of binary trees. These numbers turn out to correspond to the numbers of regions of certain subarrangements of the Catalan arrangement. We will discuss the open problem of finding a bijective explanation for these correspondences.
• Percolation. Graduate Student Seminar, Brandeis University, February 17, 2011.
• Abstract: Percolation is the study of the component structure of random subgraphs of lattice-like graphs. Specifically, we ask at what probability p do we expect a random subgraph, where every edge is selected with independent probability p, to have an infinite component? We will answer this question for the Bethe lattice and discuss the result of Harris and Keston for the square lattice.