Combinatorics and Probability

by Edited by Graham Brightwell , Imre Leader , Alex Scott , Andrew Thomason

• ISBN13: 9780521872072
• ISBN10: 0521872073
• Format: Hardcover
• Copyright: 2007-04-09
• Publisher: Cambridge University Press

Summary

Combinatorics is an area of mathematics involving an impressive breadth of ideas, and it encompasses topics ranging from codes and circuit design to algorithmic complexity and algebraic graph theory. In a highly distinguished career Béla Bollobás has made, and continues to make, many significant contributions to combinatorics, and this volume reflects the wide range of topics on which his work has had a major influence. It arises from a conference organized to mark his 60th birthday and the thirty-one articles contained here are of the highest calibre. That so many excellent mathematicians have contributed is testament to the very high regard in which Béla Bollobás is held. Students and researchers across combinatorics and related fields will find that this volume provides a wealth of insight to the state of the art.

Table of Contents

Preface	p. ix
Foreword	p. xi
Photographs	p. xx
Contributors	p. xxv
Measures of Pseudorandomness for Finite Sequences: Minimal Values	p. 1
MaxCut in H-Free Graphs	p. 31
A Tale of Three Couplings: Poisson-Dirichlet and GEM Approximations for Random Permutations	p. 51
Positional Games	p. 83
Degree Distribution of Competition-Induced Preferential Attachment Graphs	p. 132
On Two Conjectures on Packing of Graphs	p. 157
Approximate Counting and Quantum Computation	p. 171
Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs	p. 189
Duality in Infinite Graphs	p. 201
Homomorphism-Homogeneous Relational Structures	p. 217
A Spectral Turan Theorem	p. 231
Automorphism Groups of Metacirculant Graphs of Order a Product of Two Distinct Primes	p. 245
On the Number of Hamiltonian Cycles in a Tournament	p. 271
The Game of JumbleG	p. 285
2-Bases of Quadruples	p. 297
On Triple Systems with Independent Neighbourhoods	p. 309
Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs	p. 329
Triangle-Free Hypergraphs	p. 371
Odd Independent Transversals are Odd	p. 379
The First Eigenvalue of Random Graphs	p. 399
On the Number of Monochromatic Solutions of x + y = z[superscript 2]	p. 413
Rapid Steiner Symmetrization of Most of a Convex Body and the Slicing Problem	p. 429
A Note on Bipartite Graphs Without 2k-Cycles	p. 445
Book Ramsey Numbers and Quasi-Randomness	p. 451
Homomorphism and Dimension	p. 461
The distance of a permutation from a subgroup of S[subscript n]	p. 473
On Dimensions of a Random Solid Diagram	p. 481
The Small Giant Component in Scale-Free Random Graphs	p. 505
A Dirac-Type Theorem for 3-Uniform Hypergraphs	p. 547
On Dependency Graphs and the Lattice Gas	p. 571
Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time	p. 599
Table of Contents provided by Ingram. All Rights Reserved.