Stable and crossing structures (Q2711192)

This book constitutes the author's PhD thesis, delivered to the Technical University of Eindhoven in 2000. There are 3 chapters. The first chapter provides an overview of the 5 main objects of interest: lattices, graphs, matroids, submodular functions, and polyhedral combinatorics.NEWLINENEWLINENEWLINEChapter II, which studies crossing structures, contains several new results. First, it generalizes the uncrossing algorithm of \textit{C. A. J. Hurkens}, \textit{L. Lovas}, \textit{A. Schrijver} and \textit{E. Tardos} [Colloq. Math. Soc. Janos Bolyai 52, 309-314 (1988; Zbl 0744.05007)] from a special lattice to a wide class of distributive lattices. Second, it proves a conjecture of Frank (1982), namely a min cut-max cover theorem for symmetric posets. Finally, it gives a new (and much shorter) proof of Pevzner's theorem (1994) on non-3-crossing families of sets. Each of these results is all slated to appear in article form in Combinatorica.NEWLINENEWLINENEWLINEChapter III is of most interest to game theorists. This chapter connects lattice-theoretic fixed-point theorems (included a new proof of Tarski's fixed-point theorem) to the notion of graph kernels. This linkage to some very interesting insights. Among these are a new proof of the Gale-Shapley matching theorem (Theorem 12.3), a new characterization of the von Neumann-Morgenstern stable set for cooperative \(n\)-person games (Claim 16.1), a counterexample to a claim by Roth (1985) (Example 16.3), and a new proof of Scarf's Lemma (Lemma 18.6). The latter result, which constitutes the main step in computing the core of an \(p\)-person game, is joint with R. Aharoni. Taken together, these results, all of which exploit the lattice structure of stable matchings, constitute a tour de force of graph theory applied to cooperative games.