Discrete mathematics

点击翻译按钮获取中文摘要

I propose to continue research in the broad area of Discrete Mathematics with a focus on two areas: Extremal Set Theory and Matchings  Extremal Set Theory considers a family of subsets of {1,2,..., m}  and, given some property imposed on the family, asks whether you can bound the size of the family. With no property, you get the bound of 2  raised to the power m. If you use the property that every pair of sets in the family intersect, then we get the bound 2 raised to the power m-1. This is easily seen to be true by considering that each subset  of  {1,2,.., m}  can be paired with its complement and at most one of the two sets can be chosen for the family. Some of the properties that I will be considering are called forbidden configurations.   Given the elementary nature of the forbidden configuration property, it is expected to find applications of these results. These properties (under the name VC-dimension) have found applications to Learning Theory and Computational Geometry. With Sali, we have developed a beautiful conjecture that suggests what structures inside the forbidden configuration really drive the asymptotic bounds.  Given a 2mx2m checkerboard, one can ask whether you can cover it with dominoes; each domino covering two squares. This problem is easy and in fact Kastelyn counted  the large number of possible ways to do so (using this for statistical mechanics). Can you disrupt the checkerboard and still find a covering by dominoes? For example you could ask what happens if you delete some squares. Obviously you need to delete an equal number of black and white squares since each domino covers one square of each colour. If you add the simple requirement that the deleted black squares be far apart (at least 4 times square root of m) and the same restriction on the deleted whites then a covering is still possible. Moreover the use of square root of m in the distance is best possible.  These  problems are best described in  graph theory; the coverings are called matchings.  Investigations on some sensible graphs are continuing.