Extremal Combinatorics

我的研究将集中在极端组合学上。极值集合论中的一个典型问题是，给定一个整数m和一个性质P，找出满足性质P的{1，2，…，m}的子集族的最大规模。人们也可以寻找结构或计数信息。鄂尔多斯、斯通和西蒙诺维茨的显著极值图结果就是例子。在没有子图H的m个顶点上的(简单)图G中寻找边数的渐近界。渐近界基于H的色数。有许多方法可以推广到集合系统，其中我们可以将集合解释为边。我们说一个(0，1)-矩阵是简单的，如果它没有重复的列。我们利用顶点集关联矩阵A将一个集合系统编码为一个简单的(0，1)-矩阵。设F是RxS(0，1)-矩阵。我们称F是A的一个构形，如果A有一个Rxs子矩阵，它是F的行和列排列。一个重要的例子是Kk，它是k行的所有(0，1)列的kx2k矩阵。Vapnik和Chervonenkis为计算学习理论研究了这一点，它仍然很重要。Vc维是k的最大值，因此A包含kk的副本。*Anstee和Sali猜想，没有配置F的简单m行矩阵A的最大列数可以从某个限制的乘积结构范围渐近确定(作为m的函数)。我们将继续这个猜想。*证明技术包括线性代数/多项式方法、巧妙的归纳、稳定性结果、移位、遗传算法和计算机辅助案例分析。相关的问题包括禁止模式、Sperner理论、极值图论、Ramsey理论、区组设计、覆盖阵列和区组设计。*在SALI下，当禁止大小为m的函数的配置F时，找到了一些最佳可能的界。我们还考虑了针对Anstee、Frankl、Furedi和Pach关于禁用子矩阵的猜想的禁用子矩阵的性质。使用摊销分析(来自计算机科学)。*我还将研究图论中的问题。一个例子是2mx2m的棋盘。我们能用多米诺骨牌把它盖住吗？这些与网格图中的完美匹配相对应。如果我们删除一些方块，会发生什么？或者如果我们修复一些多米诺骨牌的位置？这是对高维网格图的自然扩展，其中2mx2mx2m可以用来模拟分子结构。我们找到了顶点删除的渐近最佳可能结果。一个相关的问题是将图的边分解成具有某些性质的子图。*将图分解成匹配是边着色问题。我利用了这样一个想法，即寻找分数子图(即允许选择具有分数权重的边)是一个网络流问题。这产生了快速算法和存在定理，以及有待探索的新视角。

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.