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

摘要

An $(n, n)$-tree is a connected, acyclic, bipartite graph with $n$ light and $n$ dark vertices. Uniform probability is assigned to the space, $Gamma(n, n)$, of $(n, n)$-trees. In this paper, we apply Hall's theorem to determine bounds for the edgeindependence numbers for almost all $(n,n)$-trees in $Gamma(n,n)$. Consequently, we find that for almost all $(n,n)$-trees the percentage of dark vertices in a maximum matching is at least.