Last update:
Mon Jul 7 20:01:56 MDT 2008
László Babai and
Márió Szegedy Local expansion of symmetrical graphs 1--11
C. D. Godsil Walk generating functions,
Christoffel--Darboux identities and the
adjacency matrix of a graph . . . . . . 13--25
Roland Häggkvist On the structure of non-Hamiltonian
graphs. I . . . . . . . . . . . . . . . 27--34
Tomasz \Luczak and
Boris Pittel Components of random forests . . . . . . 35--52
Hans Jürgen Prömel and
Angelika Steger Almost all Berge graphs are perfect . . 53--79
Joel Spencer and
Peter Winkler Three thresholds for a liar . . . . . . 81--93
John C. Wierman Equality of the bond percolation
critical exponents for two pairs of dual
lattices . . . . . . . . . . . . . . . . 95--105
Noga Alon Choice numbers of graphs: a
probabilistic approach . . . . . . . . . 107--114
A. R. Calderbank and
P. Frankl Improved upper bounds concerning the
Erd\Hos--Korado theorem . . . . . . . . 115--122
Neil Calkin and
Alan Frieze and
Brendan D. McKay On subgraph sizes in random graphs . . . 123--134
Persi Diaconis and
James Allen Fill and
Jim Pitman Analysis of top to random shuffles . . . 135--155
Colin McDiarmid On a correlation inequality of Farr . . 157--160
Ora Engelberg Percus and
Jerome K. Percus An expanded set of correlation tests for
linear congruential random number
generators . . . . . . . . . . . . . . . 161--168
A. Ruci\'nski and
N. C. Wormald Random graph processes with degree
restrictions . . . . . . . . . . . . . . 169--180
D. L. Vertigan and
D. J. A. Welsh The computational complexity of the
Tutte plane: the bipartite case . . . . 181--187
Noga Alon and
Imre Bárány and
Zoltán Füredi and
Daniel J. Kleitman Point selections and weak
$\epsilon$-nets for convex hulls . . . . 189--200
L. Babai and
G. L. Hetyei On the diameter of random Cayley graphs
of the symmetric group . . . . . . . . . 201--208
Victor Bryant A characterisation of strict matching
matroids . . . . . . . . . . . . . . . . 209--217
Y. Fan and
J. K. Percus Duality for random sequential adsorption
on a lattice . . . . . . . . . . . . . . 219--222
Jerzy Jaworski and
Tomasz \Luczak Cycles in a uniform graph process . . . 223--239
Guo Ping Jin Complete subgraphs of $r$-partite graphs 241--250
Tamás F. Móri Maximum waiting times are asymptotically
independent . . . . . . . . . . . . . . 251--264
B. Reed and
Colin McDiarmid The strongly connected components of
$1$-in, $1$-out . . . . . . . . . . . . 265--274
Geoff Whittle Duality in polymatroids and set
functions . . . . . . . . . . . . . . . 275--280
David Aldous Greedy search on the binary tree with
random edge-weights . . . . . . . . . . 281--293
Imre Bárány and
János Pach On the number of convex lattice polygons 295--302
Colin Cooper On the thickness of sparse random graphs 303--309
János A. Csirik Optimal strategy for the first player in
the Penney Ante game . . . . . . . . . . 311--321
Péter L. Erd\Hos and
Ulrich Faigle and
Walter Kern A group-theoretic setting for some
intersecting Sperner families . . . . . 323--334
A. D. Scott Large induced subgraphs with all degrees
odd . . . . . . . . . . . . . . . . . . 335--349
Alistair Sinclair Improved bounds for mixing rates of
Markov chains and multicommodity flow 351--370
Carsten Thomassen Plane cubic graphs with prescribed face
areas . . . . . . . . . . . . . . . . . 371--381
Peter J. Cameron and
Cleide Martins A theorem on reconstruction of random
graphs . . . . . . . . . . . . . . . . . 1--9
John Gates Some dual problems of geometric
probability in the plane . . . . . . . . 11--23
Roland Häggkvist Hamilton cycles in oriented graphs . . . 25--32
Joseph P. S. Kung Sign-coherent identities for
characteristic polynomials of matroids 33--51
Boris Pittel On a random instance of a ``stable
roommates'' problem: likely behavior of
the proposal algorithm . . . . . . . . . 53--92
D. H. Smith Optimally reliable graphs for both
vertex and edge failures . . . . . . . . 93--100
Martin Aigner and
Eberhard Triesch Reconstructing a graph from its
neighborhood lists . . . . . . . . . . . 103--113
Sven Erick Alm Upper bounds for the connective constant
of self-avoiding walks . . . . . . . . . 115--136
Noga Alon and
Raphael Yuster Threshold functions for $H$-factors . . 137--144
Philippe Flajolet and
Zhicheng Gao and
Andrew Odlyzko and
Bruce Richmond The distribution of heights of binary
trees and other simple trees . . . . . . 145--156
William M. Y. Goh and
Eric Schmutz Random matrices and Brownian motion . . 157--180
Gregory F. Lawler A discrete analogue of a theorem of
Makarov . . . . . . . . . . . . . . . . 181--199
Nguy\cftilen V\uan Ng\doc and
Zsolt Tuza Linear-time approximation algorithms for
the max cut problem . . . . . . . . . . 201--210
Rudolf Ahlswede and
Ning Cai On extremal set partitions in Cartesian
product spaces . . . . . . . . . . . . . 211--220
Vitaly Bergelson and
Neil Hindman Additive and multiplicative Ramsey
theorems in \boldmath $N$---some
elementary results . . . . . . . . . . . 221--241
Norman L. Biggs Potential theory on distance-regular
graphs . . . . . . . . . . . . . . . . . 243--255
Peter J. Cameron and
William M. Kantor Random permutations: some
group-theoretic aspects . . . . . . . . 257--262
G. Chen and
R. H. Schelp Ramsey problems with bounded degree
spread . . . . . . . . . . . . . . . . . 263--269
Martin Dyer and
Alan Frieze and
Ravi Kannan and
Ajai Kapoor and
Ljubomir Perkovic and
Umesh Vazirani A mildly exponential time algorithm for
approximating the number of solutions to
a multidimensional knapsack problem . . 271--284
Jennie C. Hansen Factorization in \boldmath $F_q[x]$ and
Brownian motion . . . . . . . . . . . . 285--299
Salvatore Ingrassia Geometric approaches to the estimation
of the spectral gap of reversible Markov
chains . . . . . . . . . . . . . . . . . 301--323
Bill Jackson A zero-free interval for chromatic
polynomials of graphs . . . . . . . . . 325--336
Miro Kraetzl and
Charles J. Colbourn Threshold channel graphs . . . . . . . . 337--349
James F. Lynch Threshold functions for Markov chains: a
graph-theoretic approach . . . . . . . . 351--362
Colin McDiarmid A random recolouring method for graphs
and hypergraphs . . . . . . . . . . . . 363--365
Safwan Akkari and
James Oxley Some local extremal connectivity results
for matroids . . . . . . . . . . . . . . 367--384
Martin Anthony and
John Shawe-Taylor Using the perceptron algorithm to find
consistent hypotheses . . . . . . . . . 385--387
Paul Erd\Hos and
R. J. Faudree and
C. C. Rousseau and
R. H. Schelp Ramsey size linear graphs . . . . . . . 389--399
Paul Erd\Hos and
Endre Makai and
János Pach Nearly equal distances in the plane . . 401--408
Paul Erd\Hos and
Edward T. Ordman and
Yechezkel Zalcstein Clique partitions of chordal graphs . . 409--415
R. Halin Minimization problems for infinite
$n$-connected graphs . . . . . . . . . . 417--436
Neil Hindman and
Imre Leader Image partition regularity of matrices 437--463
Christoph Hundack and
Hans Jürgen Prömel and
Angelika Steger Extremal graph problems for graphs with
a color-critical vertex . . . . . . . . 465--477
Guo Ping Jin Triangle-free graphs with high minimal
degrees . . . . . . . . . . . . . . . . 479--490
Nathan Linial Local-global phenomena in graphs . . . . 491--503
Tomasz \Luczak and
László Pyber On random generation of the symmetric
group . . . . . . . . . . . . . . . . . 505--512
A. Razborov and
E. Szemerédi and
A. Wigderson Constructing small sets that are uniform
in arithmetic progressions . . . . . . . 513--518
Dirk Vertigan and
Geoff Whittle Recognizing polymatroids associated with
hypergraphs . . . . . . . . . . . . . . 519--530
D. K. Arrowsmith and
J. W. Essam Reciprocity and polynomial properties
for even flows and potentials on
directed graphs . . . . . . . . . . . . 1--11
József Beck Deterministic graph games and a
probabilistic intuition . . . . . . . . 13--26
Sergej L. Bezrukov On oriented embedding of the binary tree
into the hypercube . . . . . . . . . . . 27--38
Colin Cooper and
Alan Frieze and
Michael Molloy Hamilton cycles in random regular
digraphs . . . . . . . . . . . . . . . . 39--49
Reinhard Diestel and
Imre Leader The growth of infinite graphs:
boundedness and finite spreading . . . . 51--55
Péter L. Erd\Hos and
Ákos Seress and
László A. Székely On intersecting chains in Boolean
algebras . . . . . . . . . . . . . . . . 57--62
Zoltán Füredi and
Michel X. Goemans and
Daniel J. Kleitman On the maximum number of triangles in
wheel-free graphs . . . . . . . . . . . 63--75
Mario Gionfriddo and
Salvatore Milici and
Zsolt Tuza Blocking sets in ${\rm SQS}(2v)$ . . . . 77--86
Roland Häggkvist and
Anders Johansson $(1,2)$-factorizations of general
Eulerian nearly regular graphs . . . . . 87--95
Svante Janson The numbers of spanning trees, Hamilton
cycles and perfect matchings in a random
graph . . . . . . . . . . . . . . . . . 97--126
Jaroslav Ne\vset\vril and
Pavel Valtr A Ramsey-type theorem in the plane . . . 127--135
D. J. A. Welsh Randomised approximation in the Tutte
plane . . . . . . . . . . . . . . . . . 137--143
Ron Aharoni and
Reinhard Diestel Menger's theorem for a countable source
set . . . . . . . . . . . . . . . . . . 145--156
Martin Aigner and
Regina Klimmek Matchings in lattice graphs and Hamming
graphs . . . . . . . . . . . . . . . . . 157--165
A. D. Barbour and
Simon Tavaré A rate for the Erd\Hos--Turán law . . . . 167--176
Walter A. Deuber and
Wolfgang Thumser A combinatorial approach to complexity
theory via ordinal hierarchies . . . . . 177--190
Michel Deza and
Viatcheslav Grishukhin Lattice points of cut cones . . . . . . 191--214
J. K. Dugdale and
A. J. W. Hilton Amalgamated factorizations of complete
graphs . . . . . . . . . . . . . . . . . 215--231
Hubert de Fraysseix and
Patrice Ossona de Mendez and
Pierre Rosenstiehl On triangle contact graphs . . . . . . . 233--246
János Komlós and
Endre Szemerédi Topological cliques in graphs . . . . . 247--256
W. Mader On vertex-edge-critically $n$-connected
graphs . . . . . . . . . . . . . . . . . 257--271
J. D. Annan A randomised approximation algorithm for
counting the number of forests in dense
graphs . . . . . . . . . . . . . . . . . 273--283
Yossi Azar Lower bounds for insertion methods for
TSP . . . . . . . . . . . . . . . . . . 285--292
Paul Erd\Hos and
András Gyárfás and
Tomasz \Luczak Independent transversals in sparse
partite hypergraphs . . . . . . . . . . 293--296
P. Erd\Hos and
A. Hajnal and
M. Simonovits and
V. T. Sós and
E. Szemerédi Turán--Ramsey theorems and
$K_p$-independence numbers . . . . . . . 297--325
P. L. Hammer and
A. K. Kelmans On universal threshold graphs . . . . . 327--344
Abba M. Krieger and
Paul R. Rosenbaum A stochastic comparison for arrangement
increasing functions . . . . . . . . . . 345--348
Michael Krivelevich $K^s$-free graphs without large
$K^r$-free subgraphs . . . . . . . . . . 349--354
Manoel Lemos Non-binary matroids having at most three
non-binary elements . . . . . . . . . . 355--369
Allan D. Mills A matroid reconstruction result . . . . 371--373
Bojan Mohar Obstructions for the disk and the
cylinder embedding extension problems 375--406
A. Nilli Perfect hashing and probability . . . . 407--409
Andrzej Pelc Almost safe group testing with few tests 411--419
Prasad Tetali An extension of Foster's network theorem 421--427
Rudolf Ahlswede and
Ning Cai On partitioning and packing products
with rectangles . . . . . . . . . . . . 429--434
Neal Brand and
Steve Jackson Properties of classes of random graphs 435--454
Moshe Dubiner and
Uri Zwick How do read-once formulae shrink? . . . 455--469
J. M. Hammersley and
G. Mazzarino Properties of large Eden clusters in the
plane . . . . . . . . . . . . . . . . . 471--505
C.-P. Schnorr Block reduced lattice bases and
successive minima . . . . . . . . . . . 507--522
Farhad Shahrokhi and
László A. Székely On canonical concurrent flows, crossing
number and graph expansion . . . . . . . 523--543
Arthur T. White An introduction to random topological
graph theory . . . . . . . . . . . . . . 545--555
Joseph E. Bonin Automorphisms of Dowling lattices and
related geometries . . . . . . . . . . . 1--9
F. R. K. Chung and
S.-T. Yau Eigenvalues of graphs and Sobolev
inequalities . . . . . . . . . . . . . . 11--25
Reinhard Diestel Graph minors. I. A short proof of the
path-width theorem. Comment on: ``Graph
minors. I. Excluding a forest'' [J.
Combin. Theory Ser. B \bf 35 (1983), no.
1, 39--61; MR0723569 (85d:05148)] by N.
Robertson and P. D. Seymour . . . . . . 27--30
Keith Edwards The harmonious chromatic number of
almost all trees . . . . . . . . . . . . 31--46
Alan Frieze and
A. J. Radcliffe and
Stephen Suen Analysis of a simple greedy matching
algorithm on random cubic graphs . . . . 47--66
Fair Barbour Hurst and
Talmage James Reid Some small circuit--cocircuit Ramsey
numbers for matroids . . . . . . . . . . 67--80
W. Mader On vertices of degree $n$ in minimally
$n$-edge-connected graphs . . . . . . . 81--95
Jeong Han Kim On Brooks' theorem for sparse graphs . . 97--132
Gregory F. Lawler Recurrence and transience for a card
shuffling model . . . . . . . . . . . . 133--142
Guy Louchard and
Wojciech Szpankowski A probabilistic analysis of a string
editing problem and its variations . . . 143--166
Oleg Verbitsky On the hardness of approximating some
optimization problems that are
supposedly easier than MAX CLIQUE . . . 167--180
John C. Wierman Substitution method critical probability
bounds for the square lattice site
percolation model . . . . . . . . . . . 181--188
A. El Maftouhi and
W. Fernandez de la Vega On random $3$-sat . . . . . . . . . . . 189--195
Takashi Hara and
Gordon Slade The self-avoiding-walk and percolation
critical points in high dimensions . . . 197--215
P. E. Haxell and
Y. Kohayakawa and
T. \Luczak The induced size-Ramsey number of cycles 217--239
János Komlós and
Gábor N. Sárközy and
Endre Szemerédi Proof of a packing conjecture of Bollobás 241--255
Colin McDiarmid and
Bruce Reed Almost every graph can be covered by
$\lceil{\Delta/2}\rceil$ linear forests 257--268
F. Matú\vs and
M. Studený Conditional independences among four
random variables. I . . . . . . . . . . 269--278
Dudley Stark First occurrence in pairs of long words:
a Penney-ante conjecture of Pevzner . . 279--285
Mikkel Thorup Shortcutting planar digraphs . . . . . . 287--315
Gunnar Brinkmann and
Brendan D. McKay and
Carsten Saager The smallest cubic graphs of girth nine 317--329
Tuhao Chen and
E. Seneta Multivariate identities, permutation and
Bonferroni upper bounds . . . . . . . . 331--342
Colin Cooper and
Alan Frieze On the connectivity of random $k$th
nearest neighbour graphs . . . . . . . . 343--362
Yahya Ould Hamidoune On weighted sequence sums . . . . . . . 363--367
Svante Janson Random regular graphs: asymptotic
distributions and contiguity . . . . . . 369--405
F. Matú\vs Conditional independences among four
random variables. II . . . . . . . . . . 407--417
L. Saloff-Coste Isoperimetric inequalities and decay of
iterated kernels for almost-transitive
Markov chains . . . . . . . . . . . . . 419--442
Colin Cooper and
Alan Frieze and
Michael Molloy and
Bruce Reed Perfect matchings in random $r$-regular,
$s$-uniform hypergraphs . . . . . . . . 1--14
Keith Edwards The harmonious chromatic number of
bounded degree trees . . . . . . . . . . 15--28
Zoltán Füredi An upper bound on Zarankiewicz' problem 29--33
M. Hujter and
Zs. Tuza Precoloring extension. III. Classes of
perfect graphs . . . . . . . . . . . . . 35--56
K. Kilakos and
B. Shepherd Excluding minors in cubic graphs . . . . 57--78
János Komlós and
Endre Szemerédi Topological cliques in graphs. II . . . 79--90
Toma\vz Slivnik Short proof of Galvin's theorem on the
list-chromatic index of a bipartite
multigraph . . . . . . . . . . . . . . . 91--94
C. C. Chen and
G. P. Jin Cycle partitions in graphs . . . . . . . 95--97
Amanda Chetwynd and
Roland Häggkvist An improvement of Hind's upper bound on
the total chromatic number . . . . . . . 99--104
Anant P. Godbole and
Daphne E. Skipper and
Rachel A. Sunley $t$-covering arrays: upper bounds and
Poisson approximations . . . . . . . . . 105--117
W. T. Gowers An almost $m$-wise independent random
permutation of the cube . . . . . . . . 119--130
Valery A. Liskovets Some asymptotical estimates for planar
Eulerian maps . . . . . . . . . . . . . 131--138
Claudia Neuhauser A phase transition for the distribution
of matching blocks . . . . . . . . . . . 139--159
Laurent Saloff-Coste and
Wolfgang Woess Computing norms of group-invariant
transition operators . . . . . . . . . . 161--178
Carsten Thomassen $K_5$-subdivisions in graphs . . . . . . 179--189
Martin Anthony and
Peter Bartlett and
Yuval Ishai and
John Shawe-Taylor Valid generalisation from approximate
interpolation . . . . . . . . . . . . . 191--214
C. Cooper Asymptotic enumeration of
predicate-junction flowgraphs . . . . . 215--226
Bradley S. Gubser A characterization of almost-planar
graphs . . . . . . . . . . . . . . . . . 227--245
C. Douglas Howard Orthogonality of measures induced by
random walks with scenery . . . . . . . 247--256
Wojciech Kordecki Small submatroids in random matroids . . 257--266
Aleksandar Peke\vc A winning strategy for the Ramsey graph
game . . . . . . . . . . . . . . . . . . 267--276
Bruce Reed Paths, stars and the number three . . . 277--295
Rachid Saad Finding a longest alternating cycle in a
$2$-edge-coloured complete graph is in
RP . . . . . . . . . . . . . . . . . . . 297--306
Janusz Szuster and
Pawe\l Wla\'z and
Jerzy \.Zurawiecki On recognition of shift registers . . . 307--315
Gerd Baron and
Michael Drmota and
Ljuben Mutafchiev Predecessors in random mappings . . . . 317--335
Bogdan S. Chlebus and
Krzysztof Diks and
Andrzej Pelc Reliable broadcasting in hypercubes with
random link and node failures . . . . . 337--350
Robert P. Dobrow and
James Allen Fill Multiway trees of maximum and minimum
probability under the random permutation
model . . . . . . . . . . . . . . . . . 351--371
Konrad Engel Interval packing and covering in the
Boolean lattice . . . . . . . . . . . . 373--384
Roland Häggkvist Restricted edge-colourings of bipartite
graphs . . . . . . . . . . . . . . . . . 385--392
Norbert Hegyvári Subset sums in \boldmath $N^2$ . . . . . 393--402
Ewa Kubicka An efficient method of examining all
trees . . . . . . . . . . . . . . . . . 403--413
John Shawe-Taylor Fast string matching in stationary
ergodic sources . . . . . . . . . . . . 415--427
Z. Skupie\'n Smallest sets of longest paths with
empty intersection . . . . . . . . . . . 429--436
Carsten Thomassen On the number of Hamiltonian cycles in
bipartite graphs . . . . . . . . . . . . 437--442
A. D. Barbour and
Anant P. Godbole and
Jinghua Qian Imperfections in Random Tournaments . . 1--15
Edward A. Bender and
E. Rodney Canfield and
Zhicheng Gao and
L. Bruce Ricmond Submap Density and Asymmetry Results for
Two Parameter Map Families . . . . . . . 17--25
Laurent Decreusefond and
Gilles ZéMor On the Error-Correcting Capabilities of
Cycle Codes of Graphs . . . . . . . . . 27--38
Tristan Denley On a Result of Lemke and Kleitman . . . 39--43
Kimmo Eriksson Autocorrelation and the Enumeration of
Strings Avoiding a Fixed String . . . . 45--48
Andrew S. Greenhalgh A Model for Random Random-Walks on
Finite Groups . . . . . . . . . . . . . 49--56
Ulrich Martin Hirth Probabilistic Number Theory, the
GEM/Poisson--Dirichlet Distribution and
the Arc-sine Law . . . . . . . . . . . . 57--77
Colin McDiarmid Centering Sequences with Bounded
Differences . . . . . . . . . . . . . . 79--86
Dudley Stark Explicit Limits of Total Variation
Distance in Approximations of Random
Logarithmic Assemblies by Related
Poisson Processes . . . . . . . . . . . 87--105
Pou-Lin Wu An Upper Bound on the Number of Edges of
a $2$-Connected Graph . . . . . . . . . 107--113
Raphael Yuster Independent Transversals and Independent
Coverings in Sparse Partite Graphs . . . 115--125
R. Ahlswede and
N. Alon and
P. L. Erd\Hos and\'nRuszinkó and
L. A. Székely Intersecting Systems . . . . . . . . . . 127--137
S. Alesker A Remark on the Szarek--Talagrand
Theorem . . . . . . . . . . . . . . . . 139--144
Noga Alon On the Edge-Expansion of Graphs . . . . 145--152
E. J. Cockayne and
C.\'nMynhardt Irredundance and Maximum Degree in
Graphs . . . . . . . . . . . . . . . . . 153--157
Lenore Cowen and
Rudolph Mathar The Offset Problem . . . . . . . . . . . 159--164
D. Crippa and
K. Simon and
P. Trunz Markov Processes Involving $q$-Stirling
Numbers . . . . . . . . . . . . . . . . 165--178
Peter J. Grabner and
Helmut Prodinger Maximum Statistics of $N$ Random
Variables Distributed by the Negative
Binomial Distribution . . . . . . . . . 179--183
Ulrich Martin Hirth From GEM back to Dirichlet via Hoppe's
Urn . . . . . . . . . . . . . . . . . . 185--195
Irene Hueter and
Yuval Peres Self-Affine Carpets on the Square
Lattice . . . . . . . . . . . . . . . . 197--204
L. Pronzato and
H. P. Wynn and
A. A. Zhigljavsky Stochastic Analysis of Convergence via
Dynamic Representation for a Class of
Line-search Algorithms . . . . . . . . . 205--229
Frank Vogt and
Bernd Voigt Symmetric Chain Decompositions of Linear
Lattices . . . . . . . . . . . . . . . . 231--245
Van H. Vu On a Theorem of Ganter . . . . . . . . . 247--254
Jòrgen Bang-Jensen and
Gregory Gutin and
Anders Yeo Hamiltonian Cycles Avoiding Prescribed
Arcs in Tournaments . . . . . . . . . . 255--261
Neil J. Calkin Dependent Sets of Constant Weight Binary
Vectors . . . . . . . . . . . . . . . . 263--271
Charles\'nGrinstead On Medians of Lattice Distributions and
a Game with Two Dice . . . . . . . . . . 273--294
Roland Häggkvist and
Jeannette Janssen New Bounds on the List-Chromatic Index
of the Complete Graph and Other Simple
Graphs . . . . . . . . . . . . . . . . . 295--313
Jennie C. Hansen Limit Laws for the Optimal Directed Tree
with Random Costs . . . . . . . . . . . 315--335
Michael Krivelevich Triangle Factors in Random Graphs . . . 337--347
Vojtech Rödl and
Andrzej Ruci\'nSki Bipartite Coverings of Graphs . . . . . 349--352
László A. Székely Crossing Numbers and Hard Erd\Hos
Problems in Discrete Geometry . . . . . 353--358
B. Tóth and
W. Werner Tied Favourite Edges for Simple Random
Walk . . . . . . . . . . . . . . . . . . 359--369
Ekkehard Weineck Log-Concavity and the Spectral Gap of
Stochastic Matrices . . . . . . . . . . 371--379
C. C. Chen and
G. P. Jin and
K.\'nKoh Triangle-Free Graphs with Large Degree 381--396
Hervé Daudé and
Philippe Flajolet and
Brigitte Vallée An Average-Case Analysis of the Gaussian
Algorithm for Lattice Reduction . . . . 397--433
James Allen Fill and
Robert P. Dobrow The Number of $m$-ary Search Trees on
$n$ Keys . . . . . . . . . . . . . . . . 435--453
Peter Firby and
Julie Haviland Maximal Spacing Configurations in Graphs 455--463
Nabil Kahale Large Deviation Bounds for Markov Chains 465--474
Ulrich Matthias Constructive Upper Bounds for the Turán
Number . . . . . . . . . . . . . . . . . 475--479
Attila Sali and
Gábor Simonyi Recovering Set Systems and Graph Entropy 481--491
Miroslav Tanushev and
Richard Arratia A Note on Distributional Equality in the
Cyclic Tour Property for Markov Chains 493--496
Carsten Thomassen The Zero-Free Intervals for Chromatic
Polynomials of Graphs . . . . . . . . . 497--506
David Aldous On the Critical Value for `Percolation'
of Minimum-Weight Trees in the
Mean-Field Distance Model . . . . . . . 1--10
Sven Erick Alm A Note on a Problem by Welsh in
First-Passage Percolation . . . . . . . 11--15
Jòrgen Bang-Jensen and
Tibor Jordán Adding and Reversing Arcs in
Semicomplete Digraphs . . . . . . . . . 17--25
Neil J. Calkin and
P. J. Cameron Almost Odd Random Sum-Free Sets . . . . 27--32
Dwight Duffus and
Tomasz \Luczak and
Vojt\vech Rödl and
Andrzej Ruci\'nski Endomorphisms of Partially Ordered Sets 33--46
P. Frankl and
K. Ota and
N. Tokushige Uniform Intersecting Families with
Covering Number Restrictions . . . . . . 47--56
D. A. Grable A Large Deviation Inequality for
Functions of Independent, Multi-Way
Choices . . . . . . . . . . . . . . . . 57--63
David S. Gunderson and
Vojtéch Rödl Extremal Problems for Affine Cubes of
Integers . . . . . . . . . . . . . . . . 65--79
Y. O. Hamidoune Adding Distinct Congruence Classes . . . 81--87
Hsien-Kuei Hwang A Poisson * Geometric Convolution Law
for the Number of Components in
Unlabelled Combinatorial Structures . . 89--110
Peter Kirschenhofer and
Helmut Prodinger Comparisons in Hoare's \tt find
Algorithm . . . . . . . . . . . . . . . 111--120
János Pach and
Micha Sharir On the Number of Incidences Between
Points and Curves . . . . . . . . . . . 121--127
Gunnar Brinkmann All Ramsey Numbers $r(K_3,G)$ for
Connected Graphs of Order $7$ and $8$ 129--140
F. R. K. Chung and
Prasad Tetali Isoperimetric Inequalities for Cartesian
Products of Graphs . . . . . . . . . . . 141--148
A. W. F. Edwards Seven-Set Venn Diagrams with Rotational
and Polar Symmetry . . . . . . . . . . . 149--152
Hugh Edwards and
Robert Hierons and
Bill Jackson The Zero-Free Intervals for
Characteristic Polynomials of Matroids 153--165
Neil Hindman and
Dona Strauss An Algebraic Proof of Deuber's Theorem 167--180
M. Juvan and
B. Mohar and
R. \vSKrekovski List Total Colourings of Graphs . . . . 181--188
László Lovász and
Peter Winkler Reversal of Markov Chains and the Forget
Time . . . . . . . . . . . . . . . . . . 189--204
András Lukács On Local Expansion of Vertex-Transitive
Graphs . . . . . . . . . . . . . . . . . 205--209
Michele Mosca Removing Edges Can Increase the Average
Number of Colours in the Colourings of a
Graph . . . . . . . . . . . . . . . . . 211--216
Richard H. Schelp and
Andrew Thomason A Remark on the Number of Complete and
Empty Subgraphs . . . . . . . . . . . . 217--219
William T. Trotter and
Peter Winkler Ramsey Theory and Sequences of Random
Variables . . . . . . . . . . . . . . . 221--238
M. D. Atkinson Generalized Stack Permutations . . . . . 239--246
P. Frankl and
N. Tokushige Some Inequalities Concerning
Cross-Intersecting Families . . . . . . 247--260
W. D. Gao and
Y. O. Hamidoune Zero Sums in Abelian Groups . . . . . . 261--263
Johan Jonasson On the Cover Time for Random Walks on
Random Graphs . . . . . . . . . . . . . 265--279
Akira Maruoka and
Mike Paterson and
Hirotaka Koizumi Consistency of Natural Relations on Sets 281--293
Michael Molloy and
Bruce Reed The Size of the Giant Component of a
Random Graph with a Given Degree
Sequence . . . . . . . . . . . . . . . . 295--305
S. D. Noble Evaluating the Tutte Polynomial for
Graphs of Bounded Tree-Width . . . . . . 307--321
Andrzej Pelc and
Eli Upfal Reliable Fault Diagnosis with Few Tests 323--333
Shuji Shiraishi On the Maximum Cut of Line Graphs . . . 335--337
Ma\lgorzata Bednarska On Biased Positional Games . . . . . . . 339--351
Tuhao Chen and
E. Seneta Lower Bounds for the Probability of
Intersection of Several Unions of Events 353--364
Vlado Dancík Common Subsequences and Supersequences
and their Expected Length . . . . . . . 365--373
Thomas Emden-Weinert and
Stefan Hougardy and
Bernd Kreuter Uniquely Colourable Graphs and the
Hardness of Colouring Graphs of Large
Girth . . . . . . . . . . . . . . . . . 375--386
Petros Hadjicostas The Asymptotic Proportion of
Subdivisions of a $2 \times 2$ Table
that Result in Simpson's Paradox . . . . 387--396
Olle Häggström On a Conjecture of Bollobás and
Brightwell Concerning Random Walks on
Product Graphs . . . . . . . . . . . . . 397--401
Yahya Ould Hamidoune and
Oscar Ordaz and
Asdrubal Ortuño On a Combinatorial Theorem of Erd\Hos,
Ginzburg and Ziv . . . . . . . . . . . . 403--412
Chris Jagger Distant Vertex Partitions of Graphs . . 413--422
Tomasz \Luczak and
Vojt\vech Rödl and
Endre Szemerédi Partitioning Two-Coloured Complete
Graphs into Two Monochromatic Cycles . . 423--436
Brendan D. McKay and
Robert W. Robinson Asymptotic Enumeration of Eulerian
Circuits in the Complete Graph . . . . . 437--449
Petr Savický Complexity and Probability of Some
Boolean Formulas . . . . . . . . . . . . 451--463
Kyle Siegrist Expected Value Expansions in Random
Subgraphs with Applications to Network
Reliability . . . . . . . . . . . . . . 465--483
Haidong Wu On Vertex-Triads in $3$-Connected Binary
Matroids . . . . . . . . . . . . . . . . 485--497
Paul Erd\Hos A selection of problems and results in
combinatorics . . . . . . . . . . . . . 1--6
Noga Alon Combinatorial Nullstellensatz . . . . . 7--29
E. A. Bender and
P. J. Cameron and
A. M. Odlyzko and
L. B. Richmond Connectedness, classes and cycle index 31--43
Béla Bollobás and
Oliver Riordan A Tutte polynomial for coloured graphs 45--93
Peter J. Cameron and
Paul Erd\Hos Notes on sum-free and related sets . . . 95--107
Hans-Georg Carstens and
Walter A. Deuber and
Wolfgang Thumser and
Elke Koppenrade Geometrical bijections in discrete
lattices . . . . . . . . . . . . . . . . 109--129
Micha\l Karo\'nski and
Edward R. Scheinerman and
Karen B. Singer-Cohen On random intersection graphs: the
subgraph problem . . . . . . . . . . . . 131--159
János Komlós The blow-up lemma . . . . . . . . . . . 161--176
Jaroslav Ne\vset\vril The homomorphism structure of classes of
graphs . . . . . . . . . . . . . . . . . 177--184
Richard Arratia and
A. D. Barbour and
Simon Tavaré On Poisson-Dirichlet limits for random
decomposable combinatorial structures 193--208
Sunil Arya and
Mordecai J. Golin and
Kurt Mehlhorn On the Expected Depth of Random Circuits 209--228
Joseph E. Bonin and
Jennifer McNulty and
Talmage James Reid The Matroid Ramsey Number $n{(6,6)}$ . . 229--235
Stephan Brandt On the Structure of Dense Triangle-Free
Graphs . . . . . . . . . . . . . . . . . 237--245
Jean-Dominique Deuschel and
Ofer Zeitouni On increasing subsequences of I.I.D.\
samples . . . . . . . . . . . . . . . . 247--263
A. V. Kostochka and
V. Rödl and
L. A. Talysheva On Systems of Small Sets with No Large
$\Delta$-Subsystems . . . . . . . . . . 265--268
F. Matú\vs Conditional independences among four
random variables. III. Final conclusion 269--276
Tomasz Schoen On the Density of Universal Sum-Free
Sets . . . . . . . . . . . . . . . . . . 277--280
M. Seysen A Measure for the Non-Orthogonality of a
Lattice Basis . . . . . . . . . . . . . 281--291
R. \vSkrekovski List Improper Colourings of Planar
Graphs . . . . . . . . . . . . . . . . . 293--299
Rudolf Ahlswede and
Ning Cai A Counterexample to Kleitman's
Conjecture Concerning an
Edge-Isoperimetric Problem . . . . . . . 301--305
Sven Erick Alm and
John C. Wierman Inequalities for Means of Restricted
First-Passage Times in Percolation
Theory . . . . . . . . . . . . . . . . . 307--315
Robert P. Dobrow and
James Allen Fill Total Path Length for Random Recursive
Trees . . . . . . . . . . . . . . . . . 317--333
Peter Eichelsbacher and
Ma\lGorzata Roos Compound Poisson Approximation for
Dissociated Random Variables via Stein's
Method . . . . . . . . . . . . . . . . . 335--346
Svante Janson One, Two and Three Times $\log n / n$
for Paths in a Complete Graph with
Random Weights . . . . . . . . . . . . . 347--361
V. Rödl and
A. Ruci\'nski and
A. Taraz Hypergraph Packing and Graph Embedding 363--376
A. Steger and
N. C. Wormald Generating Random Regular Graphs Quickly 377--396
Helmut Alt and
Ulrich Fuchs and
Klaus Kriegel On the Number of Simple Cycles in Planar
Graphs . . . . . . . . . . . . . . . . . 397--405
Richard Arratia and
A. D. Barbour and
Simon Tavaré The Poisson--Dirichlet distribution and
the scale-invariant Poisson process . . 407--416
Claudia Bertram-Kretzberg and
Thomas Hofmeister and
Hanno Lefmann Sparse $0$-$1$ matrices and forbidden
hypergraphs . . . . . . . . . . . . . . 417--427
Isa Cakir and
Ourania Chryssaphinou and
Marianne Månsson On a Conjecture by Eriksson Concerning
Overlap in Strings . . . . . . . . . . . 429--440
S. Guattery and
T. Leighton and
G. L. Miller The Path Resistance Method for Bounding
the Smallest Nontrivial Eigenvalue of a
Laplacian . . . . . . . . . . . . . . . 441--460
Y. O. Hamidoune and
A. S. Lladó and
O. Serra On Sets with a Small Subset Sum . . . . 461--466
A. V. Kostochka and
J. Ne\vset\vril Properties of Descartes' Construction of
Triangle-Free Graphs with High Chromatic
Number . . . . . . . . . . . . . . . . . 467--472
Michael Mitzenmacher Studying Balanced Allocations with
Differential Equations . . . . . . . . . 473--482
Oleg Pikhurko The Minimum Size of Saturated
Hypergraphs . . . . . . . . . . . . . . 483--492
R. \vSkrekovski A Grötzsch-Type Theorem for List
Colourings with Impropriety One . . . . 493--507
Éva Czabarka Intersecting Chains in Finite Vector
Spaces . . . . . . . . . . . . . . . . . 509--528
Tristan Denley and
Talmage James Reid On the Number of Elements in Matroids
with Small Circuits or Cocircuits . . . 529--537
Luis A. Goddyn and
Bill Jackson Removable Circuits in Binary Matroids 539--545
Jochen Harant and
Anja Pruchnewski and
Margit Voigt On Dominating Sets and Independent Sets
of Graphs . . . . . . . . . . . . . . . 547--553
Alan Stacey Searches on a Binary Tree with Random
Edge-Weights . . . . . . . . . . . . . . 555--565
Dudley Stark Total Variation Asymptotics for Refined
Poisson Process Approximations of Random
Logarithmic Assemblies . . . . . . . . . 567--598
Petros Hadjicostas Corrigendum: ``The asymptotic proportion
of subdivisions of a $2\times 2$ table
that result in Simpson's paradox''
[Combin. Probab. Comput. \bf 7 (1998),
no. 4, 387--396; MR1680088 (99m:05008)] 599
Noga Alon and
Benny Sudakov Bipartite Subgraphs and the Smallest
Eigenvalue . . . . . . . . . . . . . . . 1--12
Alexander V. Gnedin A Note on Sequential Selection from
Permutations . . . . . . . . . . . . . . 13--17
Michael Krivelevich The Choice Number of Dense Random Graphs 19--26
David Reimer Proof of the Van den Berg--Kesten
Conjecture . . . . . . . . . . . . . . . 27--32
H. D. Robalewska and
N. C. Wormald Random Star Processes . . . . . . . . . 33--43
C. R. Subramanian Algorithms for Colouring Random
$k$-colourable Graphs . . . . . . . . . 45--77
Van H. Vu On the Choice Number of Random
Hypergraphs . . . . . . . . . . . . . . 79--95
J. K. Dugdale and
A. J. W. Hilton A Sufficient Condition for a Graph to be
the Core of a Class $2$ Graph . . . . . 97--104
Lori Fern and
Gary Gordon and
Jason Leasure and
Sharon Pronchik Matroid Automorphisms and Symmetry
Groups . . . . . . . . . . . . . . . . . 105--123
Oliver Riordan Spanning Subgraphs of Random Graphs . . 125--148
Yoav Seginer The Expected Norm of Random Matrices . . 149--166
David G. Wagner Zeros of Reliability Polynomials and
$f$-vectors of Matroids . . . . . . . . 167--190
David J. Aldous Mixing Time for a Markov Chain on
Cladograms . . . . . . . . . . . . . . . 191--204
Noga Alon and
Miklós Bóna and
Joel Spencer Packing Ferrers Shapes . . . . . . . . . 205--211
Martin Anthony and
Peter L. Bartlett Function Learning from Interpolation . . 213--225
M. A. Fiol and
E. Garriga and
J. L. A. Yebra On Twisted Odd Graphs . . . . . . . . . 227--240
Alan\'nFrieze and
Lei Zhao Optimal Construction of Edge-Disjoint
Paths in Random Regular Graphs . . . . . 241--263
N. N. Kuzjurin Explicit Constructions of Rödl's
Asymptotically Good Packings and
Coverings . . . . . . . . . . . . . . . 265--276
John Mount Fast Unimodular Counting . . . . . . . . 277--285
D. Barraez and
S. Boucheron and
W. Fernandez De La Vega On the Fluctuations of the Giant
Component . . . . . . . . . . . . . . . 287--304
Joseph E. Bonin Involutions of Connected Binary Matroids 305--308
Yair Caro and
Raphael Yuster Dominating a Family of Graphs with Small
Connected Subgraphs . . . . . . . . . . 309--313
Sándor Csörgo and
Wei Biao Wu Random Graphs and the Strong Convergence
of Bootstrap Means . . . . . . . . . . . 315--347
Benjamin Doerr Linear and Hereditary Discrepancy . . . 349--354
Joseph P. S. Kung Critical Exponents, Colines, and
Projective Geometries . . . . . . . . . 355--362
Eunice Gogo Mphako Tutte Polynomials of Perfect Matroid
Designs . . . . . . . . . . . . . . . . 363--367
Jacques Verstraëte On Arithmetic Progressions of Cycle
Lengths in Graphs . . . . . . . . . . . 369--373
M. Voigt Algorithmic Aspects of Partial List
Colourings . . . . . . . . . . . . . . . 375--380
Noga Alon and
János Körner and
Angelo Monti String Quartets in Binary . . . . . . . 381--390
Shai Ben-David and
Leonid Gurvits A Note on VC-Dimension and Measure of
Sets of Reals . . . . . . . . . . . . . 391--405
Joseph E. Bonin and
Talmage James Reid Simple Matroids with Bounded Cocircuit
Size . . . . . . . . . . . . . . . . . . 407--419
Peter Gács The Clairvoyant Demon Has a Hard Task 421--424
Olle Häggström and
Jeffrey E. Steif Propp--Wilson Algorithms and Finitary
Codings for High Noise Markov Random
Fields . . . . . . . . . . . . . . . . . 425--439
Gregory F. Lawler and
Emily E. Puckette The Intersection Exponent for Simple
Random Walk . . . . . . . . . . . . . . 441--464
Jean-Pierre Tillich and
Gilles ZéMor Discrete Isoperimetric Inequalities and
the Probability of a Decoding Error . . 465--479
Noga Alon and
Emanuela Fachini and
János Körner Locally Thin Set Families . . . . . . . 481--488
Josep Díaz and
Mathew D. Penrose and
Jordi Petit and
María Serna Convergence Theorems for Some Layout
Measures on Random Lattice and Random
Geometric Graphs . . . . . . . . . . . . 489--511
Y. O. Hamidoune and
A. S. Lladó and
O. Serra On Restricted Sums . . . . . . . . . . . 513--518
P. Hitczenko and
G. Stengle Expected Number of Distinct Part Sizes
in a Random Integer Composition . . . . 519--527
Marianne Månsson On Compound Poisson Approximation for
Sequence Matching . . . . . . . . . . . 529--548
Oliver Riordan and
Alex Selby The Maximum Degree of a Random Graph . . 549--572
Robin Thomas and
Jan McDonald Thomson Excluding Minors in Nonplanar Graphs of
Girth at Least Five . . . . . . . . . . 573--585
C. Houdré and
P. Tetali Concentration of Measure for Products of
Markov Kernels and Graph Products via
Functional Inequalities . . . . . . . . 1--28
Andreas Nolte and
Rainer Schrader Simulated Annealing and Graph Colouring 29--40
Alan D. Sokal Bounds on the Complex Zeros of
(Di)Chromatic Polynomials and
Potts-Model Partition Functions . . . . 41--77
Van H. Vu A Large Deviation Result on the Number
of Small Subgraphs of a Random Graph . . 79--94
P. N. Balister On the Alspach Conjecture . . . . . . . 95--125
M. A. Fiol Some Spectral Characterizations of
Strongly Distance-Regular Graphs . . . . 127--135
Jeff Kahn and
János Komlós Singularity Probabilities for Random
Matrices over Finite Fields . . . . . . 137--157
Hans Jürgen Prömel and
Angelika Steger and
Anusch Taraz Counting Partial Orders with a Fixed
Number of Comparable Pairs . . . . . . . 159--177
Hongxun Qin Connected Matroids with Symmetric Tutte
Polynomials . . . . . . . . . . . . . . 179--186
Ron\'nAdin and
Yuval Roichman Descent Functions and Random Young
Tableaux . . . . . . . . . . . . . . . . 187--201
Jürgen Bennies and
Jim Pitman Asymptotics of the Hurwitz Binomial
Distribution Related to Mixed Poisson
Galton--Watson Trees . . . . . . . . . . 203--211
Alexander Gnedin and
Sergei Kerov A Characterization of GEM Distributions 213--217
Jeff Kahn An Entropy Approach to the Hard-Core
Model on Bipartite Graphs . . . . . . . 219--237
C. F. Maclean and
Neil O'Connell Random Finite Topologies and their
Thresholds . . . . . . . . . . . . . . . 239--249
Philippe Marchal A Combinatorial Approach to the
Two-Sided Exit Problem for
Left-Continuous Random Walks . . . . . . 251--266
Wang Weifan and
Ko-Wei Lih Structural Properties and Edge
Choosability of Planar Graphs without
6-Cycles . . . . . . . . . . . . . . . . 267--276
János Barát and
Péter Hajnal Operations Which Preserve Path-Width at
Most Two . . . . . . . . . . . . . . . . 277--291
Ourania Chryssaphinou and
Stavros Papastavridis and
Eutichia Vaggelatou Poisson Approximation for the
Non-Overlapping Appearances of Several
Words in Markov Chains . . . . . . . . . 293--308
Emanuela Fachini and
János Körner and
Angelo Monti Self-Similarity Bounds for Locally Thin
Set Families . . . . . . . . . . . . . . 309--315
H. L. Fu and
C. A. Rodger $4$-Cycle Group-Divisible Designs with
Two Associate Classes . . . . . . . . . 317--343
P. E. Haxell A Note on Vertex List Colouring . . . . 345--347
Bráulio Maia and
Manoel Lemos Matroids Having Small Circumference . . 349--360
V. Nikiforov On the Minimum Number of $k$-Cliques in
Graphs with Restricted Independence
Number . . . . . . . . . . . . . . . . . 361--366
Tom Bohman and
Alan Frieze and
Miklós Ruszinkó and
Lubo\vs Thoma $G$-Intersecting Families . . . . . . . 367--384
S. Boucheron and
W. Fernandez de la Vega On the Independence Number of Random
Interval Graphs . . . . . . . . . . . . 385--396
János Komlós and
Gábor N. Sárkózy and
Endre Szemerédi Spanning Trees in Dense Graphs . . . . . 397--416
R. E. Lillo and\'nMartin Characterization Results Based on a
Functional Derivative Approach . . . . . 417--434
Oleg Pikhurko Weakly Saturated Hypergraphs and
Exterior Algebra . . . . . . . . . . . . 435--451
Talmage James Reid and
Haidong Wu On Minimally $3$-Connected Binary
Matroids . . . . . . . . . . . . . . . . 453--461
Paul Balister Packing Circuits into $K_N$ . . . . . . 463--499
Emanuela Fachini and
János Körner A Note on Counting Very Different
Sequences . . . . . . . . . . . . . . . 501--504
Jan Van Den Heuvel Algorithmic Aspects of a Chip-Firing
Game . . . . . . . . . . . . . . . . . . 505--529
Stefan T. Mecay Maximum-Sized Matroids with No Minors
Isomorphic to $U_{2,5}$, $F_7$, $F^-_7$
or $P_7$ . . . . . . . . . . . . . . . . 531--542
V. Nikiforov On the Edge Distribution of a Graph . . 543--555
Tibor Szabó and
Gábor Tardos A Multidimensional Generalization of the
Erd\Hos--Szekeres Lemma on Monotone
Subsequences . . . . . . . . . . . . . . 557--565
Noga Alon and
Bojan Mohar The Chromatic Number of Graph Powers . . 1--10
V. S. Borkar On the Lock-in Probability of Stochastic
Approximation . . . . . . . . . . . . . 11--20
Leslie Ann Goldberg and
Mark Jerrum The `Burnside Process' Converges Slowly 21--34
André E. Kézdy and
Hunter S. Snevily Distinct Sums Modulo $n$ and Tree
Embeddings . . . . . . . . . . . . . . . 35--42
Orlando Lee and
Yoshiko Wakabayashi On the Circuit Cover Problem for Mixed
Graphs . . . . . . . . . . . . . . . . . 43--59
E. Manstavicius Mappings on Decomposable Combinatorial
Structures: Analytic Approach . . . . . 61--78
Dudley Stark and
A. Ganesh and
Neil O'Connell Information Loss in Riffle Shuffling . . 79--95
Jacques Verstraëte A Note on Vertex-Disjoint Cycles . . . . 97--102
Van H. Vu A General Upper Bound on the List
Chromatic Number of Locally Sparse
Graphs . . . . . . . . . . . . . . . . . 103--111
S. Boucheron and
W. Fernandez de la Vega On a Square Packing Problem . . . . . . 113--127
Colin Cooper and
Alan Frieze Multi-Coloured Hamilton Cycles in Random
Edge-Coloured Graphs . . . . . . . . . . 129--133
Martin Dyer and
Leslie Ann Goldberg and
Catherine Greenhill and
Gabriel Istrate and
Mark Jerrum Convergence of the Iterated Prisoner's
Dilemma Game . . . . . . . . . . . . . . 135--147
Grzegorz Kubicki and
Jeno Lehel and
Michal Morayne A Ratio Inequality for Binary Trees and
the Best Secretary . . . . . . . . . . . 149--161
Colin McDiarmid Concentration for Independent
Permutations . . . . . . . . . . . . . . 163--178
V. Nikiforov Some Inequalities for the Largest
Eigenvalue of a Graph . . . . . . . . . 179--189
Bogdan Oporowski Partitioning Matroids with Only Small
Cocircuits . . . . . . . . . . . . . . . 191--197
J.\'nTalbot Lagrangians of Hypergraphs . . . . . . . 199--216
Sven Erick Alm and
Gregory B. Sorkin Exact Expectations and Distributions for
the Random Assignment Problem . . . . . 217--248
Colin Cooper and
Alan Frieze and
Bruce Reed Random Regular Graphs of Non-Constant
Degree: Connectivity and Hamiltonicity 249--261
Edward Dobson Packing Trees into the Complete Graph 263--272
Catherine Greenhill and
Svante Janson and
Jeong Han Kim and
Nicholas C. Wormald Permutation Pseudographs and Contiguity 273--298
Dhruv Mubayi Some Exact Results and New Asymptotics
for Hypergraph Turán Numbers . . . . . . 299--309
Gary K. Schwartz On the Automorphism Groups of Dowling
Geometries . . . . . . . . . . . . . . . 311--321
Colin Cooper and
Alan Frieze and
Bruce Reed and
Oliver Riordan Random Regular Graphs of Non-Constant
Degree: Independence and Chromatic
Number . . . . . . . . . . . . . . . . . 323--341
Edward Dobson Constructing Trees in Graphs whose
Complement has no $K_{2,s}$ . . . . . . 343--347
Klaus Dohmen Bonferroni-Type Inequalities via Chordal
Graphs . . . . . . . . . . . . . . . . . 349--351
Hsien-Kuei Hwang and
Tsung-Hsi Tsai Quickselect and the Dickman Function . . 353--371
Brendan D. McKay and
Ian\'n Wanless and
Nicholas C. Wormald Asymptotic Enumeration of Graphs with a
Given Upper Bound on the Maximum Degree 373--392
Marianne Månsson Pattern Avoidance and Overlap in Strings 393--402
James Oxley and
Dominic Welsh Chromatic, Flow and Reliability
Polynomials: The Complexity of their
Coefficients . . . . . . . . . . . . . . 403--426
András Telcs A Note on Rough Isometry Invariance of
Resistance . . . . . . . . . . . . . . . 427--432
Sven Erick Alm and
Robert Parviainen Lower and Upper Bounds for the Time
Constant of First-Passage Percolation 433--445
Robert Beals and
Charles R. Leedham-Green and
Alice C. Niemeyer and
Cheryl E. Praeger and
Ákos Seress Permutations with Restricted Cycle
Structure and an Algorithmic Application 447--464
Michael Krivelevich and
Benny Sudakov and
Van H. Vu A Sharp Threshold for Network
Reliability . . . . . . . . . . . . . . 465--474
Samuel Kutin Constructing Large Set Systems with
Given Intersection Sizes Modulo
Composite Numbers . . . . . . . . . . . 475--486
Elchanan Mossel The Minesweeper Game: Percolation and
Complexity . . . . . . . . . . . . . . . 487--499
Jim Pitman Poisson--Dirichlet and GEM Invariant
Distributions for Split-and-Merge
Transformations of an Interval
Partition2 . . . . . . . . . . . . . . . 501--514
Daniel C. Slilaty Matroid Duality from Topological Duality
in Surfaces of Nonnegative Euler
Characteristic . . . . . . . . . . . . . 515--528
Wolfgang Stadje The Residues modulo $m$ of Products of
Random Integers . . . . . . . . . . . . 529--540
Patrick Bellenbaum and
Reinhard Diestel Two Short Proofs Concerning
Tree-Decompositions . . . . . . . . . . 541--547
S. Jukna and
G. Schnitger Triangle-Freeness is Hard to Detect . . 549--569
Joseph Samuel Myers Graphs without Large Complete Minors are
Quasi-Random . . . . . . . . . . . . . . 571--585
Ralph Neininger The Wiener Index of Random Trees . . . . 587--597
C.\'nReidys Distances in Random Induced Subgraphs of
Generalized $n$-Cubes . . . . . . . . . 599--605
Dudley Stark Information Loss in Top to Random
Shuffling . . . . . . . . . . . . . . . 607--627
John C. Wierman An Improved Upper Bound for the
Hexagonal Lattice Site Percolation
Critical Probability . . . . . . . . . . 629--643
Paul Balister Packing Digraphs with Directed Closed
Trails . . . . . . . . . . . . . . . . . 1--15
M. A. Fiol A General Spectral Bound for Distant
Vertex Subsets . . . . . . . . . . . . . 17--26
Svante Janson Cycles and Unicyclic Components in
Random Graphs . . . . . . . . . . . . . 27--52
A. V. Kostochka and
K. Nakprasit Equitable Colourings of $d$-degenerate
Graphs . . . . . . . . . . . . . . . . . 53--60
Michael Krivelevich and
Benny Sudakov The Largest Eigenvalue of Sparse Random
Graphs . . . . . . . . . . . . . . . . . 61--72
Sven Rahmann and
Eric Rivals On the Distribution of the Number of
Missing Words in Random Texts . . . . . 73--87
David Reimer An Average Set Size Theorem . . . . . . 89--93
John C. Wierman Upper and Lower Bounds for the Kagomé
Lattice Bond Percolation Critical
Probability . . . . . . . . . . . . . . 95--111
Nadia Creignou and
Hervé Daudé and
Olivier Dubois Approximating the satisfiability
threshold for random $k$-XOR-formulas 113--126
Ben Green Some Constructions in the Inverse
Spectral Theory of Cyclic Groups . . . . 127--138
Peter Keevash and
Benny Sudakov Local Density in Graphs with Forbidden
Subgraphs . . . . . . . . . . . . . . . 139--153
Yoshiharu Kohayakawa and
Brendan Nagle and
Vojt\vech Rödl Hereditary Properties of Triple Systems 155--189
Micha Sharir The Clarkson--Shor technique revisited
and extended . . . . . . . . . . . . . . 191--201
Elmar Teufl The average displacement of the simple
random walk on the Sierpi\'nski graph 203--222
Anonymous The Oberwolfach Meeting on
Combinatorics, Probability and Computing 223--223
Micah Adler and
Harald Räcke and
Naveen Sivadasan and
Christian Sohler and
Berthold Vöcking Randomized Pursuit-Evasion in Graphs . . 225--244
Andreas Goerdt and
Tomasz Jurdzi\'nski Some results on random unsatisfiable
$k$-SAT instances and approximation
algorithms applied to random structures 245--267
Catherine Greenhill and
Andrzej Ruci\'nski and
Nicholas C. Wormald Connectedness of the Degree Bounded Star
Process . . . . . . . . . . . . . . . . 269--283
Matthias Krause and
Hans Ulrich Simon Determining the Optimal Contrast for
Secret Sharing Schemes in Visual
Cryptography . . . . . . . . . . . . . . 285--299
Peter Sanders and
Berthold Vöcking Tail Bounds and Expectations for Random
Arc Allocation and Applications . . . . 301--318
Miklós Simonovits and
Vera T. Sós Hereditary Extended Properties,
Quasi-Random Graphs and Induced
Subgraphs . . . . . . . . . . . . . . . 319--344
Alan Stacey Branching Random Walks on
Quasi-Transitive Graphs . . . . . . . . 345--358
Mieczys\law Borowiecki and
Jaros\law Grytczuk and
Mariusz Ha\luszczak and
Zsolt Tuza Schütte's Tournament Problem and
Intersecting Families of Sets . . . . . 359--364
Benjamin Doerr and
Anand Srivastav Multicolour Discrepancies . . . . . . . 365--399
Henrik Eriksson and
Kimmo Eriksson and
Jonas Sjöstrand Exact Expectations for Random Graphs and
Assignments . . . . . . . . . . . . . . 401--412
Yahya Ould Hamidoune Subsequence Sums . . . . . . . . . . . . 413--425
Ji\vrí Matou\vsek A Lower Bound on the Size of Lipschitz
Subsets in Dimension $3$ . . . . . . . . 427--430
Cyril Roberto A Path Method for the Logarithmic
Sobolev Constant . . . . . . . . . . . . 431--455
Haidong Wu Contractible Elements in Graphs and
Matroids . . . . . . . . . . . . . . . . 457--465
Béla Bollobás and
Andrew Thomason Frank Ramsey . . . . . . . . . . . . . . 469--475
Noga Alon and
Michael Krivelevich and
Benny Sudakov Turán numbers of bipartite graphs and
related Ramsey-type questions . . . . . 477--494
Maria Axenovich and
Tao Jiang and
Zsolt Tuza Local anti-Ramsey numbers of graphs . . 495--511
Tom C. Brown On the canonical version of a theorem in
Ramsey theory . . . . . . . . . . . . . 513--514
Ehud Friedgut and
Yoshiharu Kohayakawa and
Vojt\vech Rödl and
Andrzej Ruci\'nski and
Prasad Tetali Ramsey games against a one-armed bandit 515--545
Hillel Furstenberg and
Benjamin Weiss Markov processes and Ramsey theory for
trees . . . . . . . . . . . . . . . . . 547--563
Vince Grolmusz A note on explicit Ramsey graphs and
modular sieves . . . . . . . . . . . . . 565--569
Neil Hindman and
Imre Leader and
Dona Strauss Open problems in partition regularity 571--583
Tao Jiang and
Douglas B. West On the Erd\Hos--Simonovits--Sós
conjecture about the anti-Ramsey number
of a cycle . . . . . . . . . . . . . . . 585--598
Veselin Jungi\'c and
Jacob Licht and
Mohammad Mahdian and
Jaroslav Ne\vset\vril and
Rado\vs Radoi\vci\'c Rainbow arithmetic progressions and
anti-Ramsey results . . . . . . . . . . 599--620
Péter Komjáth and
Saharon Shelah A partition theorem for scattered order
types . . . . . . . . . . . . . . . . . 621--626
Alexandr Kostochka and
Benny Sudakov On Ramsey numbers of sparse graphs . . . 627--641
Randall McCutcheon A Sárközy theorem for finite fields . . . 643--651
C. C. Rousseau and
S. E. Speed Mixed Ramsey numbers revisited . . . . . 653--660
Pavel Pudlák An application of Hindman's theorem to a
problem on communication complexity . . 661--670
N. W. Sauer Canonical vertex partitions . . . . . . 671--704
Magnus Bordewich Approximating the Number of Acyclic
Orientations for a Class of Sparse
Graphs . . . . . . . . . . . . . . . . . 1--16
Ehud Friedgut Influences in Product Spaces: KKL and
BKKKL Revisited . . . . . . . . . . . . 17--29
Hans Garmo and
Svante Janson and
Michal Karonski On Generalized Random Railways . . . . . 31--35
André E. Kézdy and
Hunter S. Snevily Polynomials that Vanish on Distinct
$n$th Roots of Unity . . . . . . . . . . 37--59
Yoshiharu Kohayakawa and
Vojtech Rödl and
Mathias Schacht The Turán Theorem for Random Graphs . . . 61--91
Daniela Kühn and
Deryk Osthus Large Topological Cliques in Graphs
Without a $4$-Cycle . . . . . . . . . . 93--102
Robert Parviainen Random Assignment with Integer Costs . . 103--113
Béla Bollobás How Sharp is the Concentration of the
Chromatic Number? . . . . . . . . . . . 115--117
Imre Leader Book Review: ``Extremal Combinatorics:
with Applications in Computer Science''
by Stasys Jukna, Springer, 2001, xvii +
375 pp. \pounds 32.50; \$49.95, ISBN
3-540-66313-4} . . . . . . . . . . . . . 119--121
Alexander Scott Book Review: ``Topics in Graph
Automorphisms and Reconstruction'' by
Josef Lauri and Raffaele Scapellato,
Cambridge University Press, 2003, 172
pp. \pounds 47.50; \$65.00 hardback,
\pounds 16.95; \$23.00, paperback, ISBN
0-521-82151-7 (hardback), 0-521-52903-4
(paperback) . . . . . . . . . . . . . . 121--122
Anders Dessmark and
Andrzej Pelc Distributed Colouring and Communication
in Rings with Local Knowledge . . . . . 123--136
David Galvin and
Jeff Kahn On Phase Transition in the Hard-Core
Model on ${\mathbb Z}^d$ . . . . . . . . 137--164
Stefanie Gerke and
Colin McDiarmid On the Number of Edges in Random Planar
Graphs . . . . . . . . . . . . . . . . . 165--183
Alexander V. Gnedin Three Sampling Formulas . . . . . . . . 185--193
J. Robert Johnson A Disproof of the Fon-der-Flaass
Conjecture . . . . . . . . . . . . . . . 195--201
Micha Sharir and
Emo Welzl Point--Line Incidences in Space . . . . 203--220
Alan D. Sokal Chromatic Roots are Dense in the Whole
Complex Plane . . . . . . . . . . . . . 221--261
J. Solymosi A Note on a Question of Erd\Hos and
Graham . . . . . . . . . . . . . . . . . 263--267
Lorenzo Traldi A Subset Expansion of the Coloured Tutte
Polynomial . . . . . . . . . . . . . . . 269--275
Béla Bollobás and
Imre Leader Isoperimetric Problems for $r$-sets . . 277--279
Imre Bárány Book Review: ``Using the Borsuk--Ulam
Theorem: Lectures on Topological Methods
in Combinatorics and Geometry,'' by J
Matou\vsek, Springer, 2003, 196 pp.,
\pounds 30.50, \$49.95, \euro 49.95} . . 281--282
Boris Aronov and
János Pach and
Micha Sharir and
Gábor Tardos Distinct Distances in Three and Higher
Dimensions . . . . . . . . . . . . . . . 283--293
Geoffrey Atkinson and
Alan Frieze On the $b$-Independence Number of Sparse
Random Graphs . . . . . . . . . . . . . 295--309
Paul N. Balister and
Ervin Györi and
Jenö Lehel and
Richard H. Schelp Longest Paths in Circular Arc Graphs . . 311--317
Colin Cooper and
Alan Frieze The Size of the Largest Strongly
Connected Component of a Random Digraph
with a Given Degree Sequence . . . . . . 319--337
Steven N. Evans Embedding a Markov Chain into a Random
Walk on a Permutation Group . . . . . . 339--351
Don Hush and
Clint Scovel Fat-Shattering of Affine Functions . . . 353--360
Daniela Kühn and
Deryk Osthus Subdivisions of ${K}_{r+2}$ in Graphs of
Average Degree at Least $r +
\varepsilon$ and Large but Constant
Girth . . . . . . . . . . . . . . . . . 361--371
Gregory L. McColm Threshold Functions for Random Graphs on
a Line Segment . . . . . . . . . . . . . 373--387
Shakhar Smorodinsky and
Micha Sharir Selecting Points that are Heavily
Covered by Pseudo-Circles, Spheres or
Rectangles . . . . . . . . . . . . . . . 389--411
Andrew Thomason Two Minor Problems . . . . . . . . . . . 413--414
Michael Drmota and
Wojciech Szpankowski Special Issue on Analysis of Algorithms 415--417
Laurent Alonso and
Philippe Chassaing and
Florent Gillet and
Svante Janson and
Edward M. Reingold and
René Schott Quicksort with Unreliable Comparisons: A
Probabilistic Analysis . . . . . . . . . 419--449
B. Bollobás and
A. D. Scott Max Cut for Random Graphs with a Planted
Partition . . . . . . . . . . . . . . . 451--474
B. Chauvin and
P. Flajolet and
D. Gardy and
B. Gittenberger And/Or Trees Revisited . . . . . . . . . 475--497
Benoît Daireaux and
Brigitte Vallée Dynamical Analysis of the Parametrized
Lehmer--Euclid Algorithm . . . . . . . . 499--536
Olivier Dubois and
Guy Louchard and
Jacques Mandler Additive Decompositions, Random
Allocations, and Threshold Phenomena . . 537--575
Philippe Duchon and
Philippe Flajolet and
Guy Louchard and
Gilles Schaeffer Boltzmann Samplers for the Random
Generation of Combinatorial Structures 577--625
Predrag R. Jelenkovic and
Ana Radovanovic Optimizing LRU Caching for Variable
Document Sizes . . . . . . . . . . . . . 627--643
O. Milenkovic and
K. J. Compton Probabilistic Transforms for
Combinatorial Urn Models . . . . . . . . 645--675
Kate Morris and
Alois Panholzer and
Helmut Prodinger On Some Parameters in Heap Ordered Trees 677--696
Michel Nguyen The Area and Inertial Moment of Dyck Paths 697--716
Alois Panholzer Distribution of the Steiner Distance in
Generalized $M$-ary Search Trees . . . . 717--733
Robin Pemantle and
Mark C. Wilson Asymptotics of Multivariate Sequences
II: Multiple Points of the Singular
Variety . . . . . . . . . . . . . . . . 735--761
Werner Schachinger Concentration of Size and Path Length of
Tries . . . . . . . . . . . . . . . . . 763--793
Noga Alon and
Uri Stav New Bounds on Parent-Identifying Codes:
The Case of Multiple Parents . . . . . . 795--807
F.\'nDong and
K.\'nKoh Two Results on Real Zeros of Chromatic
Polynomials . . . . . . . . . . . . . . 809--813
Peter Gács Compatible Sequences and a Slow Winkler
Percolation . . . . . . . . . . . . . . 815--856
P. E. Haxell On the Strong Chromatic Number . . . . . 857--865
Luke Pebody The Reconstructibility of Finite Abelian
Groups . . . . . . . . . . . . . . . . . 867--892
Raphael Yuster Families of Trees Decompose the Random
Graph in an Arbitrary Way . . . . . . . 893--910
Yonatan Bilu and
Nathan Linial Ramanujan Signing of Regular Graphs . . 911--912
Anton Bovier Book Review: ``Spin Glasses: A Challenge
for Mathematicians -- Cavity and Mean
Field Models'', by Michel Talagrand,
Springer, 2003, 586 pp., \euro
139.05/\$159.00} . . . . . . . . . . . . 913--915
Lars Holst Book Review: ``Logarithmic Combinatorial
Structures: A Probabilistic Approach'',
by Richard Arratia, A. D. Barbour and
Simon Tavaré, European Mathematical
Society Monographs in Mathematics, 2003,
375 pp., \euro 69 . . . . . . . . . . . 916--917
Hans Jürgen Prömel Special Issue in Memory of Walter Deuber 1--1
Hans Jürgen Prömel Complete Disorder is Impossible: The
Mathematical Work of Walter Deuber . . . 3--16
Martin Aigner The $k$-Equal Problem . . . . . . . . . 17--24
Jens-P. Bode and
Hans-Dietrich O. F. Gronau and
Heiko Harborth Some Ramsey Schur Numbers . . . . . . . 25--30
Michel Deza and
Mathieu Dutour Zigzag Structures of Simple Two-Faced
Polyhedra . . . . . . . . . . . . . . . 31--57
Reinhard Diestel The Cycle Space of an Infinite Graph . . 59--79
Gábor Elek and
Vera T. Sós Paradoxical Decompositions and Growth
Conditions . . . . . . . . . . . . . . . 81--105
M. Ferrara and
Y. Kohayakawa and
V. Rödl Distance Graphs on the Integers . . . . 107--131
Matthias Kriesell Triangle Density and Contractibility . . 133--146
Hanno Lefmann Sparse Parity-Check Matrices over
$GF(q)$ . . . . . . . . . . . . . . . . 147--169
Jaroslav Ne\vsetril Ramsey Classes and Homogeneous
Structures . . . . . . . . . . . . . . . 171--189
Jens Schlaghoff and
Eberhard Triesch Improved Results for Competitive Group
Testing . . . . . . . . . . . . . . . . 191--202
E. Specker Modular Counting and Substitution of
Structures . . . . . . . . . . . . . . . 203--210
Angelika Steger On the Evolution of Triangle-Free Graphs 211--224
Ingo Wegener and
Carsten Witt On the Optimization of Monotone
Polynomials by Simple Randomized Search
Heuristics . . . . . . . . . . . . . . . 225--247
M. Bloznelis Orthogonal Decomposition of Symmetric
Functions Defined on Random Permutations 249--268
Onn Chan and
T. K. Lam Lifting Markov Chains to Random Walks on
Groups . . . . . . . . . . . . . . . . . 269--273
Keith Edwards Detachments of Complete Graphs . . . . . 275--310
Peter L. Hammer and
Igor E. Zverovich Construction of a Maximum Stable Set
with $k$-Extensions . . . . . . . . . . 311--318
Norbert Hegyvári On Intersecting Properties of Partitions
of Integers . . . . . . . . . . . . . . 319--323
Daniela Kühn and
Deryk Osthus Packings in Dense Regular Graphs . . . . 325--337
Tamás F. Móri The Maximum Degree of the
Barabási--Albert Random Tree . . . . . . 339--348
V. Nikiforov The Cycle-Complete Graph Ramsey Numbers 349--370
Y. Peng and
V. Rödl and
J. Skokan Counting Small Cliques in $3$-uniform
Hypergraphs . . . . . . . . . . . . . . 371--413
Wolfgang Woess Lamplighters, Diestel--Leader Graphs,
Random Walks, and Harmonic Functions . . 415--433
Zoltán Füredi and
András Gyárfás and
Gábor Simonyi Connected matchings and Hadwiger's
conjecture . . . . . . . . . . . . . . . 435--438
Amin Coja-Oghlan The Lovász Number of Random Graphs . . . 439--465
Zoltán Füredi and
Miklós Simonovits Triple Systems Not Containing a Fano
Configuration . . . . . . . . . . . . . 467--484
Y. O. Hamidoune and
D. Quiroz On Subsequence Weighted Products . . . . 485--489
Russell Lyons Asymptotic Enumeration of Spanning Trees 491--522
Neal Madras and
C. Chris Wu Self-Avoiding Walks on Hyperbolic Graphs 523--548
William D. May and
John C. Wierman Using Symmetry to Improve Percolation
Threshold Bounds . . . . . . . . . . . . 549--566
Dillon Mayhew Inequivalent Representations of Bias
Matroids . . . . . . . . . . . . . . . . 567--583
V. Rödl and
L. Thoma On Cover Graphs and Dependent Arcs in
Acyclic Orientations . . . . . . . . . . 585--617
Jeffrey E. Steif Book Review: ``Probability on Discrete
Structures'', edited by H. Kesten,
Encyclopaedia of Mathematical Sciences,
Vol. 110, Springer 2004, 351 pp., ISBN
3-540-00845-4, \euro 94.95/\pounds
73.00/\$109.00} . . . . . . . . . . . . 619--623
Peter McMullen Book Review: ``Convex Polytopes'', by
Branko Grünbaum, second edition (first
edition (1967) written with the
cooperation of V. L. Klee,\'nPerles and
G. C. Shephard; second edition (2003)
prepared by V. Kaibel, V. L. Klee and
G.\'nZiegler), Graduate Texts in
Mathematics, Vol. 221, Springer 2003,
568 pp., \pounds 61.50/\euro
85.55/\$79.97} . . . . . . . . . . . . . 623--626
Noga Alon and
Michael Krivelevich and
Benny Sudakov MaxCut in \boldmath ${H}$-Free Graphs 629--647
József Beck Positional Games . . . . . . . . . . . . 649--696
N. Berger and
C. Borgs and
J. T. Chayes and
R. M. D'Souza and
R. D. Kleinberg Degree Distribution of
Competition-Induced Preferential
Attachment Graphs . . . . . . . . . . . 697--721
Béla Bollobás and
Alexandr Kostochka and
Kittikorn Nakprasit On Two Conjectures on Packing of Graphs 723--736
M. Bordewich and
M. Freedman and
L. Lovász and
D. Welsh Approximate Counting and Quantum
Computation . . . . . . . . . . . . . . 737--754
Fan Chung A Spectral Turán Theorem . . . . . . . . 755--767
Ehud Friedgut and
Jeff Kahn On the Number of Hamiltonian Cycles in a
Tournament . . . . . . . . . . . . . . . 769--781
Alan Frieze and
Michael Krivelevich and
Oleg Pikhurko and
Tibor Szabó The Game of JumbleG . . . . . . . . . . 783--793
Zoltán Füredi and
Oleg Pikhurko and
Miklós Simonovits On Triple Systems with Independent
Neighbourhoods . . . . . . . . . . . . . 795--813
Svante Janson The First Eigenvalue of Random Graphs 815--828
B. Klartag and
V. Milman Rapid Steiner Symmetrization of Most of
a Convex Body and the Slicing Problem 829--843
Assaf Naor and
Jacques Verstraëte A Note on Bipartite Graphs Without
$2^k$-Cycles . . . . . . . . . . . . . . 845--849
V. Nikiforov and
C. C. Rousseau and
R. H. Schelp Book Ramsey Numbers and Quasi-Randomness 851--860
Patrice Ossona de Mendez and
Pierre Rosenstiehl Homomorphism and Dimension . . . . . . . 861--872
Boris Pittel On Dimensions of a Random Solid Diagram 873--895
Oliver Riordan The Small Giant Component in Scale-Free
Random Graphs . . . . . . . . . . . . . 897--938
N. Alon and
Y. Kohayakawa and
C. Mauduit and
C. G. Moreira and
V. Rödl Measures of Pseudorandomness for Finite
Sequences: Minimal Values . . . . . . . 1--29
Richard Arratia and
A. D. Barbour and
Simon Tavaré A Tale of Three Couplings:
Poisson--Dirichlet and GEM
Approximations for Random Permutations 31--62
Christian Borgs Absence of Zeros for the Chromatic
Polynomial on Bounded Degree Graphs . . 63--74
Henning Bruhn and
Reinhard Diestel Duality in Infinite Graphs . . . . . . . 75--90
Peter J. Cameron and
Jaroslav Ne\vSEtril Homomorphism-Homogeneous Relational
Structures . . . . . . . . . . . . . . . 91--103
Edward Dobson Automorphism Groups of Metacirculant
Graphs of Order a Product of Two
Distinct Primes . . . . . . . . . . . . 105--130
Zoltán Füredi and
Gyula O. H. Katona $2$-Bases of Quadruples . . . . . . . . 131--141
W. T. Gowers Quasirandomness, Counting and Regularity
for 3-Uniform Hypergraphs . . . . . . . 143--184
Ervin Gyori Triangle-Free Hypergraphs . . . . . . . 185--191
Penny Haxell and
Tibor Szabó Odd Independent Transversals are Odd . . 193--211
Ayman Khalfalah and
Endre Szemerédi On the Number of Monochromatic Solutions
of boldmath $x + y= z^2$ . . . . . . . . 213--227
Vojtech Rödl and
Andrzej Rucinski and
Endre Szemerédi A Dirac-Type Theorem for $3$-Uniform
Hypergraphs . . . . . . . . . . . . . . 229--251
Alexander D. Scott and
Alan D. Sokal On Dependency Graphs and the Lattice Gas 253--279
Alexander D. Scott and
Gregory B. Sorkin Solving Sparse Random Instances of Max
Cut and Max $2$-CSP in Linear Expected
Time . . . . . . . . . . . . . . . . . . 281--315
Alon Amit and
Nathan Linial Random Lifts of Graphs: Edge Expansion 317--332
Manuel Bodirsky and
Mihyun Kang Generating Outerplanar Graphs Uniformly
at Random . . . . . . . . . . . . . . . 333--343
Maria Deijfen and
Olle Häggström The Initial Configuration is Irrelevant
for the Possibility of Mutual Unbounded
Growth in the Two-Type Richardson Model 345--353
Guoli Ding and
Jinko Kanno Splitter Theorems for Cubic Graphs . . . 355--375
G. E. Farr The Complexity of Counting Colourings of
Subgraphs of the Grid . . . . . . . . . 377--383
Omer Giménez and
Marc Noy On the Complexity of Computing the Tutte
Polynomial of Bicircular Matroids . . . 385--395
Petr Hlinený The Tutte Polynomial for Matroids of
Bounded Branch-Width . . . . . . . . . . 397--409
Russell Martin and
Dana Randall Disjoint Decomposition of Markov Chains
and Sampling Circuits in Cayley Graphs 411--448
S. D. Noble Evaluating the Rank Generating Function
of a Graphic $2$-Polymatroid . . . . . . 449--461
Thomas Voigt and
Günter\'n Ziegler Singular $0$/$1$-Matrices, and the
Hyperplanes Spanned by Random
$0$/$1$-Vectors . . . . . . . . . . . . 463--471
Jirí Matou\vsek and
Ale\vs Prívetivý The Minimum Independence Number of a
Hasse Diagram . . . . . . . . . . . . . 473--475
Sven Erick Alm On Measures of Average Degree for
Lattices . . . . . . . . . . . . . . . . 477--488
Tom Bohman and
David Kravitz Creating a Giant Component . . . . . . . 489--511
W. Duckworth and
N. C. Wormald On the Independent Domination Number of
Random Regular Graphs . . . . . . . . . 513--522
Luis Goddyn and
Petr Hlinený and
Winfried Hochstättler Balanced Signings and the Chromatic
Number of Oriented Matroids . . . . . . 523--539
R. Kannan and
L. Lovász and
R. Montenegro Blocking Conductance and Mixing in
Random Walks . . . . . . . . . . . . . . 541--570
Christopher Malon and
Igor Pak Percolation on Finite Cayley Graphs . . 571--588
Serban Nacu Increments of Random Partitions . . . . 589--595
József Solymosi Arithmetic Progressions in Sets with
Small Sumsets . . . . . . . . . . . . . 597--603
Donald K. Wagner Weakly $3$-Connected Graphs . . . . . . 605--617
Peter Wagner An Upper Bound for Constrained Ramsey
Numbers . . . . . . . . . . . . . . . . 619--626
Aart Blokhuis Jaeger's Conjecture . . . . . . . . . . 627--629
Edward Odell Book Review: ``Ramsey Methods in
Analysis'', by Spiros A. Argyros and
Stevo Todorcevic, Birkhäuser 2005,
257pp.,\pounds 29.00/\$49.95/38 Euros} 631--636
Colin Cooper Distribution of Vertex Degree in
Web-Graphs . . . . . . . . . . . . . . . 637--661
Idris David Mercer Autocorrelations of Random Binary
Sequences . . . . . . . . . . . . . . . 663--671
Itai Benjamini and
Gady Kozma and
László Lovász and
Dan Romik and
Gábor Tardos Waiting for a Bat to Fly By (in
Polynomial Time) . . . . . . . . . . . . 673--683
Ken-Ichi Kawarabayashi and
Alexandr Kostochka and
Gexin Yu On Sufficient Degree Conditions for a
Graph to be $k$-linked . . . . . . . . . 685--694
Remco Van Der Hofstad and
Gordon Slade Expansion in \boldmath $n^{-1}$ for
Percolation Critical Values on the
$n$-cube and \boldmath $\mathbb{Z}^n$:
the First Three Terms . . . . . . . . . 695--713
József Balogh and
Yuval Peres and
Gábor Pete Bootstrap Percolation on Infinite Trees
and Non-Amenable Groups . . . . . . . . 715--730
Amin Coja-Oghlan Finding Large Independent Sets in
Polynomial Expected Time . . . . . . . . 731--751
W. Paulsen Best Odds for Finding a Perfect Matching
in a Bipartite Graph . . . . . . . . . . 753--763
Youngbin Choe and
David G. Wagner Rayleigh Matroids . . . . . . . . . . . 765--781
Noga Alon Feasible Schedules for Rotating
Transmissions . . . . . . . . . . . . . 783--787
Bruce C. Berndt Book Review: ``Integer Partitions'', by
George E. Andrews and Kimmo Eriksson,
Cambridge University Press 2004, 152pp.,
\pounds 15.99/\$24.99 (paperback);
\pounds 40.00/\$70.00 (hardback) . . . . 789--790
Noga Alon and
Asaf Shapira A Characterization of Easily Testable
Induced Subgraphs . . . . . . . . . . . 791--805
M. Beiglböck A Multidimensional Central Sets Theorem 807--814
Joshua N. Cooper and
Joel Spencer Simulating a Random Walk with Constant
Error . . . . . . . . . . . . . . . . . 815--822
Gianluca De Marco and
Andrzej Pelc Randomized Algorithms for Determining
the Majority on Graphs . . . . . . . . . 823--834
Joanna A. Ellis-Monaghan and
Lorenzo Traldi Parametrized Tutte Polynomials of Graphs
and Matroids . . . . . . . . . . . . . . 835--854
S. Jukna On Graph Complexity . . . . . . . . . . 855--876
Bojan Mohar and
Andrej Vodopivec On Polyhedral Embeddings of Cubic Graphs 877--893
V. Nikiforov Edge Distribution of Graphs with Few
Copies of a Given Graph . . . . . . . . 895--902
Remco Van Der Hofstad and
Gerard Hooghiemstra and
Piet Van Mieghem Size and Weight of Shortest Path Trees
with Exponential Link Weights . . . . . 903--926
Paul Wollan Extremal Functions for Shortening Sets
of Paths . . . . . . . . . . . . . . . . 927--932
Noga Alon Splitting digraphs . . . . . . . . . . . 933--937
Bojan Mohar Book Review: ``Graphs on Surfaces and
Their Applications'', by Sergei K. Lando
and Alexander K. Zvonkin, Encyclopaedia
of Mathematical Sciences 141,
Springer-Verlag, 2004, 455pp., \pounds
73.00/\$109.00/94.95 Euros} . . . . . . 939--941
Imre Bárány Book Review: ``Geometric Graphs and
Arrangements: Some Chapters from
Combinatorial Geometry'', by Stefan
Felsner, Vieweg Verlag, 2004, 170pp.,
29.90 Euros . . . . . . . . . . . . . . 941--942
Pierre Charbit and
Stéphan Thomassé and
Anders Yeo The Minimum Feedback Arc Set Problem is
NP-Hard for Tournaments . . . . . . . . 1--4
Amin Coja-Oghlan and
Andreas Goerdt and
André Lanka Strong Refutation Heuristics for Random
$k$-SAT . . . . . . . . . . . . . . . . 5--28
Devdatt Dubhashi and
Johan Jonasson and
Desh Ranjan Positive Influence and Negative
Dependence . . . . . . . . . . . . . . . 29--41
Eslie Ann Goldberg and
Mark Jerrum The Complexity of Ferromagnetic Ising
with Local Fields . . . . . . . . . . . 43--61
Kevin Hutson and
Thomas\'nLewis The Expected Length of a Minimal
Spanning Tree of a Cylinder Graph . . . 63--83
Bill Jackson Zero-Free Intervals for Flow Polynomials
of Near-Cubic Graphs . . . . . . . . . . 85--108
Peter Keevash and
Dhruv Mubayi and
Benny Sudakov and
Jacques Verstraëte Rainbow Turán Problems . . . . . . . . . 109--126
Jan Remy and
Alexander Souza and
Angelika Steger On an Online Spanning Tree Problem in
Randomly Weighted Graphs . . . . . . . . 127--144
C. R. Subramanian List Set Colouring: Bounds and
Algorithms . . . . . . . . . . . . . . . 145--158
Ádám Timár Cutsets in Infinite Graphs . . . . . . . 159--166
A. V. Kostochka and
G. Yu Ore-type graph packing problems . . . . 167--169
Norman Biggs Book Review: ``Topics in Algebraic Graph
Theory, by Lowell W. Beineke and Robin
J. Wilson (Academic Consultant: Peter J.
Cameron), Encyclopedia of Mathematics
and its Applications 102, CUP 2005,
257pp., \pounds 50.00/\$95.00''} . . . . 171--172
Noga Alon and
Vera Asodi Edge Colouring with Delays . . . . . . . 173--191
Joseph E. Bonin and
Omer Giménez Multi-Path Matroids . . . . . . . . . . 193--217
Mei-Chu Chang Additive and Multiplicative Structure in
Matrix Spaces . . . . . . . . . . . . . 219--238
Bill Cuckler Hamiltonian Cycles in Regular
Tournaments . . . . . . . . . . . . . . 239--249
G. E. Farr On the Ashkin--Teller Model and
Tutte--Whitney Functions . . . . . . . . 251--260
Abraham D. Flaxman and
Alan\'nFrieze and
Juan Vera Adversarial Deletion in a Scale-Free
Random Graph Process . . . . . . . . . . 261--270
Dalibor Froncek and
Janja Jerebic and
Sandi Klavzar and
Petr Kovár Strong Isometric Dimension, Biclique
Coverings, and Sperner's Theorem . . . . 271--275
Daniela Küuhn and
Deryk Osthus Maximizing Several Cuts Simultaneously 277--283
William D. May and
John C. Wierman The Application of Non-Crossing
Partitions to Improving Percolation
Threshold Bounds . . . . . . . . . . . . 285--307
Lingsheng Shi and
Nicholas Wormald Colouring Random $4$-Regular Graphs . . 309--344
Brian H. Bowditch The Angel Game in the Plane . . . . . . 345--362
András Máthé The Angel of Power $2$ Wins . . . . . . 363--374
Tom Bohman and
Alan Frieze and
Tomasz Luczak and
Oleg Pikhurko and
Clifford Smyth and
Joel Spencer and
Oleg Verbitsky First-Order Definability of Trees and
Sparse Random Graphs . . . . . . . . . . 375--400
Peter J. Cameron and
K. K. Kayibi Orbital Chromatic and Flow Roots . . . . 401--407
Hemanshu Kaul and
Alexandr Kostochka Extremal Graphs for a Graph Packing
Theorem of Sauer and Spencer . . . . . . 409--416
R. Marchand and
E. Zohoorian Azad Limit Law of the Length of the Standard
Right Factor of a Lyndon Word . . . . . 417--434
Martin Möhle On a Class of Non-Regenerative Sampling
Distributions . . . . . . . . . . . . . 435--444
Eran Ofek On the Expansion of the Giant Component
in Percolated $(n, d, \lambda)$ Graphs 445--457
Lingsheng Shi and
Nicholas Wormald Colouring Random Regular Graphs . . . . 459--494
Jeff Kahn and
Gil Kalai Thresholds and Expectation Thresholds 495--502
Luke Pebody Reconstructing Odd Necklaces . . . . . . 503--514
Amin Coja-Oghlan Colouring Semirandom Graphs . . . . . . 515--552
Harout Aydinian and
Péter L. Erd\Hos All Maximum Size Two-Part Sperner
Systems: In Short . . . . . . . . . . . 553--555
Colin Cooper and
Martin Dyer and
Catherine Greenhill Sampling Regular Graphs and a
Peer-to-Peer Network . . . . . . . . . . 557--593
Jurek Czyzowicz and
Dariusz Kowalski and
Euripides Markou and
Andrzej Pelc Searching for a Black Hole in
Synchronous Tree Networks . . . . . . . 595--619
Svante Linusson and
Johan Wästlund Completing a $(k - 1)$-Assignment . . . 621--629
Svante Janson and
Joel Spencer A Point Process Describing the Component
Sizes in the Critical Window of the
Random Graph Evolution . . . . . . . . . 631--658
Richard Dudley Book Review: ``The Generic Chaining:
Upper and Lower Bounds of Stochastic
Processes'', by Michel Talagrand ,
Springer-Verlag, 2005, 222 pp., \pounds
61.50/\$99.00/79.95 Euros} . . . . . . . 659--660
B. Csaba On the Bollobás--Eldridge Conjecture for
Bipartite Graphs . . . . . . . . . . . . 661--691
Dvir Falik and
Alex Samorodnitsky Edge-Isoperimetric Inequalities and
Influences . . . . . . . . . . . . . . . 693--712
Abraham D. Flaxman and
Alan\'nFrieze and
Juan Carlos Vera On the Average Case Performance of Some
Greedy Approximation Algorithms For the
Uncapacitated Facility Location Problem 713--732
Alan Frieze and
Michael Krivelevich and
Cliff Smyth On the Chromatic Number of Random Graphs
with a Fixed Degree Sequence . . . . . . 733--746
Norbert Hegyvári and
François Hennecart and
Alain Plagne Answer to a Question by Burr and Erd\Hos
on Restricted Addition, and Related
Results . . . . . . . . . . . . . . . . 747--756
Svante Janson On a Random Graph Related to Quantum
Theory . . . . . . . . . . . . . . . . . 757--766
János Körner and
Blerina Sinaimeri On Cancellative Set Families . . . . . . 767--773
Tomasz Schoen Difference Covers . . . . . . . . . . . 775--787
Mark Walters Extensions of the Polynomial
Hales--Jewett Theorem . . . . . . . . . 789--803
Raphael Yuster Packing Cliques in Graphs with
Independence Number $2$ . . . . . . . . 805--817
Alexander Gnedin and
Jim Pitman Poisson Representation of a Ewens
Fragmentation Process . . . . . . . . . 819--827
Pierre Charbit and
Stéphan Thomassé Graphs with Large Girth Not Embeddable
in the Sphere . . . . . . . . . . . . . 829--832
Vojtech Rödl and
Mathias Schacht Regular Partitions of Hypergraphs:
Regularity Lemmas . . . . . . . . . . . 833--885
Vojtech Rödl and
Mathias Schacht Regular Partitions of Hypergraphs:
Counting Lemmas . . . . . . . . . . . . 887--901
M. A. Steel and
L. A. Székely Teasing Apart Two Trees . . . . . . . . 903--922
Amin Coja-Oghlan On the Laplacian Eigenvalues of
$G_{n,p}$ . . . . . . . . . . . . . . . 923--946
Joanna A. Ellis-Monaghan and
Irasema Sarmiento Distance Hereditary Graphs and the
Interlace Polynomial . . . . . . . . . . 947--973
Alexander Barvinok Enumerating Contingency Tables via
Random Permanents . . . . . . . . . . . 1--19
Frédéric Chyzak and
Michael Drmota and
Thomas Klausner and
Gerard Kok The Distribution of Patterns in Random
Trees . . . . . . . . . . . . . . . . . 21--59
Yahya Ould Hamidoune On Iterated Image Size for
Point-Symmetric Relations . . . . . . . 61--66
M. Kang and
T. G. Seierstad The Critical Phase for Random Graphs
with a Given Degree Sequence . . . . . . 67--86
Roberto Oliveira Balls-in-Bins Processes with Feedback
and Brownian Motion . . . . . . . . . . 87--110
Oliver Riordan The $k$-Core and Branching Processes . . 111--136
Vincent Vatter Enumeration Schemes for Restricted
Permutations . . . . . . . . . . . . . . 137--159
N. Broutin and
L. Devroye An Analysis of the Height of Tries with
Random Weights on the Edges . . . . . . 161--202
Adrian Dumitrescu and
Csaba D. Tóth On the Number of Tetrahedra with
Minimum, Unit, and Distinct Volumes in
Three-Space . . . . . . . . . . . . . . 203--224
Roberto Fernández and
Aldo Procacci Regions Without Complex Zeros for
Chromatic Polynomials on Graphs with
Bounded Degree . . . . . . . . . . . . . 225--238
Raymond Hemmecke and
Jason Morton and
Anne Shiu and
Bernd Sturmfels and
Oliver Wienand Three Counter-Examples on Semi-Graphoids 239--257
Svante Janson and
Andrew Thomason Dismantling Sparse Random Graphs . . . . 259--264
H. A. Kierstead and
A. V. Kostochka A Short Proof of the Hajnal--Szemerédi
Theorem on Equitable Colouring . . . . . 265--270
Po-Shen Loh and
Benny Sudakov On the Strong Chromatic Number of Random
Graphs . . . . . . . . . . . . . . . . . 271--286
Vadim Lozin Boundary Classes of Planar Graphs . . . 287--295
T. Sanders A Note on Freiman's Theorem in Vector
Spaces . . . . . . . . . . . . . . . . . 297--305
Roy Wagner Tail Estimates for Sums of Variables
Sampled by a Random Walk . . . . . . . . 307--316
Hans-Otto Georgii Book Review: ``The Random-Cluster
Model'', by Geoffrey Grimmett, Springer,
2006, 377pp., \pounds
69.00/\$125.00/89.95 Euros} . . . . . . 317--318
Noga Alon and
Oded Schwartz and
Asaf Shapira An Elementary Construction of
Constant-Degree Expanders . . . . . . . 319--327
Jean Bertoin Two-Parameter Poisson--Dirichlet
Measures and Reversible Exchangeable
Fragmentation-Coalescence Processes . . 329--337
Arturas Dubickas An Approximation by Lacunary Sequence of
Vectors . . . . . . . . . . . . . . . . 339--345
Shmuel Friedland and
Leonid Gurvits Lower Bounds for Partial Matchings in
Regular Bipartite Graphs and
Applications to the Monomer-Dimer
Entropy . . . . . . . . . . . . . . . . 347--361
W. T. Gowers Quasirandom Groups . . . . . . . . . . . 363--387
Carlos Hoppen and
Nicholas Wormald Induced Forests in Regular Graphs with
Large Girth . . . . . . . . . . . . . . 389--410
Daniela Kühn and
Deryk Osthus Linkedness and Ordered Cycles in
Digraphs . . . . . . . . . . . . . . . . 411--422
Charles Semple and
Dominic Welsh Negative Correlation in Graphs and
Matroids . . . . . . . . . . . . . . . . 423--435
Jim X. Zhang and
Paul Dupuis Large-Deviation Approximations for
General Occupancy Models . . . . . . . . 437--470