Structural Combinatorics

我从事的是一个广泛的组合学研究项目，其主题是寻求对异常现象的结构性理解。根据我打算在未来5年研究的主要主题，本摘要分为两部分。**组合数论*本课题的一个基本问题是刻划乘法群的有限子集A、B，其中乘积集AB的大小很小。对这个项目的第一个深刻贡献(G=Z)归功于Freiman，随后由Ruzsa改进。许多作者最近的工作揭示了这个问题对加法组合数学界和更远的世界的意义。Breulliard，Green和Tao的一项新突破给出了一个适用于任意群的强大的粗结构定理。然而，要获得更准确的理解，还有很多工作要做。我在这方面的工作涉及到当|AB|非常小时的极端情况(在这个领域中，主题是高度组合的)。在|AB|&lt；|A|+|B|的情况下，我最近完成了一个描述集合的精确结构定理。和我的博士生Tom Boothby一起，我们已经开始刻画那些|AB|=|A|+|B|的集合，并希望继续研究|AB|&lt；|A|+|B|+c为固定常数c的集合的结构。这种情况下的粗略结构定理在(数学)应用中将是非常有用的。**图论和加法数论之间有许多交叉，我对这种联系特别感兴趣。我和Mohar一起证明了一个关于点传递图的小分离度的粗结构定理，它在图论和组合数论中都有应用。在这方面有很多方向可以推进(例如。对有向图的推广)，我相信它会成为适合学生的项目。另一个交叉问题是给出正则图的幂的平均度的界。与麦克唐纳和谢德一起，我最近证明了这一点对2次方(Mod 3)的严格限制。将这些结果从图推广到有向图，对于极值图论和加性组合学都是非常有价值的。**图沉浸*沉浸是图中的一种自然包容操作，与图的次要项相比，它受到的关注相对较少。Robertson和Seymour著名地证明了图在浸没下是良好的拟有序的，但对这种关系的结构性质了解很少。最近，我与不同的同事小组合作研究沉浸。我们最值得注意的结果包括证明每个最小度200t的简单图都浸没完全图K_t的一个定理和一个不浸没给定图的图的粗略结构定理。这里有许多未来研究的重要方向。事实上，我目前正在与两名硕士研究生一起解决这些问题。我们与Mahdieh Malekian(和McDonald)一起致力于不浸入K_5或K_{3，3}的图的精确刻画，与Stefan Hannie(以及Mohar和Archdeacon)一起研究2-正则有向图的浸入。**拟阵子群*Geelen，Gerards和Whitte的拟阵子群计划建立了一个强大的可在固定有限域上表示的拟阵理论。这项工作也促进了对某些与称为框架拟阵的图非常接近的拟阵的研究。作为理解这些拟阵的第一步，我的博士生Daryl Funk和Goddyn和我证明了这些拟阵的一个表示定理，我们相信这个定理将有助于理解它们的结构，也是我们的最终目标。

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.