October 28, 1999

Point Sets which Admit Many Non-Crossing Matchings

        My plan is for us to get back to the problem
of finding point sets which admit many non-crossing
matchings.  We agreed that convex sets admit ~4^n
matchings (Catalan numbers).  I can/will show you a set of
points which have ~6^n matchings -- but can you do better??
I am sure there are grounds to improve this signficantly...

See you tommorow
Steve


From jsbm@amirani.ams.sunysb.edu Fri Oct 29 13:38:52 1999


The upper bound on the number of triangulations is about 2^{8.2 n}.
It is in the paper:  http://www.dgp.toronto.edu/cccg/cccg97/papers/43/43.html

An earlier paper, which may be very relevant to our discussions today,
is 

@article{acns-cfs-82
, author =      "M. Ajtai and V. Chv{\'a}tal and M. Newborn and E. 
Szemer{\'e}di"
, title =       "Crossing-free subgraphs"
, journal =     "Ann. Discrete Math."
, volume =      12
, year =        1982
, pages =       "9--12"
, update =      "98.03 agarwal+bibrelex"
}