Discrete mathematics

我建议继续在离散数学的广阔领域进行研究，重点关注两个领域：极值集理论和匹配极值集理论考虑{1,2，…， m}，并且，给定一些强加给家庭的财产，问你是否可以限制家庭的规模。在没有性质的情况下，你得到的是2的界的m次方，如果你利用这个性质即族中的每一对集合相交，那么我们得到的是2的界的m-1次方。考虑到{1,2，…的每个子集，很容易看出这是正确的， m}可以与其补体配对，并且最多只能选择两个集合中的一个作为家族。我要考虑的一些性质被称为禁止构型。鉴于禁止构型性质的基本性质，期望找到这些结果的应用。这些属性（被称为vc维）已经在学习理论和计算几何中得到了应用。在Sali的帮助下，我们提出了一个美丽的猜想，这个猜想表明，在被禁止的构型中，哪些结构真正驱动了渐近边界。给定一个2mx2m的棋盘，有人会问你是否可以用多米诺骨牌覆盖它；每个多米诺骨牌覆盖两个方块。这个问题很简单，事实上，Kastelyn计算了大量可能的方法（将其用于统计力学）。你能在破坏棋盘的同时用多米诺骨牌找到掩护吗？例如，你可以问如果你删除一些平方会发生什么。显然，您需要删除相同数量的黑色和白色方块，因为每个多米诺骨牌覆盖每种颜色的一个方块。如果你加上一个简单的要求，即删除的黑色方块要相距很远（至少4乘以m的平方根），并且对删除的白色方块也有同样的限制，那么覆盖仍然是可能的。此外，在距离中使用m的平方根是最好的。这些问题最好用图论来描述；这些覆盖物被称为匹配物。对一些敏感图形的调查仍在继续。

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.