Surveys in combinatorics 2007 : [21st Biennial British Combinatorial Conference ... Reading in July 2007

This volume contains survey articles based on the invited lectures given at the Twenty-first British Combinatorial Conference, held in July 2007 at the University of Reading. This biennial conference is a well-established international event and the articles are of the high quality that befits the event. By its nature this volume provides an up-to-date overview of current research activity in several areas of combinatorics, ranging from graph theory to current applications of combinatorial mathematics, including efficient approximability of NP-hard optimization problems and cryptographic key management. The authors are some of the world's foremost researchers in their fields, and here they summarize existing results, and give a unique preview of work currently being written up. The book provides a valuable survey of the present state of knowledge in combinatorics. It will be useful to research workers and advanced graduate students, primarily in mathematics but also in computer science, statistics and engineering. Cover......Page 1 London Mathematical Society Lecture Note Series 346......Page 2 Surveys in Combinatorics 2007......Page 4 9780521698238......Page 5 Contents......Page 6 Preface......Page 8 1 Introduction......Page 10 2 Hereditary and Monotone Properties......Page 12 3 Measures of Properties......Page 14 4 The Cover Inequality, the Box Theorem, and Large Hereditary Properties......Page 18 5 Hereditary Properties of Graphs......Page 21 6 Classifying Labelled Speeds......Page 25 7 Monotone Properties......Page 29 8 Unlabelled Speed......Page 30 9 Colouring Random Graphs with Hereditary Properties......Page 31 10 The Distance from a Hereditary Property......Page 33 11 Posets, Permutations, Ordered Hypergraphs, and Partitions......Page 34 12 Words......Page 39 References......Page 43 1 Introduction......Page 50 2 Bruhat order on A(R, S)......Page 51 3 Bruhat order on Z+(R, S)......Page 55 4 Ordering A(R, S) by shape of insertion tableau......Page 56 5 Bruhat order on symmetric matrices......Page 60 6 Ordering by spectral radius (index)......Page 62 7 Ordering by rank......Page 68 8 Higher-dimensional permutation arrays......Page 69 References......Page 72 1 Introduction......Page 76 2 Uniform length cycles......Page 79 3 Cycles of varying lengths......Page 89 References......Page 102 1 Introduction......Page 108 2 Perfect Graphs......Page 109 3 Claw-free Graphs......Page 112 4 Bull-free Graphs......Page 117 5 Trigraphs......Page 119 6 Even-hole-free Graphs......Page 121 7 Detecting Induced Subgraphs......Page 123 References......Page 126 1 Context......Page 130 2 Preliminaries......Page 131 3 Existence......Page 134 4 Growth estimates......Page 138 5 Orientable cyclic biembeddings......Page 144 6 Enumeration......Page 147 7 Trades......Page 150 8 Maximum genus embeddings......Page 155 9 Hamiltonian embeddings......Page 159 10 Latin squares......Page 164 11 Symmetric configurations......Page 170 12 Concluding remarks......Page 173 References......Page 177 1 Introduction......Page 184 2 Background......Page 185 3 The zeta function......Page 189 4 Equality in the Hasse–Weil bound......Page 190 5 Examples of maximal curves......Page 192 6 Theoretical background......Page 193 7 Some optimal curves......Page 195 8 The Frobenius linear series of a maximal curve......Page 197 9 Maximal curves of large genus......Page 198 10 Non-isomorphic maximal curves......Page 200 11 Singular plane curves......Page 202 12 Counting points on a plane curve......Page 205 References......Page 207 1 Introduction......Page 210 2 Efficient computation......Page 212 3 Maximal constraint satisfaction problems......Page 213 4 Approximation algorithms......Page 214 5 Constraints on two variables......Page 216 6 Some approximation resistant predicates......Page 219 7 Proof systems......Page 220 8 Constraints on three Boolean variables......Page 223 9 Max-CSP on Boolean variables of higher width......Page 225 11 Conclusions and open problem......Page 227 References......Page 228 1 Introduction......Page 232 2 Cryptographic key management......Page 233 3 Key establishment framework......Page 235 4 Preliminaries......Page 239 5 Key predistribution schemes......Page 241 6 Group key distribution schemes......Page 255 7 Group key agreement schemes......Page 265 8 Concluding remarks......Page 275 References......Page 276 1 Introduction......Page 284 2 Faithful branch-decompositions......Page 286 3 Connected branch-decompositions......Page 287 4 The partition Lemma......Page 291 References......Page 294 This 2007 Volume Contains Survey Articles Based On The Invited Lectures Given At The Twenty-first British Combinatorial Conference, Held In July 2007 At The University Of Reading. This Biennial Conference Is A Well-established International Event And The Articles Are Of The High Quality That Befits The Event. By Its Nature This Volume Provides An Overview Of Current Research Activity In Several Areas Of Combinatorics, Ranging From Graph Theory To Current Applications Of Combinatorial Mathematics, Including Efficient Approximability Of Np-hard Optimization Problems And Cryptographic Key Management. The Authors Are Some Of The World's Foremost Researchers In Their Fields, And Here They Summarize Existing Results, And Give A Unique Preview Of Work Currently Being Written Up. The Book Provides A Valuable Survey Of The State Of Knowledge In Combinatorics. It Will Be Useful To Research Workers And Advanced Graduate Students, Primarily In Mathematics But Also In Computer Science, Statistics And Engineering. Hereditary And Monotone Propertie Of Combinatorial Structures / Béla Bollobás -- Ordering Classes Of Matrices Of 0s And 1s / Richard A. Brualdi -- Cycle Decompositions Of Complete Graphs / Darryn Bryant -- Excluding Induced Subgraphs / Maria Chudnovsky And Paul Seymour -- Designs And Topology / M.j. Grannell And T.s. Griggs -- The Number Of Points On An Algebraic Curve Over A Finite Field / J.w.p. Hirschfeld, G. Korchmáros, And F. Torres -- On The Efficient Approximability Of Constraint Satisfaction Problems / Johan H°astad -- The Combinatorics Of Cryptographic Key Establishment / Keith M. Martin -- Bandwidth Of Graphic Matroids / Frédéric Mazoit And Stéphan Thomassé. Edited By Anthony Hilton, John Talbot. Papers From The 21st British Combinatorial Conference At Reading, 2007 - Preface. Includes Bibliographical References. 2 Efficient computation3 Maximal constraint satisfaction problems; 4 Approximation algorithms; 5 Constraints on two variables; 6 Some approximation resistant predicates; 7 Proof systems; 8 Constraints on three Boolean variables; 9 Max-CSP on Boolean variables of higher width; 10 Exact constants and the unique games conjecture; 11 Conclusions and open problem; 8 The combinatorics of cryptographic key establishment; 1 Introduction; 2 Cryptographic key management; 3 Key establishment framework; 3.1 Broad classification of key establishment schemes; 3.2 Secondary distinguishers; 3.2.1 Security 3 Cycles of varying lengths3.1 Summary of results; 3.2 Häggkvist's cycle decomposition lemma; 3.3 Balister's trails of octahedra method; 3.4 Cycle repacking; 4 Excluding induced subgraphs; 1 Introduction; 2 Perfect Graphs; 3 Claw-free Graphs; 4 Bull-free Graphs; 5 Trigraphs; 6 Even-hole-free Graphs; 7 Detecting Induced Subgraphs; 8 Acknowledgments; 5 Designs and topology; 1 Context; 2 Preliminaries; 3 Existence; 4 Growth estimates; 5 Orientable cyclic biembeddings; 6 Enumeration; 7 Trades; 8 Maximum genus embeddings; 9 Hamiltonian embeddings; 10 Latin squares; 11 Symmetric configurations 1 Introduction2 Bruhat order on A(R, S); 3 Bruhat order on Z+(R, S); 4 Ordering A(R, S) by shape of insertion tableau; 5 Bruhat order on symmetric matrices; 6 Ordering by spectral radius (index); 7 Ordering by rank; 8 Higher-dimensional permutation arrays; 3 Cycle decompositions of complete graphs; 1 Introduction; 1.1 Overview; 1.2 Definitions and notation; 2 Uniform length cycles; 2.1 The spectrum problem for m-cycles; 2.2 Reduction of the spectrum problem for m-cycles; 2.3 Solution to the spectrum problem for m-cycles; 2.4 m-cycle decompositions of complete graphs minus a 1-factor Cover; Title; Copyright; Contents; Preface; 1 Hereditary and monotone properties of combinatorial structures; 1 Introduction; 2 Hereditary and Monotone Properties; 3 Measures of Properties; 4 The Cover Inequality, the Box Theorem, and Large Hereditary Properties; 5 Hereditary Properties of Graphs; 6 Classifying Labelled Speeds; 7 Monotone Properties; 8 Unlabelled Speed; 9 Colouring Random Graphs with Hereditary Properties; 10 The Distance from a Hereditary Property; 11 Posets, Permutations, Ordered Hypergraphs, and Partitions; 12 Words; 2 Ordering classes of matrices of 0's and 1's 12 Concluding remarks6 The number of points on an algebraic curve over a finite field; 1 Introduction; 2 Background; 2.1 Planes; 2.2 Plane curves; 2.3 Affine and projective curves; 3 The zeta function; 4 Equality in the Hasse-Weil bound; 5 Examples of maximal curves; 6 Theoretical background; 7 Someoptimalcurves; 8 The Frobenius linear series of a maximal curve; 9 Maximal curves of large genus; 10 Non-isomorphic maximal curves; 11 Singular plane curves; 12 Counting points on a plane curve; 7 On the efficient approximability of constraint satisfaction problems; 1 Introduction