Handbook of Combinatorics

Name: Handbook of Combinatorics
Brand: Elsevier
Price: 360.0 EUR
Availability: OnlineOnly

R. L. Graham(Author)

Elsevier (Publisher)

Published on 11. December 1995

1018 pages

E-Book

PDF with digital watermarking

System requirements

978-0-08-093384-9 (ISBN)

€360.00incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

e9780444823465.pdf
Front Cover
Handbook of Combinatorics
Copyright Page
Table of Contents
Preface
List of Contributors
Part I: Structures
Session 1: Graphs
CHAPTER 1. Basic Graph Theory: Paths and Circuits
1. Basic concepts
2. Hamilton paths and circuits in graphs
3. Hamilton paths and circuits in digraphs
4. Fundamental parameters
5. Fundamental classes of graphs and digraphs
6. Special proof techniques for paths and circuits
7. Lengths of circuits
8. Packings and coverings by paths and circuits
References
CHAPTER 2. Connectivity and Network Flows
1. Introduction, preliminaries
2. Reachability
3. Directed walks and paths of minimum cost
4. Circulations and flows
5. Minimum cost circulations and flows
6. Trees and arborescences
7. Higher connectivity
8. Multicommodity flows and disjoint paths
References
CHAPTER 3. Matchings and Extensions
1. Introduction and preliminaries
2. Bipartite matching
3. Nonbipartite matching
4. Structure theory
5. Weighted matchings and polyhedra
6. Variations and extensions
7. Determinants, permanents and Pfaffians
8. Stable sets and claw free graphs
Acknowledgement
References
CHAPTER 4. Colouring, Stable Sets and Perfect Graphs
List of books and surveys
1. Basic definitions and motivation
2. Constructions and examples
3. Algorithmic aspects
4. Upper and lower bounds for the chromatic number
5. Colour-critical graphs
6. Graphs on surfaces
7. Stable sets
8. Perfect graphs
9. Edge-colourings
10. Concluding remarks
Acknowledgement
References
APPENDIX TO CHAPTER 4. Nowhere-Zero Flows
1. Introduction
2. Group-valued flows
3. Applications of Theorem 2.3
4. Nowhere-zero 4-flows
5. The 3-flow conjecture
6. The 5-flow conjecture
References
CHAPTER 5. Embeddings and Minors
1. Introduction
2. Graphs in the plane
3. Graphs on higher surfaces
4. Graph minors
5. Embeddings and well-quasi-orderings of graphs
References
CHAPTER 6. Random Graphs
1. Introduction
2. Evolving graphs
3. Evolution - Main epochs
4. Phase transition
5. Thresholds, threshold spectra and 0-1 laws
6. Distributions
7. Extreme characteristics
8. Coloring
Appendix A. Quasi-random graphs
References
Session 2: Finite Sets and Relations
CHAPTER 7. Hypergraphs
1. Hypergraphs and set systems
2. Hypergraphs versus graphs
3. Remarkable hypergraphs and min-max properties
4. Stability, transversals and matchings
5. Coloring problems
References
CHAPTER 8. Partially Ordered Sets
Introduction
1. Notation and terminology
2. Dilworth's theorem and the Greene-Kleitman theorem
3. Kierstead's chain partitioning theorem
4. Sperner's lemma and the cross cut conjecture
5. Linear extensions and correlation
6. Balancing pairs and the 1/3-2/3 conjecture
7. Dimension and posets of bounded degree
8. Interval orders and semiorders
9. Degrees of freedom
10. Dimension and planarity
11. Regressions and monotone chains
References
Session 3: Matroids
CHAPTER 9. Matroids: Fundamental Concepts
1. Introduction/History
2. Axiom systems
3. Some examples
4. The polygon/cycle matroid of a graph, circuits, connectedness
5. Duality
6. Submatroids and minors
7. Geometric lattices
8. Pavings, transversals and linkages
9. Submodular set functions
10. Linear representability
11. Algebraic matroids
12. Structural properties
13. Colourings, flows and the critical problem
14. Varieties and universal models
15. Oriented matroids
16. Extensions of matroids
17. Conclusion
References
CHAPTER 10. Matroid Minors
1. Introduction
2. Connectivity
3. Connectivity to ensure the spread of information
4. Connectivity to eliminate hybrid structure
5. Decomposition
6. Applications of the regular matroid decomposition
References
CHAPTER 11. Matroid Optimization and Algorithms
1. Introduction
2. Matroid optimization
3. Matroid intersection
4. Submodular functions and polymatroids
5. Submodular flows and other general models
6. Matroid connectivity algorithms
7. Recognition of representability
8. Matroid flows and linear programming
Acknowledgement
References
Session 4: Symmetric Structures
CHAPTER 12. Permutation Groups
1. Introduction
2. Transitivity and primitivity
3. The O'Nan-Scott theorem
4. Finite simple groups
5. Applications of the classification
6. Characters and configurations
7. The characters of the symmetric group
8. Computing in permutation groups
9. Infinite permutation groups
References
CHAPTER 13. Finite Geometries
1. Introduction
2. Projective and affine spaces
3. Collineation groups
4. Galois geometry
5. The coding connection
6. Projective and affine planes
7. Generalized polygons
8. Buildings
9. Buekenhout geometries
10. Partial geometries
References
CHAPTER 14. Block Designs
Introduction
1. Generalities
2. De Bruijn-Erdos and Fisher inequalities and variations
3. Square 2-designs
4. Inequalities in 2-designs
5. Derived and residual designs, extensions
6. Existence and construction of t-designs with large t
7. Mutually orthogonal Latin squares
8. Group-divisible designs and transversal designs
9. PBD-closed sets
10. Steiner triple systems
11. 3-Designs
12. Resolvability
13. Completing designs
14. Packing and covering
15. Codes and designs
16. Witt designs, Golay codes and Mathieu groups
Appendix. The known SBIBDs
References
CHAPTER 15. Association Schemes
1. Introduction
2. Strongly regular graphs
3. Association schemes
4. Applications
References
CHAPTER 16. Codes
1. Introduction
2. Linear codes
3. Bounds on codes
4. Cyclic codes
5. Important classes of linear codes
6. Some nonlinear codes
7. Codes and designs
8. Perfect codes and uniformly packed codes
9. Codes, finite geometries and block designs
References
Session 5: Combinatorial Structures in Geometry and Number Theory
CHAPTER 17. Extremal Problems in Combinatorial Geometry
1. Introduction
2. Sylvester-Gallai theorems
3. Arrangements
4. Other geometries
5. Metric problems
6. Helly-type theorems
7. Some other problems
References
CHAPTER 18. Convex Polytopes and Related Complexes
1. Introduction and basic definitions
2. Additional terminology
3. Presentations of polytopes
4. Polytopal readability of complexes
5. Enumeration of combinatorial classes
6. Face-vectors
7. Polytopal graphs
References
CHAPTER 19. Point Lattices
1. Introduction
2. Lattices, convex bodies and reduction theory
3. Geometry of numbers
4. Packings and coverings
5. N-dimensional crystallography and tilings
6. Lattice polytopes
7. Algorithmic geometry of numbers and integer programming
8. Connections to other areas of mathematics
References
CHAPTER 20. Combinatorial Number Theory
1. Introduction
2. Combinatorial sieve methods
3. Bases and density theorems on addition of sets
4. Other additive problems
5. Multiplicative problems
6. Van der Waerden's theorem and generalizations
7. Miscellaneous problems
Acknowledgements
References
Author index
Subject index
e9780444880024
Front Cover
Handbook of Combinatorics
Copyright Page
Contents
Preface
List of Contributors
Part II: Aspects
Chapter 21. Algebraic Enumeration
Chapter 22. Asymptotic Enumeration Methods
Chapter 23. Extremal Graph Theory
Chapter 24. Extremal Set Systems
Chapter 25. Ramsey Theory
Chapter 26. Discrepancy Theory
Chapter 27. Automorphism Groups, Isomorphism, Reconstruction
Chapter 28. Combinatorial Optimization
Chapter 29. Computational Complexity
Part III: Methods
Chapter 30. Polyhedral Combinatorics
Chapter 31. Tools from Linear Algebra
Appendix
Chapter 32. Tools from Higher Algebra
Chapter 33. Probabilistic Methods
Chapter 34. Topological Methods
Part IV: Applications
Chapter 35. Combinatorics in Operations Research
Chapter 36. Combinatorics in Electrical Engineering and Statics
Chapter 37. Combinatorics in Statistical Physics
Chapter 38. Combinatorics in Chemistry
Chapter 39. Applications of Combinatorics to Molecular Biology
Chapter 40. Combinatorics in Computer Science
Chapter 41. Combinatorics in Pure Mathematics
Part V: Horizons
Chapter 42. Infinite Combinatorics
Chapter 43. Combinatorial Games
Chapter 44. The History of Combinatorics
Author Index
Subject Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Handbook of Combinatorics

Description

More details

Other editions

Additional editions

Content

System requirements