Tournament Immersion and Rao's Conjecture

锦标赛沉浸与拉奥猜想

• 批准号: 0901075
• 负责人: Paul Seymour
• 金额: $ 22万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0901075&HistoricalAwards=false
• 关键词: Tournament; Immersion; Rao; Conjecture

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.

主要研究者：Seymour，Paul D。提案编号：DMS - 0901075机构：普林斯顿大学标题：锦标赛沉浸和饶氏猜想该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。B。娆拉奥猜想本身涉及图的度序列，并且仍然是开放的，尽管在与Maria Chudnovsky的联合工作中，PI已经取得了实质性的进展，并且相信他们接近一个完整的证明。拉奥猜想是一个关于良准序的陈述;给定无穷多个度序列，其中一个在某种意义上必须“包含”另一个。与罗伯逊的工作产生了一些分支，在复杂性理论和纯图论，同样拉奥的猜想提出了一些侧面的问题。PI，在联合工作与尼尔罗伯逊，已经解决了两个主要问题，以及准序：瓦格纳猜想，即给定无穷多个图，其中一个必须是另一个的子图，以及纳什-威廉姆斯猜想，给定无穷多个图，其中一个必须包含在另一个图中作为“浸入”。“看来，他们为这两个猜想开发的方法，也可以应用到拉奥猜想上。此外，他们还遇到了几个新的和有趣的问题，关于图，作为副产品，他们的工作对饶的猜想，并计划对其中一些工作。这些侧面问题将是研究生论文的优秀问题，PI希望与学生一起回答这些问题。