Combinatorics (math.CO)

Abstract: By using biclique partitions of digraphs, this paper gives reduction formulas for the number of oriented spanning trees, stationary distribution vector and Kemeny's constant of digraphs. As applications, we give a method for enumerating spanning trees of undirected graphs by vertex degrees and biclique partitions. The biclique partition formula also extends the results of Knuth and Levine from line digraphs to general digraphs.

Abstract: Let $M_0(n)$ (resp. $M_1(n)$) denote the number of partitions of $n$ with even (reps. odd) crank. We establish the effective bound for the asymptotic formula for $M_0(n)-M_1(n)$ due to Choi, Kang and Lovejoy. By utilizing this formula with the explicit bound, we demonstrate that the cranks are asymptotically equidistributed modulo 2. We also use this formula to show that $(-1)^n(M_0(n)-M_1(n))>d$ for $d\geq 1$ and $n\geq \left\lceil\frac{24}{\pi^2}\left(\ln\left(\frac{7d}{2}\right)\right)^2+\frac{1}{24}\right\rceil$ which strengthens a result due to Andrews and Lewis. Moreover, we establish an upper bound and a lower bound for $M_0(n)$ and $M_1(n)$. The upper bound and the lower bound for $M_k(n)$ enable us to show that $M_k(n-1)+M_k(n+1)>2M_k(n)$ for $k=0$ or $1$ and $n\geq 39$. This result can be seen as the refinement of the classical result regarding the convexity of the partition function $p(n)$, which counts the number of partitions of $n$. We also show that $M_0(n)$ (resp. $M_1(n)$) is log-concave for $n\geq 94$ and satisfies the higher order Tur\'an inequalities for $n\geq 207$ with the aid of the upper bound and the lower bound for $M_0(n)$ and $M_1(n)$.