Extremal Combinatorics

极值组合学

• 批准号: RGPIN-2018-03732
• 负责人: Anstee, Richard
• 金额: $ 1.17万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=675733
• 关键词: Extremal; Combinatorics

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.

我的研究重点是极值组合学。 极值集合论中的一个典型问题是，给定整数 m 和属性 P，找到满足属性 P 的 {1,2,..,m} 子集族的最大大小。人们还可以寻求结构或枚举信息。 Erdos、Stone 和 Simonovits 出色的极值图结果提供了例子。人们在没有子图 H 的 m 个顶点上寻找（简单）图 G 中边数的渐近界限。渐近界限基于 H 的色数。有多种方法可以推广到集合系统，其中我们可以将集合解释为边。如果一个 (0,1) 矩阵没有重复的列，我们就说它是简单的。我们使用顶点集关联矩阵 A 将集合系统编码为简单的 (0,1) 矩阵。子图概括如下。令 F 为 rxs (0,1) 矩阵。 如果 A 的 rxs 子矩阵是 F 的行和列排列，我们就说 F 是 A 的配置。我们考虑禁止配置。一个重要的例子是 Kk，即所有 (0,1) 列、k 行的 kx2k 矩阵。 Vapnik 和 Chervonenkis 针对计算学习理论对此进行了研究，并且它仍然很重要。 VC 维是 k 的最大值，使得 A 包含 Kk 的副本。 ****** Anstee 和 Sali 推测，没有配置 F 的简单 m 行矩阵 A 中的最大列数可以从乘积构造的某个受限范围渐近确定（作为 m 的函数）。 我们将继续研究这个猜想。 ****** 证明技术包括线性代数/多项式方法、巧妙归纳、稳定性结果、平移、遗传算法和计算机辅助案例分析。 相关问题包括禁止模式、Sperner 理论、极值图论、Ramsey 理论、块设计、覆盖数组和块设计。******使用 Sali，当禁止大小为 a 的配置 F 时，找到了一些最佳可能的边界。 m 的函数。我们还考虑了禁止子矩阵的性质，旨在解决 Anstee、Frankl、Furedi 和 Pach 对禁止子矩阵的猜想。使用摊销分析（来自计算机科学）。 ******我还将研究图论中的问题。 一个示例问题是 2mx2m 棋盘。我们可以用多米诺骨牌覆盖它吗？这些对应于网格图中的完美匹配。 如果我们删除一些方块会发生什么？或者我们是否修复一些多米诺骨牌的位置？ 这可以自然扩展到更高维度的网格图，其中 2mx2mx2m 可以用于模拟分子结构。 我们发现顶点删除的渐进最佳结果。 一个相关的问题是将图的边分解为具有某些属性的子图。***将图分解为匹配项是边着色问题。 我利用了这样的想法：寻找分数子图（即允许使用分数权重选择边）是一个网络流问题。这产生了快速算法和存在定理以及有待探索的新观点。