Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200416November 2004 
Nicholas Georgiou
Abstract
Let T^{n} be the complete binary tree of height n, with root 1_{n} as the maximum element. For T a tree, define A(n;T) to be the number of subtrees S of T^{n}, with S isomorphic to T and 1_{n} in S, and define C(n;T) to be the total number of subtrees S of T^{n} with S isomorphic to T. We disprove a conjecture of Kubicki, Lehel and Morayne, which claims that A(n;T_{1})/C(n;T_{1}) ≤ A(n;T_{2})/C(n;T_{2}) for any fixed n and arbitrary rooted trees T_{1}, T_{2} with T_{1} a subtree of T_{2} . We show that A(n;T) is of the form where l is the number of leaves of T, and each q_{j} is a polynomial. We provide an algorithm for calculating the two leading terms of q_{l} for any tree T. We investigate the asymptotic behaviour of the ratio A(n;T)/C(n;T) and give examples of classes of pairs of trees T_{1}, T_{2} where it is possible to compare A(n;T_{1})/C(n;T_{1}) and A(n;T_{2})/C(n;T_{2}). By calculating these ratios for a particular class of pairs of trees, we show that the conjecture fails for these trees, for all sufficiently large n. Kubicki, Lehel and Morayne have proved the conjecture when T_{1}, T_{2} are restricted to being binary trees. We also look at embeddings into other complete trees, and we show how the result can be viewed as one of many possible correlation inequalities for embeddings of binary trees. We also show that if we consider strict orderpreserving maps of T_{1}, T_{2} into T^{n} (rather than embeddings) then the corresponding correlation inequalities for these maps also generalise to arbitrary trees.
A PDF file (268 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200416, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7732. Fax: +44(0)207955 6877. Email: info@cdam.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html