On the edge independence number of a random (N,N)-tree

In this paper we study the asymptotic behavior of the edge independence number of a random (n,n)-tree. The tools we use include the matrix-tree theorem, the probabilistic method and Hall's theorem. We begin with some definitions. An (n,n)_tree T is a connected, acyclic, bipartite graph with n light and n dark vertices (see [Pa92]). A subset M of edges of a graph is called independent(or matching) if no two edges of M are adfacent. A subset S of vertices of a graph is called independent if no two vertices of S are adjacent. The edge independence number of a graph T is the number $eta_1(T)$ of edges in any largest independent subset of edges of T. Let $Gamma(n,n)$ denote the set of all (n,n)-tree with n light vertices labeled 1, $ldots$, n and n dark vertices labeled 1, $ldots$, n. We give $Gamma(n,n)$ the uniform probability distribution. Our aim in this paper is to find bounds on $eta_1$(T) for a random (n,n)-tree T is $Gamma(n,n)$.