Combinatorial structures and generating functions of Fishburn numbers, parking functions, and Tesler matrices

This dissertation reflects the author\u27s work on two problems involving combinatorial structures. The first section, which was also published in the Journal of Combinatorial Theory, Series A, discusses the author\u27s work on several conjectures relating to the Fishburn numbers. The Fishburn numbers can be defined as the coefficients of the generating function [special characters omitted] Combinatorially, the Fishburn numbers enumerate certain supersets of sets enumerated by the Catalan numbers. We add to this work by giving an involution-based proof of the conjecture of Claesson and Linusson that the Fishburn numbers enumerate non-2-neighbor-nesting matchings. We begin by proving that a map originally defined by Claesson and Linusson gives a bijection between non-2-neighbor-nesting matchings and (2-1)-avoiding inversion tables. We then define a set of diagrams, which we call Fishburn diagrams, that give a natural interpretation to the generating function of the Fishburn numbers. Using an involution on Fishburn diagrams, we then prove that the Fishburn numbers enumerate (2-1)-avoiding inversion tables. By using two variations of this involution on two subsets of Fishburn diagrams, we then give a visual proof of the conjecture of Remmel and Kitaev that two bivariate refinements of the generating function of the Fishburn numbers are equivalent. In an appendix, we give an inductive proof of the conjecture of Claesson and Linusson that the distribution of left-nestings over the set of all matchings is given by the second-order Eulerian triangle. The conjecture of Remmel and Kitaev was independently proved by Jelin\u27ek and by Yan with a matrix interpretation defined by Dukes and Parviainen. Bijections surveyed by Callan can lead to a similar proof of the conjecture of Claesson and Linusson giving the distribution of left-nestings over matchings, using a result on the Stirling permutations due to Gessel and Stanley. This work was done independently. The second section, some of which was presented at the Formal Power Series and Algebriac Combinatorics conference (FPSAC), discusses the author\u27s work on several conjectures relating to parking functions and to Tesler matrices. Parking functions are combinatorial objects which generalize both permutations and Catalan paths. Haglund and Loehr conjectured that the generating functions of two statistics, area and dinv, over the set of parking functions (the q, t-parking functions) gives the Hilbert series of the diagonal coinvariants. Haglund recently proved that this Hilbert series is given by another generating function over the set of matrices with every hook sum equal to one ( Tesler matrices ). We prove several structural results on parking functions inspired by Tesler matrices, including a near-recursive generation of the q, t-parking functions. We also give consistent bijective proofs of several special cases of Haglund\u27s Tesler function identity, giving a combinatorial connection between parking functions and Tesler matrices, and discuss related conjectures. A connection between the q = 1 special case and a result of Kreweras was later pointed out by Garsia et al., and some of the original ideas on the q = 1 special case arose from a discussion between the author, Haglund, Bandlow, and Visontai