Investigations in Extremal Combinatorics and Graph Theory

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

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.