Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA symmetry on weakly increasing trees and multiset Schett polynomials
98
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
By considering the parity of the degrees and levels of nodes in increasing trees, a new combinatorial interpretation for the coefficients of the Taylor expansions of the Jacobi elliptic functions is found. As one application of this new interpretation, a conjecture of Ma-Mansour-Wang-Yeh is solved. Unifying the concepts of increasing trees and plane trees, Lin-Ma-Ma-Zhou introduced weakly increasing trees on a multiset. A symmetry joint distribution of even-degree nodes on odd levels and odd-degree nodes on weakly increasing trees is found, extending the Schett polynomials, a generalization of the Jacobi elliptic functions introduced by Schett, to multisets. A combinatorial proof and an algebraic proof of this symmetry are provided, as well as several relevant interesting consequences. Moreover, via introducing a group action on trees, we prove the partial $gamma$-positivity of the multiset Schett polynomials, a result implies both the symmetry and the unimodality of these polynomials.
rate research
Read More
A graph polynomial $P$ is weakly distinguishing if for almost all finite graphs $G$ there is a finite graph $H$ that is not isomorphic to $G$ with $P(G)=P(H)$. It is weakly distinguishing on a graph property $mathcal{C}$ if for almost all finite graphs $Ginmathcal{C}$ there is $H in mathcal{C}$ that is not isomorphic to $G$ with $P(G)=P(H)$. We give sufficient conditions on a graph property $mathcal{C}$ for the characteristic, clique, independence, matching, and domination and $xi$ polynomials, as well as the Tutte polynomial and its specialisations, to be weakly distinguishing on $mathcal{C}$. One such condition is to be addable and small in the sense of C. McDiarmid, A. Steger and D. Welsh (2005). Another one is to be of genus at most $k$.
For a finite subset $A$ of $mathbb{Z}_{>0}$, Lazar and Wachs (2019) conjectured that the number of cycles on $A$ with only even-odd drops is equal to the number of D-cycles on $A$. In this note, we introduce cycles on a multiset with only even-odd drops and prove bijectively a multiset version of their conjecture. As a consequence, the number of cycles on $[2n]$ with only even-odd drops equals the Genocchi number $g_n$. With Laguerre histories as an intermediate structure, we also construct a bijection between a class of permutations of length $2n-1$ known to be counted by $g_n$ invented by Dumont and the cycles on $[2n]$ with only even-odd drops.
The study of Markov processes and broadcasting on trees has deep connections to a variety of areas including statistical physics, phylogenetic reconstruction, MCMC algorithms, and community detection in random graphs. Notably, the celebrated Belief Propagation (BP) algorithm achieves Bayes-optimal performance for the reconstruction problem of predicting the value of the Markov process at the root of the tree from its values at the leaves. Recently, the analysis of low-degree polynomials has emerged as a valuable tool for predicting computational-to-statistical gaps. In this work, we investigate the performance of low-degree polynomials for the reconstruction problem on trees. Perhaps surprisingly, we show that there are simple tree models with $N$ leaves where (1) nontrivial reconstruction of the root value is possible with a simple polynomial time algorithm and with robustness to noise, but not with any polynomial of degree $N^{c}$ for $c > 0$ a constant, and (2) when the tree is unknown and given multiple samples with correlated root assignments, nontrivial reconstruction of the root value is possible with a simple, noise-robust, and computationally efficient SQ (Statistical Query) algorithm but not with any polynomial of degree $N^c$. These results clarify some of the limitations of low-degree polynomials vs. polynomial time algorithms for Bayesian estimation problems. They also complement recent work of Moitra, Mossel, and Sandon who studied the circuit complexity of Belief Propagation. We pose related open questions about low-degree polynomials and the Kesten-Stigum threshold.
In this note, by the umbra calculus method, the Sun and Zagiers congruences involving the Bell numbers and the derangement numbers are generalized to the polynomial cases. Some special congruences are also provided.
A di-sk tree is a rooted binary tree whose nodes are labeled by $oplus$ or $ominus$, and no node has the same label as its right child. The di-sk trees are in natural bijection with separable permutations. We construct a combinatorial bijection on di-sk trees proving the two quintuples $(LMAX,LMIN,DESB,iar,comp)$ and $(LMAX,LMIN,DESB,comp,iar)$ have the same distribution over separable permutations. Here for a permutation $pi$, $LMAX(pi)/LMIN(pi)$ is the set of values of the left-to-right maxima/minima of $pi$ and $DESB(pi)$ is the set of descent bottoms of $pi$, while $comp(pi)$ and $iar(pi)$ are respectively the number of components of $pi$ and the length of initial ascending run of $pi$. Interestingly, our bijection specializes to a bijection on $312$-avoiding permutations, which provides (up to the classical {em Knuth--Richards bijection}) an alternative approach to a result of Rubey (2016) that asserts the two triples $(LMAX,iar,comp)$ and $(LMAX,comp,iar)$ are equidistributed on $321$-avoiding permutations. Rubeys result is a symmetric extension of an equidistribution due to Adin--Bagno--Roichman, which implies the class of $321$-avoiding permutations with a prescribed number of components is Schur positive. Some equidistribution results for various statistics concerning tree traversal are presented in the end.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
