| We study the structure theory of two combinatorial objects closely related to graphs.;First, we consider degree sequences, and we prove several results originally motivated by attempts to prove what was, until recently, S.B. Rao's conjecture, and what is now a theorem of Paul Seymour and Maria Chudnovsky, namely, that graphic degree sequences are well quasi ordered. We give a new, surprisingly non-graph theoretic proof of the bounded case of this theorem. Next, we obtain an exact structure theorem of degree sequences excluding a square and a pentagon. Using this result, we then prove a structure theorem for degree sequences excluding a square and, more generally, excluding an arbitrary cycle. It should be noted that taking complements, this yields a structure theorem for excluding a matching.;The structure theorems above, however, are stated in terms of forcibly chordal graphs, hence we next begin their characterization. While an exact characterization seems difficult, certain partial results are obtained. Specifically, we first characterize the degree sequences of forcibly chordal trees. Next, we use this result to extend the characterization to forcibly chordal forests. Finally, we characterize forcibly chordal graphs having a certain path structure.;Next, we define a class of combinatorial objects that generalizes digraphs and partial orders, which is motivated by proof systems arising in mathematical logic. We give what we believe will be the basic theory of these objects, including definitions, theorems, and proofs. We define the minors of a proof system, and we give two forbidden minors theorems, one of them characterizing partial orders as proof systems by forbidden minors. |
