The maximum number of non-crossing straight-line perfect matchings that a set of n points in the plane can have is known to be O(10.0438n) and Ω*(3n), where the Ω* notation hides polynomial factors in the aymptotic expression. The lower bound, due to García, Noy, and Tejel (2000), is attained by the double chain, which has Θ(3n/nΘ(1)) such matchings. We reprove this bound in a simplified way that uses the novel notion of down-free matchings. We then apply this approach to several other constructions. As a result, we improve the lower bound: First we show that the double zigzag chain with n points has Θ*(λn) non-crossing perfect matchings with λ≈3.0532. Next we analyze further generalizations of double zigzag chains: double r-chains. The best choice of parameters leads to a construction that has Θ*(μn) non-crossing perfect matchings with μ≈3.0930. The derivation of this bound requires an analysis of a coupled dynamic-programming recursion between two infinite vectors.
Moral: Don't count your boobies until they are hatched matched.