Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA new proof of Cayleys formula
68
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a very simple new bijective proof of Cayleys formula. The bijection is useful for the analysis of random trees, and we explain some of the ways in which it can be used to derive probabilistic identities, bounds, and growth procedures for such trees. We also introduce a partial order on the degree sequences of rooted trees, and conjecture that it induces a stochastic partial order on heights of random rooted trees with given degrees.
rate research
Read More
There are several proofs now for the stability of Tooms example of a two-dimensional stable cellular automaton and its application to fault-tolerant computation. Simon and Berman simplified and strengthened Tooms original proof: the present report is a simplified exposition of their proof.
In light of the well-known fact that the $n$th divided difference of any polynomial of degree $m$ must be zero while $m<n$,the present paper proves the $(alpha,beta)$-inversion formula conjectured by Hsu and Ma [J. Math. Res. $&$ Exposition 25(4) (2005) 624]. As applications of $(alpha,beta)$-inversion, we not only recover some known matrix
Babson and Steingr{i}msson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian statistic in terms of generalized pattern functions, which is denoted $stat$. Given a permutation $pi$, let $des(pi)$ denote the descent number of $pi$ and $maj(pi)$ denote the major index of $pi$. Babson and Steingr{i}msson conjectured that $(des,stat)$ and $(des,maj)$ are equidistributed on $S_n$. Foata and Zeilberger settled this conjecture using q-enumeration, generating functions and Maple packages ROTA and PERCY. Later, Burstein provided a bijective proof of a refinement of this conjecture. In this paper, we give a new bijective proof of this conjecture.
A typical decomposition question asks whether the edges of some graph $G$ can be partitioned into disjoint copies of another graph $H$. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of complete graphs into edge-disjoint copies of a tree. It says that any tree with $n$ edges packs $2n+1$ times into the complete graph $K_{2n+1}$. In this paper, we prove this conjecture for large $n$.
We prove a conjecture of Ohba which says that every graph $G$ on at most $2chi(G)+1$ vertices satisfies $chi_ell(G)=chi(G)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
