CSUN Algebra, Number Theory, and Discrete Mathematics Seminar

We say that a permutation $\pi ={\pi }_1{\pi }_2\cdots {\pi }_n\in {\mathfrak{𝔖}}_n$ has a peak at index $i$ if ${\pi }_{i-1}<{\pi }_i>{\pi }_{i+1}$. Let $\P \left(\pi \right)$ denote the set of indices where $\pi$ has a peak. Given a set $S$ of positive integers, we define $\P \left(S;n\right)=\left\{\pi \in {\mathfrak{𝔖}}_n:\P \left(\pi \right)=S\right\}$. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers $S$ and sufficiently large $n$, $|\P \left(S;n\right)|=p_S\left(n\right)2^{n-\left|S\right|-1}$ where $p_S\left(x\right)$ is a polynomial depending on $S$. They gave a recursive formula for $p_S\left(x\right)$ involving an alternating sum, and they conjectured that the coefficients of $p_S\left(x\right)$ expanded in a binomial coefficient basis centered at $max\left(S\right)$ are all nonnegative. In this talk we introduce a new recursive formula for $|\P \left(S;n\right)|$ without alternating sums and we use this recursion to prove that their conjecture is true. Moreover, we develop a generalization of peak polynomials to graphs that is consistent with the $S_n$ case and explore positivity therein.