Structural Combinatorics

结构组合学

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

I pursue a broad research program in combinatorics which is themed by the search for structural understanding of exceptional phenomena. This summary is divided according to the major topics which I intend to study over the next 5 years. **Combinatorial Number Theory*One of the fundamental problems in this subject is to describe finite subsets A,B of a (multiplicative) group for which the product set AB has small size. The first deep contribution to this program (for G=Z) was due to Freiman, and subsequently refined by Ruzsa. Recent work by numerous authors have revealed the significance of this problem to the world of additive combinatorics and beyond. A new breakthrough by Breulliard, Green, and Tao gives a powerful rough structure theorem which applies in arbitrary groups. However, much work remains to be done to gain a more precise understanding. My work in this area concerns the extreme case when |AB| is very small (in this realm the subject is highly combinatorial). In the case when |AB| < |A| + |B|, I have recently completed a precise structure theorem describing the sets. Together with my Ph.D. student, Tom Boothby, we have begun to characterize those sets with |AB| = |A| + |B|, and going forward, I hope to pursue the structure of sets with |AB| < |A| + |B| + c for a fixed constant c. A rough structure theorem for this case would be extremely useful in (mathematical) applications. **There many crossovers between graph theory and additive number theory, and I am especially interested in this connection. Together with Mohar, I have proved a rough structure theorem for small separations in vertex transitive graphs which has applications in both graph theory and combinatorial number theory. There are numerous directions to push forward here (ex. a generalization to digraphs) which I believe would make suitable projects for students. Another crossover problem is to give bounds on the average degree of a power of a regular graph. Together with McDonald and Scheide, I have recently proved a tight bound on this for powers which are 2 (mod 3). Extending these results from graphs to digraphs would be extremely valuable for both extremal graph theory and additive combinatorics. **Graph Immersion*Immersion is a natural containment operation in graphs which has received relatively little attention in comparison to graph minors. Robertson and Seymour have famously shown that graphs are well-quasi-ordered under immersion, but very little is understood about structural properties of this relation. Recently I have collaborated with various groups of colleagues to study immersion. Our most notable results include a theorem demonstrating that every simple graph of minimum degree 200t immerses the complete graph K_t and a rough structure theorem for graphs which do not immerse a given graph. There are numerous important directions for future research here. Indeed, I am working on such problems at present with two Masters students. Together with Mahdieh Malekian (and McDonald) we are working toward a precise characterization of the graphs which do not immerse K_5 or K_{3,3}, and together with Stefan Hannie (and Mohar and Archdeacon) we are studying immersion of 2-regular digraphs.**Matroid Minors*The matroid minors project of Geelen, Gerards, and Whittle has established a powerful theory of matroids which are representable over a fixed finite field. This work also has promoted the study of certain matroids which are quite close to graphs called frame matroids. As a first step toward understanding these matroids, my Ph.D. student Daryl Funk and Goddyn and I have proved a representation theorem for these matroids which we believe will be useful in understanding their structure, our eventual goal.

我在组合学方面有一个广泛的研究项目，其主题是寻找对特殊现象的结构性理解。这个总结是根据我未来5年打算研究的主要课题进行划分的。**组合数论*本学科的一个基本问题是描述乘积集AB较小的（乘法）群的有限子集A，B。对这个程序（对于G=Z）的第一个深刻贡献是由于Freiman，随后由Ruzsa改进。许多作者最近的工作揭示了这个问题对加性组合学和其他领域的重要性。Breulliard， Green和Tao的新突破给出了一个适用于任意群的强大的粗糙结构定理。然而，为了获得更精确的理解，还有很多工作要做。我在这个领域的工作涉及|AB|非常小的极端情况（在这个领域，这个主题是高度组合的）。在|AB| < |A| + |B|的情况下，我最近完成了一个描述集合的精确结构定理。与我的博士生Tom Boothby一起，我们已经开始用|AB| = |A| + |B|来描述这些集合的特征，并且我希望继续追求|AB| < |A| + |B| + c的固定常数c的集合结构。这种情况下的粗略结构定理将在（数学）应用中非常有用。**图论和加性数论之间有很多交叉，我对这种联系特别感兴趣。我与Mohar一起证明了顶点传递图中小分离的粗糙结构定理，该定理在图论和组合数论中都有应用。这里有许多方向可以推进（例如对有向图的概括），我相信这将成为适合学生的项目。另一个交叉问题是给出正则图的幂次的平均次的界。最近，我与McDonald和Scheide一起证明了幂为2 （mod 3）的紧界。将这些结果从图扩展到有向图，对于极值图论和加性组合学都是非常有价值的。**图浸入式*浸入式是图中的自然包含操作，与图的次要操作相比，它受到的关注相对较少。Robertson和Seymour已经证明了图形在浸入状态下是准有序的，但对这种关系的结构性质了解甚少。最近我和不同小组的同事合作研究浸入式。我们最值得注意的结果包括一个定理，证明每个最小度为200t的简单图都浸入完全图K_t，以及一个不浸入给定图的图的粗糙结构定理。这里有许多重要的未来研究方向。事实上，我目前正在和两位硕士生一起研究这些问题。与Mahdieh Malekian（和McDonald）一起，我们正在研究不浸入K_5或K_{3,3}的图的精确表征，与Stefan Hannie（和Mohar和Archdeacon）一起，我们正在研究2正则有向图的浸入。Geelen， Gerards和Whittle的矩阵子项目建立了一个强大的矩阵子理论，这些矩阵子可以在一个固定的有限域上表示。这项工作也促进了对某些与图非常接近的称为框架拟阵的拟阵的研究。作为理解这些拟阵的第一步，我的博士生Daryl Funk和Goddyn和我已经证明了这些拟阵的一个表示定理，我们相信这将有助于理解它们的结构，我们的最终目标。