This 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.
