Structural Combinatorics

结构组合学

• 批准号: RGPIN-2014-06301
• 负责人: DeVos, Matthew
• 金额: $ 1.31万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612146
• 关键词: 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年内研究的主要课题划分的。 组合数论 在这个主题中的基本问题之一是描述有限子集A，B的（乘法）组的产品集AB具有小的大小。对这个程序（G=Z）的第一个深刻贡献是由于Freiman，随后由Ruzsa改进。许多作者最近的工作揭示了这个问题对加法组合学和其他领域的重要性。Breulliard，绿色，和陶的一个新的突破给出了一个强大的粗糙结构定理，适用于任意群。然而，要获得更准确的理解，还有许多工作要做。我在这方面的工作涉及极端情况，|AB|是非常小的（在这个领域的主题是高度组合）。时的情况下|AB| < |一| + |B|，我最近完成了一个描述集合的精确结构定理。加上我的博士学位。学生，汤姆·布斯比，我们已经开始用|AB| = |一| + |B|，并展望未来，我希望追求集的结构，|AB| < |一| + |B| + c为固定常数c。这种情况下的粗糙结构定理在（数学）应用中非常有用。 图论和加法数论之间有许多交叉，我对这种联系特别感兴趣。与Mohar一起，我证明了一个粗糙的结构定理，小分离的顶点传递图，这在图论和组合数论的应用。有许多方向可以向前推进（例如。对有向图的推广），我相信这将为学生提供合适的项目。另一个交叉问题是给出正则图的幂的平均度的界。与麦克唐纳和Scheide一起，我最近已经证明了对于2（mod 3）的权力，这是一个严格的约束。将这些结果从图推广到有向图，对于极值图论和加法组合学都是非常有价值的。 图形沉浸 浸入是图中的一种自然包含操作，与图子项相比，它受到的关注相对较少。Robertson和Seymour已经证明了图在浸入下是良好准序的，但是对于这种关系的结构性质知之甚少。最近，我与不同的同事合作研究浸入式教学。我们最显著的结果包括一个定理，证明了每个最小度为200 t的简单图都浸入完全图K_t，以及一个不浸入给定图的图的粗结构定理。这里有许多未来研究的重要方向。事实上，我目前正在与两名硕士生研究这些问题。我们与Mahdieh Malekian（和McDonald）一起致力于不浸入K_5或K_{3，3}的图的精确刻画，并与Stefan Hannie（和Mohar和Archdeacon）一起研究2-正则有向图的浸入。 副拟阵 Geelen，Gerards和Whittle的拟阵子项目建立了一个强大的拟阵理论，它在固定的有限域上是可表示的。这一工作也促进了某些拟阵的研究，这些拟阵非常接近于图，称为框架拟阵。作为理解这些拟阵的第一步，我的博士学位。学生Daryl Funk和Goddyn以及我已经证明了这些拟阵的一个表示定理，我们相信这将有助于理解它们的结构，这是我们的最终目标。