You are previewing Surveys in Combinatorics 2013.
O'Reilly logo
Surveys in Combinatorics 2013

Book Description

This volume contains nine survey articles based on the invited lectures given at the 24th British Combinatorial Conference, held at Royal Holloway, University of London in July 2013. This biennial conference is a well-established international event, with speakers from around the world. The volume provides an up-to-date overview of current research in several areas of combinatorics, including graph theory, matroid theory and automatic counting, as well as connections to coding theory and Bent functions. Each article is clearly written and assumes little prior knowledge on the part of the reader. The authors are some of the world's foremost researchers in their fields, and here they summarise existing results and give a unique preview of cutting-edge developments. The book provides a valuable survey of the present state of knowledge in combinatorics, and will be useful to researchers and advanced graduate students, primarily in mathematics but also in computer science and statistics.

Table of Contents

  1. Cover
  2. Series
  3. Title
  4. Copyright
  5. Table of Contents
  6. Preface
  7. Graph removal lemmas
    1. 1 Introduction
    2. 2 The graph removal lemma
    3. 3 The induced removal lemma
    4. 4 Arithmetic removal
    5. 5 Sparse removal
    6. 6 Further topics
    7. References
  8. The geometry of covering codes: small complete caps and saturating sets in Galois spaces
    1. 1 Introduction
    2. 2 Covering codes with radius 2
    3. 3 Irreducible algebraic curves and function fields
    4. 4 The plane case
    5. 5 The three-dimensional case
    6. 6 Constructions in higher dimensions
    7. 7 Multiple saturating sets in the plane
    8. References
  9. Bent functions and their connections to combinatorics
    1. 1 Introduction
    2. 2 Definitions and basic properties
    3. 3 Some known classes of bent functions
    4. 4 Connections to coding theory
    5. 5 Bent functions and other combinatorial objects
    6. 6 Crosscorrelation and bent sequences
    7. 7 Conclusions
    8. References
  10. The complexity of change
    1. 1 Introduction
    2. 2 Reconfiguration of satisfiability problems
    3. 3 Reconfiguration of graph colourings
    4. 4 Moving tokens on graphs
    5. 5 Applications
    6. 6 Open problem
    7. Acknowledgements
    8. References
  11. How symmetric can maps on surfaces be?
    1. 1 Introduction
    2. 2 Regular maps - algebra and geometry
    3. 3 Orientably regular maps - algebra and geometry
    4. 4 The classification of regular maps
    5. 5 Regular maps: Constructions, operations, and external symmetries
    6. 6 Conclusion
    7. References
  12. Some open problems on permutation patterns
    1. 1 Introduction
    2. 2 Kinds of patterns
    3. 3 Enumeration and asymptotics of avoiders: The case of 1324
    4. 4 Are layered patterns the most easily avoided?
    5. 5 The pattern poset, its Mobius function and topology
    6. 6 Other algebraic aspects
    7. 7 Growth rates of permutation classes
    8. 8 Acknowledgements
    9. References
  13. The world of hereditary graph classes viewed through Truemper configurations
    1. 1 Introduction
    2. 2 Truemper’s Theorem
      1. 2.1 Recognizing Truemper configurations
    3. 3 The decomposition method
      1. 3.1 Triangulated graphs
      2. 3.2 Common cutsets
    4. 4 Regular and balanced matrices
      1. 4.1 Decomposition of regular matroids
      2. 4.2 Decomposition of balanced matrices
    5. 5 Classes closed under minor taking
    6. 6 (3PC(·, ·), 3PC(Δ, ·), 3PC(Δ, Δ), wheel)-free graphs
    7. 7 (3PC(Δ, ·), 3PC(Δ, Δ), wheel)-free graphs
      1. 7.1 (ISK4, wheel)-free graphs
      2. 7.2 Unichord-free graphs
      3. 7.3 Propeller-free graphs
    8. 8 (3PC(Δ, ·), proper wheel)-free
      1. 8.1 Cap-free graphs
      2. 8.2 Claw-free graphs
      3. 8.3 Bull-free graphs
    9. 9 Excluding some wheels and some 3-path-configurations
      1. 9.1 Even-hole-free graphs
      2. 9.2 Perfect graphs and odd-hole-free graphs
    10. 10 Combinatorial optimization with 1-joins and 2-joins
      1. 10.1 1-Joins
      2. 10.2 2-Joins
    11. Acknowledgements
    12. References
  14. Structure in minor-closed classes of matroids
    1. 1 Introduction
    2. 2 A matroid primer
    3. 3 Growth rates of minor-closed classes
    4. 4 Frame matroids and varieties
    5. 5 Regular matroids
    6. 6 Modularity
    7. 7 Branch width and tangles
    8. 8 Grids
    9. 9 Core classes and deviations
    10. 10 Bounded rank perturbations
    11. 11 Back to tangles
    12. 12 Progress towards Rota’s Conjecture
    13. References
  15. Automatic counting of tilings of skinny plane regions
    1. 1 Very important
    2. 2 How it all started: April 5, 2012
    3. 3 C-finite sequences
    4. 4 The art of guessing
    5. 5 Orders of recurrences
    6. 6 Rational generating functions
    7. 7 Why is the number of tilings of the Knuth square-ring C-finite?
    8. 8 A more efficient way
    9. 9 An even more efficient way
    10. 10 Mihai Ciucu’s amazing theorem
    11. 11 The number of domino tilings of a rectangle of a fixed width
    12. 12 Counting the number of domino tilings of a holey rectangle
    13. 13 The bivariate generating function
    14. 14 Tiling crosses
    15. 15 Monomer-dimer tilings
    16. 16 Weighted counting
    17. 17 The Maple package ARGF
    18. 18 Conclusion
    19. Acknowledgements
    20. References