Investigations in Extremal Combinatorics and Graph Theory

我的研究将遵循两个主线：极值组合学和匹配理论。对于第一个问题，我首先描述一个初等极值集问题。有2^m个{1,2，…，m}的子集。{1,2，…，m}是否可以选择使每一对子集都有一个非空交集？答案是2^(m-1)=1/2 x 2^m。上界的证明很巧妙：将每个集合与其补集配对。我们只能从两者中选择一个，因为集合和它的补集不相交。当我们禁止一个给定的子结构时，我们考虑了限定集合数目的相关极值问题，得到了多项式界而不是指数界。这与有界vc维的概念有关，这是一种比较粗糙的度量。vc维在学习理论、超图中的截线和计算几何中都有应用。我们希望能够为我们的问题开发出边界，这些边界可能以类似的方式得到应用。考虑一个mxm黑白棋盘，其中m为偶数。当然，有很多方法可以用多米诺骨牌（1x2块）覆盖棋盘的正方形。如果我们删除黑色方块B‘和白色方块W’会发生什么？剩下的被刺穿的木板能被多米诺骨牌覆盖吗？我们当然需要B‘和W’的大小相等（每个多米诺骨牌覆盖一个白色和一个黑色方块）。如果我们要求被删除的方块B’的距离至少是常数乘以√m（对于W’也是如此），那么我们可以证明剩下的被刺穿的棋盘可以被多米诺骨牌覆盖。而且距离因子m的平方根是最优的。我们把它扩展到d维板。这是一个图匹配问题（多米诺骨牌变成边）。有趣的是，该证明使用了一种拓扑学论证，这种论证最初用于数字图像分析和渗透理论。我们将沿着这条路线研究其他匹配问题。

My research will follow two main threads: Extremal Combinatorics and Matching Theory. For the first problem area I first describe an elementary extremal set problem. There are 2^m subsets of{1,2,...,m}. How many subsets of {1,2,...,m} can you choose so that every pair of subsets have an non-empty intersection? The answer is 2^(m-1)=1/2 x 2^m. The proof of the upper bound is ingenious: pair up each set with its complement. We can only choose one of the two since a set and its complement don't intersect. We consider related extremal problem bounding the number of sets when we are forbidding a given substructure and get polynomial rather than exponential bounds. This relates to the concept of bounded VC-dimension which is a somewhat coarser measure. VC-dimension has had applications to Learning Theory, transversals in Hypergraphs, and computational geometry. We hope that we can develop bounds for our problems that may find application in a similar way. Consider a mxm black/white checkerboard with m even. There are of course many ways to cover the squares of the checkerboard by dominoes (1x2 pieces). What happens if we delete black squares B' and white squares W'. Can the remaining punctured board be covered by dominoes? We certainly need B' and W' to be of equal size (each domino covers one white and one black square). If we require that the deleted squares B' be at distance at least constant times square root of m (and the same for W') then we can show that the remaining punctured board can be covered by dominoes. Moreover the factor square root of m in the distance is optimal. We have extended this to d-dimensional boards. This is a graph matching problem (dominoes become edges). Interestingly the proof uses a topological argument first used in analysis of digital images and also in percolation theory. We will be pursuing other matching problems along these lines.