Издательство Birkh?user, 2009, -501 pp.
This volume surveys the development of combinatorics since 1930 by presenting in chronological order the fundamental results of the subject proved in the orginal papers.
We begin with the celebrated theorem of Ramsey [1930], originally developed to settle a special case of the decision problem for the predicate calculus with equality. It remains to this day the fundamental generalization of the classical pigeonhole principle. The paper by Erdos and Szekeres [1935a] was one of the first applications of Ramsey's theorem, and it is still one of the most elegant. Through the partition calculus of Erdos and Rado [1956a], Ramsey's theorem made inroads into set theory, where nowadays it holds the limelight. The next major advance along the lines initiated by Ramsey came with the work of Hales and Jewett [1963a], a result which has served as a foundation for much further work in the area. The categorical underpinning of Ramsey theory was worked out by Graham, Leeb, and Rothschild [1972a]. Here the original ideas of Ramsey are cleverly blended with the contribution of Hales and Jewett.
Whitney's paper [1932] marks the beginning of what is now the theory of matroids. Three years later the theory makes its appearance fully clad in another paper of Whitney [1935c] which remains the basic reference on the subject. The theory of matroids was also in the backround of Tutte's paper [1947]. Tutte's paper is couched in the language of graphs and was later generalized to arbitrary matroids by Brylawski. The motivation behind much of the work of the two outstanding graph theorists of the day, Whitney and Tutte, was the coloring problem for graphs. Two short and elegant results on coloring problems are Brooks's theorem [1941) relating the chromatic number of a graph to its maximal degree and Lovasz's theorem [1972b] characterizing perfect graphs.
Philip Hall's paper [1935b] was the first in what is now called matching theory. A very short proof of Hall's marriage theorem was given by Halmos and Vaughan [1950b]. In the same year Dilworth [l950a] proved his famous decomposition theorem for partially ordered sets, which generalizes Hall's theorem. Several other minimax combinatorial theorems can be viewed as variants or generalizations of the marriage theorem. Such are Tutte's definitive work on factors in graphs [1952], Ford and Fulkerson's theory of flows in networks [1956b], and Edmonds's [1965] efficient algorithm for matching in graphs. Gale [1957a] used network flow theory to prove a result on matrices of O's and I 's with given row and column sums also proved directly by Ryser [1957b].
De Bruijn and van Aardenne-Ehrenfest [1951], taking their lead from the early work of Kirchhoff, obtained a definitive result, now called the BEST theorem (de Bruijn-Ehrenfest-Stone-Tutte) conceing the enumeration of spanning trees and Eulerian circuits of a graph by determinants. Several years later, Kasteleyn [1961a] succeeded in solving a packing problem for dimers on a lattice by reducing the problem to the evaluation of Pfaffians.
P?lya's paper on picture-writing [ 1956c] foreshadows the notion of the incidence algebra, a term introduced years later by Rota [1964] in his theory of Mobius functions. Rota's work was substantially extended by Crapo [1968J. The mystery of the characteristic polynomial, defined in terms of the Mobius function of a partially ordered set, motivates Stanley's beautiful result [1973a] on acyclic orientations of graphs. Geissinger's three papers [1973b-d] are the definitive presentation of the theory of Mobius functions.
The subject that is now called extremal set theory is represented by Katona's paper [1966a]. The main result, independently proved by Kruskal, harks back to a theorem of Macaulay, and was generalized by Clements and Lindstrom [1969]. Lubell's blitz proof of Speer's theorem [l966b] has been extensively generalized and applied to many problems. Kleitman's solution [1970b] of a long-standing problem of Erdos related to the Littlewood-Offord problem shows the power of a simple, but far from obvious, induction argument.
Brooks, Smith, Stone, and Tutte's paper [1940] on the decomposition of rectangles into squares was the first to use Kirchhoff's laws for the solution of a problem in combinatorics, a technique that has since become standard.
Kaplansky's solution [1943] of the probleme des menages using the inclusion-exclusion principle has developed into what is now the theory of permutations with restricted position. Lovasz's contribution [1972c] to the Ulam reconstruction problem is another ingenious use of the inclusion-exclusion principle.
Erdos's paper on graph theory and probability [1959] is the first paper to show how probabilistic methods can lead to combinatorial existence theorems. A substantial number of theorems in combinatorics, for which no explicit construction is known, can be given existence proofs by this method.
Schensted's bijection [1961b] between permutations and pairs of standard Young diagrams has proved central in the seemingly unrelated topics of plane partitions and representations of the symmetric group.
Schiitzenberger's paper [1962] lays the foundation of what is now the theory of rational and algebraic power series in noncom mutative variables.
Nash-Williams's striking proof [1963b] that finite trees form a well-quasi-ordered set has blossomed both in logic and in graph theory.
I.J. Good's short proof [1970a] of a conjecture of Dyson has since been widely generalized but his approach is still the good one.
[1930] F.P. Ramsey, On a problem of formal logic
[1932] H. Whitney, Non-separable and planar graphs
[1935a] P. Erdos and G. Szekeres, A combinatorial problem in geometry
[1935b] P. Hall, On representatives of subsets
[1935c] H. Whitney, On the abstract properties of linear dependence
[1940] R.L. Brooks, C.A.B. Smith, A.H. Stone, and W.T. Tutte, The dissection of rectangles into squares
[1941] R.L. Brooks, On colouring the nodes of a network
[1943] I. Kaplansky, Solution of the "probleme des menages"
[1947] W.T. Tutte, A ring in graph theory
[1950a] R. P. Dilworth, A decomposition theorem for partially ordered sets
[1950b] P.R. Halmos and H.E. Vaughan, The marriage problem
[1951] T. van Aardenne-Ehrenfest and N.G. de Bruijn, Circuits and trees in oriented linear graphs
[1952] W. T. Tutte, The factors of graphs
[1956a] P. Erdos and R. Rado, A partition calculus in set theory
[1956b] L.R. Ford, Jr., and D.R. Fulkerson, Maximal flow through a network
[1956c] G. P?lya, On picture-writing
[1957a] D. Gale, A theorem on flows in networks
[1957b] H.J. Ryser, Combinatorial properties of matrices of zeros and ones
[1959] P. Erdos, Graph theory and probability
[1961 a] P.W. Kasteleyn, The statistics of dimers on a lattice: I. The number of
dimer arrangements on a quadratic lattice
[196Ib] C. Schensted, Longest increasing and decreasing subsequences
[1962] M.P. Schiitzenberger, On a theorem of R. Jungen
[1963a] A.W. Hales and R.I. Lewett, Regularity and positional games
[1963b] C.St.J.A. Nash-Williams, On well-quasi-ordering finite trees
[1964] G.-C. Rota, On the foundations of combinatorial theory I: Theory of Mobius functions
[1965] I. Edmonds, Paths, trees, and flowers
[1966a] G. Katona, A theorem of finite sets
[1966b] D. Lubell, A short proof of Speer's lemma
[1968] H.H. Crapo, Mobius inversion in lattices
[1969] G.F. Clements and B. Lindstrom, A generalization of a combinatorial theorem of Macaulay
[1970a] I.J. Good, Short proof of a conjecture by Dyson
[1970b] D.J. Kleitman, On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
[1972a] R.L. Graham, K. Leeb, and B.L. Rothschild, Ramsey's theorem for a class of categories
[1972b] L. Lovasz, A characterization of perfect graphs
[1972c] L. Lovasz, A note on the line reconstruction problem
[1973a] R.P. Stanley, Acyclic orientations of graphs
[1973b] L. Geissinger, Valuations on distributive lattices I
[1973c] L. Geissinger, Valuations on distributive lattices II
[1973d] L. Geissinger, Valuations on distributive lattices III
This volume surveys the development of combinatorics since 1930 by presenting in chronological order the fundamental results of the subject proved in the orginal papers.
We begin with the celebrated theorem of Ramsey [1930], originally developed to settle a special case of the decision problem for the predicate calculus with equality. It remains to this day the fundamental generalization of the classical pigeonhole principle. The paper by Erdos and Szekeres [1935a] was one of the first applications of Ramsey's theorem, and it is still one of the most elegant. Through the partition calculus of Erdos and Rado [1956a], Ramsey's theorem made inroads into set theory, where nowadays it holds the limelight. The next major advance along the lines initiated by Ramsey came with the work of Hales and Jewett [1963a], a result which has served as a foundation for much further work in the area. The categorical underpinning of Ramsey theory was worked out by Graham, Leeb, and Rothschild [1972a]. Here the original ideas of Ramsey are cleverly blended with the contribution of Hales and Jewett.
Whitney's paper [1932] marks the beginning of what is now the theory of matroids. Three years later the theory makes its appearance fully clad in another paper of Whitney [1935c] which remains the basic reference on the subject. The theory of matroids was also in the backround of Tutte's paper [1947]. Tutte's paper is couched in the language of graphs and was later generalized to arbitrary matroids by Brylawski. The motivation behind much of the work of the two outstanding graph theorists of the day, Whitney and Tutte, was the coloring problem for graphs. Two short and elegant results on coloring problems are Brooks's theorem [1941) relating the chromatic number of a graph to its maximal degree and Lovasz's theorem [1972b] characterizing perfect graphs.
Philip Hall's paper [1935b] was the first in what is now called matching theory. A very short proof of Hall's marriage theorem was given by Halmos and Vaughan [1950b]. In the same year Dilworth [l950a] proved his famous decomposition theorem for partially ordered sets, which generalizes Hall's theorem. Several other minimax combinatorial theorems can be viewed as variants or generalizations of the marriage theorem. Such are Tutte's definitive work on factors in graphs [1952], Ford and Fulkerson's theory of flows in networks [1956b], and Edmonds's [1965] efficient algorithm for matching in graphs. Gale [1957a] used network flow theory to prove a result on matrices of O's and I 's with given row and column sums also proved directly by Ryser [1957b].
De Bruijn and van Aardenne-Ehrenfest [1951], taking their lead from the early work of Kirchhoff, obtained a definitive result, now called the BEST theorem (de Bruijn-Ehrenfest-Stone-Tutte) conceing the enumeration of spanning trees and Eulerian circuits of a graph by determinants. Several years later, Kasteleyn [1961a] succeeded in solving a packing problem for dimers on a lattice by reducing the problem to the evaluation of Pfaffians.
P?lya's paper on picture-writing [ 1956c] foreshadows the notion of the incidence algebra, a term introduced years later by Rota [1964] in his theory of Mobius functions. Rota's work was substantially extended by Crapo [1968J. The mystery of the characteristic polynomial, defined in terms of the Mobius function of a partially ordered set, motivates Stanley's beautiful result [1973a] on acyclic orientations of graphs. Geissinger's three papers [1973b-d] are the definitive presentation of the theory of Mobius functions.
The subject that is now called extremal set theory is represented by Katona's paper [1966a]. The main result, independently proved by Kruskal, harks back to a theorem of Macaulay, and was generalized by Clements and Lindstrom [1969]. Lubell's blitz proof of Speer's theorem [l966b] has been extensively generalized and applied to many problems. Kleitman's solution [1970b] of a long-standing problem of Erdos related to the Littlewood-Offord problem shows the power of a simple, but far from obvious, induction argument.
Brooks, Smith, Stone, and Tutte's paper [1940] on the decomposition of rectangles into squares was the first to use Kirchhoff's laws for the solution of a problem in combinatorics, a technique that has since become standard.
Kaplansky's solution [1943] of the probleme des menages using the inclusion-exclusion principle has developed into what is now the theory of permutations with restricted position. Lovasz's contribution [1972c] to the Ulam reconstruction problem is another ingenious use of the inclusion-exclusion principle.
Erdos's paper on graph theory and probability [1959] is the first paper to show how probabilistic methods can lead to combinatorial existence theorems. A substantial number of theorems in combinatorics, for which no explicit construction is known, can be given existence proofs by this method.
Schensted's bijection [1961b] between permutations and pairs of standard Young diagrams has proved central in the seemingly unrelated topics of plane partitions and representations of the symmetric group.
Schiitzenberger's paper [1962] lays the foundation of what is now the theory of rational and algebraic power series in noncom mutative variables.
Nash-Williams's striking proof [1963b] that finite trees form a well-quasi-ordered set has blossomed both in logic and in graph theory.
I.J. Good's short proof [1970a] of a conjecture of Dyson has since been widely generalized but his approach is still the good one.
[1930] F.P. Ramsey, On a problem of formal logic
[1932] H. Whitney, Non-separable and planar graphs
[1935a] P. Erdos and G. Szekeres, A combinatorial problem in geometry
[1935b] P. Hall, On representatives of subsets
[1935c] H. Whitney, On the abstract properties of linear dependence
[1940] R.L. Brooks, C.A.B. Smith, A.H. Stone, and W.T. Tutte, The dissection of rectangles into squares
[1941] R.L. Brooks, On colouring the nodes of a network
[1943] I. Kaplansky, Solution of the "probleme des menages"
[1947] W.T. Tutte, A ring in graph theory
[1950a] R. P. Dilworth, A decomposition theorem for partially ordered sets
[1950b] P.R. Halmos and H.E. Vaughan, The marriage problem
[1951] T. van Aardenne-Ehrenfest and N.G. de Bruijn, Circuits and trees in oriented linear graphs
[1952] W. T. Tutte, The factors of graphs
[1956a] P. Erdos and R. Rado, A partition calculus in set theory
[1956b] L.R. Ford, Jr., and D.R. Fulkerson, Maximal flow through a network
[1956c] G. P?lya, On picture-writing
[1957a] D. Gale, A theorem on flows in networks
[1957b] H.J. Ryser, Combinatorial properties of matrices of zeros and ones
[1959] P. Erdos, Graph theory and probability
[1961 a] P.W. Kasteleyn, The statistics of dimers on a lattice: I. The number of
dimer arrangements on a quadratic lattice
[196Ib] C. Schensted, Longest increasing and decreasing subsequences
[1962] M.P. Schiitzenberger, On a theorem of R. Jungen
[1963a] A.W. Hales and R.I. Lewett, Regularity and positional games
[1963b] C.St.J.A. Nash-Williams, On well-quasi-ordering finite trees
[1964] G.-C. Rota, On the foundations of combinatorial theory I: Theory of Mobius functions
[1965] I. Edmonds, Paths, trees, and flowers
[1966a] G. Katona, A theorem of finite sets
[1966b] D. Lubell, A short proof of Speer's lemma
[1968] H.H. Crapo, Mobius inversion in lattices
[1969] G.F. Clements and B. Lindstrom, A generalization of a combinatorial theorem of Macaulay
[1970a] I.J. Good, Short proof of a conjecture by Dyson
[1970b] D.J. Kleitman, On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
[1972a] R.L. Graham, K. Leeb, and B.L. Rothschild, Ramsey's theorem for a class of categories
[1972b] L. Lovasz, A characterization of perfect graphs
[1972c] L. Lovasz, A note on the line reconstruction problem
[1973a] R.P. Stanley, Acyclic orientations of graphs
[1973b] L. Geissinger, Valuations on distributive lattices I
[1973c] L. Geissinger, Valuations on distributive lattices II
[1973d] L. Geissinger, Valuations on distributive lattices III