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.