Extremal Combinatorics

我的研究将集中于极值组合学。极值集理论中的一个典型问题是，给定一个整数m和一个性质P，求出{1,2，…，m}，满足性质p。也可以寻找结构的或枚举的信息。Erdos、Stone和Simonovits的显著极值图结果提供了例子。一个（简单）图G在m个没有子图h的顶点上寻找边的数目的渐近边界，渐近边界是基于h的色数的。有许多方法可以推广到集合系统，我们可以把集合解释为边。我们说（0,1）矩阵是简单的如果它没有重复的列。我们使用顶点集关联矩阵a将集合系统编码为一个简单的(0,1)-矩阵。设F是一个rxs（0,1）矩阵。我们说F是a的一个构型如果a有一个rxs子矩阵它是F的一个行和列排列我们考虑禁止构型。一个重要的例子是Kk， kx2k矩阵包含所有（0,1）列和k行。Vapnik和Chervonenkis在《计算学习理论》中研究了这一点，它仍然很重要。vc维是k的最大值，使得A包含Kk的副本。

My research will focus on Extremal Combinatorics. A typical problem in Extremal Set Theory is, given an integer m and a property P, to find the largest size of a family of subsets of {1,2,..,m} which satisfy property P. One can also seek structural or enumerative information. The remarkable extremal graph results of Erdos, Stone and Simonovits provide examples. One seeks asymptotic bounds on the number of edges in a (simple) graph G on m vertices with no subgraph H. The asymptotic bounds are based on the chromatic number of H. There are a number of ways to generalize to set system, where we can interpret the sets as edges. We say a (0,1)-matrix is simple if it has no repeated columns.We encode a set system as a simple (0,1)-matrix using the vertex-set incidence matrix A. A subgraph generalizes as follows. Let F be an rxs (0,1)-matrix. We say F is a configuration of A if there is an rxs submatrix of A which is a row and column permutation of F. We consider forbidden configurations. An important example is Kk, the kx2k matrix of all (0,1)-columns with k rows. Vapnik and Chervonenkis studied this for Computational Learning Theory and it remains important. The VC-dimension is the largest value of k so that A contains a copy of Kk. Anstee and Sali conjectured that the maximum number of columns in a simple m-rowed matrix A that has no configuration F can be determined asymptotically (as a function of m) from a certain restricted range of product constructions. We will pursue this conjecture. Proof techniques include linear algebra/polynomial methods, clever inductions, Stability results, Shifting, Genetic algorithms and computer aided case analysis. Related problems include forbidden patterns, Sperner Theory, extremal graph theory, Ramsey Theory, Block designs, covering arrays, and block designs. With Sali, some best possible bounds were found when forbidding a configuration F whose size is a function of m. We also consider the property of a forbidden submatrix aiming for the conjecture of Anstee, Frankl, Furedi and Pach on Forbidden submatrices. Amortized analysis (from Computer Science) is used. I will also investigate problems in Graph Theory. A sample problem is the 2mx2m checkerboard. Can we cover it in dominoes? These correspond to perfect matchings in the grid graph. What happens if we delete some squares? Or if we fix the placement of some dominoes? This has natural extensions to grid graphs in higher dimension where the 2mx2mx2m can serve to model molecular structure. We found asymptotically best possible results for vertex deletion. A related problem is decomposing the edges of a graph into subgraphs with certain properties. Decomposing a graph into matchings is the edge colouring problem. I exploit the idea that looking for fractional subgraphs (that is, allowing an edge to be chosen with a fractional weight) is a network flow problem. This yields fast algorithms and existence theorems and new perspectives to be explored.