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维在学习理论、超图中的横截面和计算几何中都有应用。我们希望我们可以为我们的问题制定界限，这些问题可能会以类似的方式得到应用。 考虑一个m×m的黑白棋盘，其中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.