Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications

ISBN-13: 9789401088480 / Angielski / Miękka / 2011 / 816 str.

Ivan Rival

Opis

This volume contains the accounts of the principal survey papers presented at GRAPHS and ORDER, held at Banff, Canada from May 18 to May 31, 1984. This conference was supported by grants from the N.A.T.O. Advanced Study Institute programme, the Natural Sciences and Engineering Research Council of Canada and the University of Calgary. We are grateful for all of this considerable support. Almost fifty years ago the first Symposium on Lattice Theory was held in Charlottesville, U.S.A. On that occasion the principal lectures were delivered by G. Birkhoff, O. Ore and M.H. Stone. In those days the theory of ordered sets was thought to be a vigorous relative of group theory. Some twenty-five years ago the Symposium on Partially Ordered Sets and Lattice Theory was held in Monterey, U.S.A. Among the principal speakers at that meeting were R.P. Dilworth, B. Jonsson, A. Tarski and G. Birkhoff. Lattice theory had turned inward: it was concerned primarily with problems about lattices themselves. As a matter of fact the problems that were then posed have, by now, in many instances, been completely solved.

Recenzje

` The volume provides an excellent introduction to many aspects of graphs and order. On the whole, the papers are well written and they provide a huge amount of information. Certainly I am glad to have Graphs and Order now as part of my library and suggest that it would provide an excellent source and reference that ought to find its way into at least every departmental library. '
The Journal of Symbolic Logic

Spis treści

I. Graph Representations.- Comparability graphs.- Algorithmic aspects of comparability graphs and interval graphs.- The diagram.- II. Scheduling, Searching and Sorting.- The information theoretic bound for problems on ordered sets and graphs.- Sorting and graphs.- A graph-theoretic approach to the jump-number problem.- Acyclic subdigraphs and linear orderings: polytopes, facets, and a cutting plane algorithm.- III. Extremal Orders.- Parameters of partial orders and graphs: packing, covering and representation.- Graphs and orders in Ramsey theory and in dimension theory.- Ordered ranked posets, representations of integers and inequalities from extremal poset problems.- IV. Social Sciences.- Issues in the theory of uniqueness in measurement.- V. Decomposition.- Path-partitions in directed graphs and posets.- VI. Recursion.- Recursion theoretic aspects of graphs and orders.- VII. Well-Quasi-Ordering.- Basic wqo- and bqo-theory.- Applications of well quasi-ordering and better quasi-ordering.- VIII. Problem Sessions.- Enumeration.- The diagram.- Ramsey theory.- Sorting, scheduling, computing, operations research, and social science.- Structure theories.- Infinite sets and infinite graphs.- Souvenir session.- Order-preserving and edge-preserving maps.- Miscellaneous.- IX. A Bibliography.- X. Index.