Tournament Immersion and Rao's Conjecture

建议编号：DMS-0901075机构：普林斯顿大学标题：锦标赛沉浸和拉奥的猜想该奖项是根据2009年美国复苏和再投资法案(公共法律第111-5条)资助的。建议解决了因S.B.拉奥的猜想而产生的各种新问题。拉奥的猜想本身涉及图的度序列，并且仍然是开放的，尽管PI在与Maria Chudnovsky的联合工作中已经取得了实质性的进展，并相信它们接近于完全的证明。拉奥的猜想是关于良准有序的陈述；给定无限多个度序列，它们中的一个在某种意义上一定“包含”另一个。罗伯逊的工作产生了许多分支，在复杂性理论和纯图论中，类似地，拉奥的猜想提出了一些次要问题。PI与尼尔·罗伯逊共同工作，已经解决了关于良好准排序的两个主要问题：瓦格纳猜想，给定无限多的图，一个肯定是另一个的次要的，以及纳什-威廉姆斯的猜想，给定无穷多的图，一个必然包含在另一个图中，作为“浸入”。看来，他们为这两个猜想开发的方法也适用于拉奥的猜想。此外，他们还发现了几个关于图的新的有趣的问题，这是他们对拉奥猜想工作的副产品，并计划研究其中的一些问题。这些枝节问题将是研究生论文的极好问题，PI希望与学生合作回答这些问题。

ABSTRACTPrincipal Investigator: Seymour, Paul D. Proposal Number: DMS - 0901075 Institution: Princeton UniversityTitle: Tournament Immersion and Rao's ConjectureThis award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).The proposal addresses a variety of new problems that arise from a conjecture of S. B. Rao. Rao's conjecture itself concerns degree sequences of graphs, and remains open, although in joint work with Maria Chudnovsky, the PI has made substantial progress, and believes they are near a complete proof. Rao's conjecture is a statement about well-quasi-ordering; that given infinitely many degree sequences, one of them must "contain" another in a sense. The work with Robertson gave rise to a number of offshoots, in complexity theory and in pure graph theory, and similarly Rao's conjecture suggests a number of side questions.The PI, in joint work with Neil Robertson, already settled two major questions about well-quasi-ordering: Wagner's conjecture, that given infinitely many graphs, one must be a minor of another, and Nash-Williams' conjecture, that given infinitely many graphs, one must be contained in another as an "immersion." It seems that the methods they developed for these two conjectures can also be applied to Rao's conjecture. In addition, they have come across several new and interesting questions about graphs, as by-products of their work on Rao's conjecture, and plan to work on a number of these. These side questions would be excellent problems for graduate student theses, and the PI expects to work with students to answer them.