Graph Homomorphisms Between Trees And Permutation Statistics

In this dissertation, we study both the extremal problems of counting graph homo-morphisms between trees and the combinatorial properties of some polynomials related with the classical permutation statistics, namely, the q-Eulerian polynomials and some polynomials arising in the diagonal generating function of Jacobi-Stirling numbers. The content are mainly consist of the following two parts.In the first part we study the number of graph homomorphisms between trees. We obtain a simple formula for the number of homomorphisms between paths and apply it to solve an open problem of Michels and Knauer about the number of congruence classes of paths. We find an algorithm for the number of homomorphisms from a tree to a graph. Using this algorithm, several transformations on trees and some Markov chains and entropies on some special trees, we prove that among all trees with fixed number of vertices, the path has the least endomorphisms while the star has the most.In the second part we study the permutation statistics.Four classical statistics on permutations are descents, excedances, inversion numbers and major index. Recently, Shareshian and Wachs studied the polynomials of the joint distribution of excedances and major index, called the q-Eulerian polynomials, and obtain a nice formula for the exponential generating function of these polynomials. Using this formula, Chung and Graham proved two symmetrical identities for the q-Eulerian polynomials and asked for bijective proofs. We provide such proof using a new interpretation of the q-Eulerian polynomials due to Foata and Han. We also prove a new recurrence formula for the q-Eulerian polynomials and study a q-analogue of Chung and Graham’s restricted de-scent polynomials. In particular, we find a generalized symmetrical identity for these restricted q-Eulerian polynomials with a combinatorial proof. Moreover, we define a new statistic equidistributed with the fixed points, which together with descents and a statistic arising from poset topology called admissible inversions gives a new inter-pretation of the fixed point q-Eulerian polynomials. On the other hand, we also study the descent statistic on some special Stirling permutations, which gives the combinato-rial interpretation of some polynomials arising from the diagonal generating function of Jacobi-Stirling numbers.