Handbook of Combinatorics Volume 1, Volume 1Ronald L. Graham, Martin Grötschel, László Lovász Handbook of Combinatorics, Volume 1 focuses on basic methods, paradigms, results, issues, and trends across the broad spectrum of combinatorics. The selection first elaborates on the basic graph theory, connectivity and network flows, and matchings and extensions. Discussions focus on stable sets and claw free graphs, nonbipartite matching, multicommodity flows and disjoint paths, minimum cost circulations and flows, special proof techniques for paths and circuits, and Hamilton paths and circuits in digraphs. The manuscript then examines coloring, stable sets, and perfect graphs and embeddings and minors. The book takes a look at random graphs, hypergraphs, partially ordered sets, and matroids. Topics include geometric lattices, structural properties, linear extensions and correlation, dimension and posets of bounded degree, hypergraphs and set systems, stability, transversals, and matchings, and phase transition. The manuscript also reviews the combinatorial number theory, point lattices, convex polytopes and related complexes, and extremal problems in combinatorial geometry. The selection is a valuable reference for researchers interested in combinatorics. |
Contents
Adam Mickiewicz University Poznań and Emory University | 6 |
University of Washington Seattle WA Ch | 18 |
Hamilton paths and circuits in graphs | 20 |
Hamilton paths and circuits in digraphs | 28 |
Lenstra J K Eindhoven University of Technology Eindhoven and Centre | 35 |
Lloyd E K University of Southampton Southampton Ch | 44 |
Fundamental classes of graphs and digraphs | 54 |
Automorphism Groups Isomorphism Reconstruction 1447 | 64 |
Random Graphs | 351 |
Finite Sets and Relations | 381 |
Probabilistic Methods 1785 | 385 |
Partially Ordered Sets | 433 |
Matroids | 481 |
Matroid Minors | 527 |
Matroid Optimization and Algorithms | 551 |
Symmetric Structures | 611 |
Special proof techniques for paths and circuits | 69 |
Packings and coverings by paths and circuits | 80 |
References | 94 |
Combinatorial Optimization 1541 | 98 |
Connectivity and Network Flows | 111 |
References | 170 |
Computational Complexity 1599 | 173 |
Matchings and Extensions | 179 |
Tools from Linear Algebra 1705 | 222 |
Combinatorial Games 2117 | 229 |
Colouring Stable Sets and Perfect Graphs | 233 |
NowhereZero Flows | 289 |
Embeddings and Minors | 301 |
The History of Combinatorics 2163 | 308 |
Tools from Higher Algebra 1749 | 312 |
Finite Geometries | 647 |
Block Designs | 693 |
Association Schemes | 747 |
Codes | 773 |
Combinatorial Structures in Geometry and Number Theory | 809 |
Convex Polytopes and Related Complexes | 875 |
Topological Methods 1819 | 896 |
Point Lattices | 919 |
Combinatorics in Computer Science 2003 | 961 |
Combinatorial Number Theory | 967 |
Combinatorics in Pure Mathematics 2039 | 1018 |
| xiii | |
| lix | |
| xcii | |
Common terms and phrases
3-connected algorithm applications bipartite blocks bound called chapter circuit colour Combin combinatorial complete components Comput condition conjecture connected consider construction contains convex corresponding covering cycle defined denote determined digraph dimension directed Discrete Math disjoint distance dual edges elements equal equivalent Erdős example exists extended finite flow function geometry given gives graph G groups Hamilton Hence holds hypergraph implies incident independent induced inequality integer intersection known lattice least Lemma length Let G linear matching Math matrix matroid maximal maximum minor nodes Note obtained pairs partition path perfect permutation planar plane points polynomial polytopes poset positive possible problem projective proof proved regular respectively result satisfies simple space structure subgraph subset Suppose Theorem Theory tree vector vertex vertices weight