Handbook of Combinatorics Volume 1

Description

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.

Front Cover 2
Handbook of Combinatorics 5
Copyright Page 6
Preface 7
Table of Contents 9
List of Contributors 13
Part I: Structures 15
- Session 1: Graphs 17
  - CHAPTER 1. Basic Graph Theory: Paths and Circuits 17
    - 1. Basic concepts 19
    - 2. Hamilton paths and circuits in graphs 34
    - 3. Hamilton paths and circuits in digraphs 42

Front Cover 2
Handbook of Combinatorics 5
Copyright Page 6
Preface 7
Table of Contents 9
List of Contributors 13
Part I: Structures 15
- Session 1: Graphs 17
  - CHAPTER 1. Basic Graph Theory: Paths and Circuits 17
    - 1. Basic concepts 19
    - 2. Hamilton paths and circuits in graphs 34
    - 3. Hamilton paths and circuits in digraphs 42
    - 4. Fundamental parameters 47
    - 5. Fundamental classes of graphs and digraphs 68
    - 6. Special proof techniques for paths and circuits 83
    - 7. Lengths of circuits 88
    - 8. Packings and coverings by paths and circuits 94
    - References 108
  - CHAPTER 2. Connectivity and Network Flows 125
    - 1. Introduction, preliminaries 127
    - 2. Reachability 128
    - 3. Directed walks and paths of minimum cost 134
    - 4. Circulations and flows 138
    - 5. Minimum cost circulations and flows 146
    - 6. Trees and arborescences 153
    - 7. Higher connectivity 159
    - 8. Multicommodity flows and disjoint paths 173
    - References 184
  - CHAPTER 3. Matchings and Extensions 193
    - 1. Introduction and preliminaries 195
    - 2. Bipartite matching 198
    - 3. Nonbipartite matching 202
    - 4. Structure theory 209
    - 5. Weighted matchings and polyhedra 215
    - 6. Variations and extensions 225
    - 7. Determinants, permanents and Pfaffians 235
    - 8. Stable sets and claw free graphs 239
    - Acknowledgement 241
    - References 241
  - CHAPTER 4. Colouring, Stable Sets and Perfect Graphs 247
    - List of books and surveys 249
    - 1. Basic definitions and motivation 250
    - 2. Constructions and examples 253
    - 3. Algorithmic aspects 258
    - 4. Upper and lower bounds for the chromatic number 262
    - 5. Colour-critical graphs 267
    - 6. Graphs on surfaces 273
    - 7. Stable sets 276
    - 8. Perfect graphs 279
    - 9. Edge-colourings 285
    - 10. Concluding remarks 289
    - References 292
    - Acknowledgement 292
  - APPENDIX TO CHAPTER 4. Nowhere-Zero Flows 303
    - 1. Introduction 305
    - 2. Group-valued flows 306
    - 3. Applications of Theorem 2.3 308
    - 4. Nowhere-zero 4-flows 309
    - 5. The 3-flow conjecture 310
    - 6. The 5-flow conjecture 311
    - References 312
  - CHAPTER 5. Embeddings and Minors 315
    - 1. Introduction 317
    - 2. Graphs in the plane 320
    - 3. Graphs on higher surfaces 331
    - 4. Graph minors 342
    - 5. Embeddings and well-quasi-orderings of graphs 348
    - References 358
  - CHAPTER 6. Random Graphs 365
    - 1. Introduction 367
    - 2. Evolving graphs 368
    - 3. Evolution - Main epochs 370
    - 4. Phase transition 372
    - 5. Thresholds, threshold spectra and 0-1 laws 375
    - 6. Distributions 379
    - 7. Extreme characteristics 384
    - 8. Coloring 386
    - Appendix A. Quasi-random graphs 390
    - References 391
  - Session 2: Finite Sets and Relations 395
    - Session 3: Matroids 9
      - Session 4: Symmetric Structures 10
        
        Session 5: Combinatorial Structures in Geometry and Number Theory 10
        
        CHAPTER 17. Extremal Problems in Combinatorial Geometry 823
        
        1. Introduction 825
        
        2. Sylvester-Gallai theorems 826
        
        3. Arrangements 830
        
        4. Other geometries 841
        
        5. Metric problems 848
        
        6. Helly-type theorems 862
        
        7. Some other problems 874
        
        References 879
        
        CHAPTER 18. Convex Polytopes and Related Complexes 889
        
        1. Introduction and basic definitions 891
        
        2. Additional terminology 893
        
        3. Presentations of polytopes 895
        
        4. Polytopal readability of complexes 896
        
        5. Enumeration of combinatorial classes 904
        
        6. Face-vectors 909
        
        7. Polytopal graphs 919
        
        References 924
        
        CHAPTER 19. Point Lattices 933
        
        1. Introduction 935
        
        2. Lattices, convex bodies and reduction theory 937
        
        3. Geometry of numbers 943
        
        4. Packings and coverings 948
        
        5. N-dimensional crystallography and tilings 955
        
        6. Lattice polytopes 959
        
        7. Algorithmic geometry of numbers and integer programming 966
        
        8. Connections to other areas of mathematics 972
        
        References 972
        
        CHAPTER 20. Combinatorial Number Theory 981
        
        1. Introduction 983
        
        2. Combinatorial sieve methods 984
        
        3. Bases and density theorems on addition of sets 996
        
        4. Other additive problems 1002
        
        5. Multiplicative problems 1006
        
        6. Van der Waerden's theorem and generalizations 1013
        
        7. Miscellaneous problems 1020
        
        References 1029
        
        Acknowledgements 1029
        
        Author index 1033
        
        Subject index 1079
        
        CHAPTER 12. Permutation Groups 625
        
        1. Introduction 627
        
        2. Transitivity and primitivity 628
        
        3. The O'Nan-Scott theorem 631
        
        4. Finite simple groups 633
        
        5. Applications of the classification 637
        
        6. Characters and configurations 643
        
        7. The characters of the symmetric group 647
        
        8. Computing in permutation groups 650
        
        9. Infinite permutation groups 653
        
        References 655
        
        CHAPTER 13. Finite Geometries 661
        
        2. Projective and affine spaces 663
        
        1. Introduction 663
        
        3. Collineation groups 669
        
        4. Galois geometry 671
        
        5. The coding connection 680
        
        6. Projective and affine planes 681
        
        7. Generalized polygons 688
        
        8. Buildings 690
        
        9. Buekenhout geometries 693
        
        10. Partial geometries 698
        
        References 699
        
        CHAPTER 14. Block Designs 707
        
        Introduction 709
        
        1. Generalities 709
        
        2. De Bruijn-Erdős and Fisher inequalities and variations 710
        
        3. Square 2-designs 711
        
        5. Derived and residual designs, extensions 714
        
        4. Inequalities in 2-designs 714
        
        6. Existence and construction of t-designs with large t 716
        
        7. Mutually orthogonal Latin squares 719
        
        8. Group-divisible designs and transversal designs 719
        
        9. PBD-closed sets 721
        
        10. Steiner triple systems 722
        
        11. 3-Designs 724
        
        12. Resolvability 725
        
        13. Completing designs 726
        
        14. Packing and covering 727
        
        15. Codes and designs 729
        
        16. Witt designs, Golay codes and Mathieu groups 730
        
        Appendix. The known SBIBDs 743
        
        References 745
        
        CHAPTER 15. Association Schemes 761
        
        1. Introduction 763
        
        2. Strongly regular graphs 764
        
        3. Association schemes 768
        
        4. Applications 774
        
        References 782
        
        CHAPTER 16. Codes 787
        
        1. Introduction 789
        
        2. Linear codes 790
        
        3. Bounds on codes 794
        
        4. Cyclic codes 798
        
        5. Important classes of linear codes 802
        
        6. Some nonlinear codes 809
        
        7. Codes and designs 812
        
        8. Perfect codes and uniformly packed codes 816
        
        9. Codes, finite geometries and block designs 818
        
        References 819
      - CHAPTER 9. Matroids: Fundamental Concepts 495
        
        1. Introduction/History 497
        
        2. Axiom systems 497
        
        3. Some examples 500
        
        4. The polygon/cycle matroid of a graph, circuits, connectedness 502
        
        5. Duality 506
        
        6. Submatroids and minors 508
        
        7. Geometric lattices 510
        
        8. Pavings, transversals and linkages 512
        
        9. Submodular set functions 515
        
        10. Linear representability 517
        
        11. Algebraic matroids 521
        
        12. Structural properties 523
        
        13. Colourings, flows and the critical problem 525
        
        14. Varieties and universal models 530
        
        15. Oriented matroids 531
        
        16. Extensions of matroids 534
        
        17. Conclusion 536
        
        References 537
      - CHAPTER 10. Matroid Minors 541
        
        1. Introduction 543
        
        2. Connectivity 546
        
        3. Connectivity to ensure the spread of information 548
        
        4. Connectivity to eliminate hybrid structure 551
        
        5. Decomposition 555
        
        6. Applications of the regular matroid decomposition 558
        
        References 563
      - CHAPTER 11. Matroid Optimization and Algorithms 565
        
        1. Introduction 567
        
        2. Matroid optimization 568
        
        3. Matroid intersection 572
        
        4. Submodular functions and polymatroids 580
        
        5. Submodular flows and other general models 586
        
        6. Matroid connectivity algorithms 597
        
        7. Recognition of representability 605
        
        8. Matroid flows and linear programming 613
        
        Acknowledgement 619
        
        References 619
    - CHAPTER 7. Hypergraphs 395
      - 1. Hypergraphs and set systems 397
      - 2. Hypergraphs versus graphs 403
      - 3. Remarkable hypergraphs and min-max properties 408
      - 4. Stability, transversals and matchings 418
      - 5. Coloring problems 431
      - References 442
    - CHAPTER 8. Partially Ordered Sets 447
      - Introduction 449
      - 1. Notation and terminology 449
      - 2. Dilworth's theorem and the Greene-Kleitman theorem 451
      - 3. Kierstead's chain partitioning theorem 455
      - 4. Sperner's lemma and the cross cut conjecture 458
      - 5. Linear extensions and correlation 460
      - 6. Balancing pairs and the 1/3-2/3 conjecture 462
      - 7. Dimension and posets of bounded degree 469
      - 8. Interval orders and semiorders 473
      - 9. Degrees of freedom 479
      - 10. Dimension and planarity 482
      - 11. Regressions and monotone chains 488
      - References 490

Description

TOC

Reviews (0)