Surveys in Combinatorics 2011

Cover......Page 1
LONDON MATHEMATICAL SOCIETY LECTURE NOTE SERIES......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 9
1 Introduction......Page 11
2.2 Power series......Page 14
2.3 The Potts model and the Tutte polynomial......Page 15
3 Uncoloured planar maps: the recursive approach......Page 16
3.1 A functional equation for planar maps......Page 17
Maps with prescribed face degrees......Page 19
Eulerian maps with prescribed face degrees......Page 20
Other families of maps......Page 21
3.3 Equations with one catalytic variable and algebraicity theorems......Page 22
4 Uncoloured planar maps: bijections......Page 24
Four-valent maps and blossoming trees......Page 25
A more general construction......Page 27
Quadrangulations and labelled trees......Page 28
4.2 More bijections......Page 30
5 Coloured planar maps: the recursive approach......Page 31
5.1 A functional equation for coloured planar maps......Page 32
5.2 More functional equations......Page 34
5.3 A linear case: bipolar orientations of maps......Page 35
5.4 A quasi-linear case: spanning trees......Page 39
5.5 When q is a Beraha number: Algebraicity......Page 42
5.6 The general case: differential equations......Page 44
6 Some bijections for coloured planar maps......Page 45
6.2 Spanning trees......Page 46
6.3 The Ising model (q = 2)......Page 47
7.1 Algebraicity......Page 49
7.3 Asymptotics of maps......Page 50
References......Page 51
1 Total Search Problems......Page 61
1.1 NP Total Search Problems......Page 62
1.3 PPAD, and some related concepts......Page 63
2 Sperner's lemma, and an associated computational problem......Page 65
3 Games and Nash Equilibria......Page 68
3.1 Some reductions among equilibrium problems......Page 70
3.2 The "in PPAD" result......Page 71
3.3 The Algebraic Properties of Nash Equilibria......Page 72
4 Brouwer functions, and discrete Brouwer functions......Page 73
4.1 Discrete Brouwer functions......Page 74
5 From Discrete Brouwer functions to Games......Page 76
5.1 Graphical Games......Page 78
6 Easy and hard classes of games......Page 79
6.1 Hard equilibrium computation problems......Page 80
6.2 Polynomial-time equilibrium computation problems......Page 81
7 The Complexity of Path-following Algorithms......Page 82
8 From Games to Markets......Page 86
References......Page 88
1 Introduction......Page 93
2 Basic arguments......Page 94
3 Hypergraph Lagrangians......Page 96
4 Link graphs and multigraphs......Page 99
5 Stability......Page 102
6 Counting......Page 105
7 Flag algebras......Page 107
8 The remaining exact results......Page 111
9 Bounds for complete hypergraphs......Page 115
10 The infinitary perspective......Page 118
11 Algebraic methods......Page 123
12 Probabilistic methods......Page 126
13.1 Jumps......Page 127
13.2 Minimum degree problems......Page 128
13.3 Different host graphs......Page 129
13.4 Coloured Turán problems......Page 131
13.5 The speed of properties......Page 133
13.6 Local sparsity......Page 134
13.7 Counting subgraphs......Page 135
14 Summary of results......Page 137
References......Page 138
Contents......Page 151
1 Introduction......Page 152
2.1 The extremal problems that are studied......Page 153
2.2 Erdős-Stone type problems......Page 154
2.2.1 Refining the Erdős-Stone-Bollob as theorem......Page 155
2.2.3 Complete r-partite subgraphs of dense r-graphs......Page 156
2.3 Saturation problems......Page 158
2.4.1 A general stability theorem......Page 160
2.4.2 Strong stability......Page 161
2.4.3 Kr-free graphs with large minimum degree......Page 162
2.5 The number of graphs with large forbidden subgraphs......Page 164
3.1 The spectral problems that are studied......Page 166
3.2 Spectral forms of the Turán theorem
......Page 167
3.3 A spectral Erdős-Stone-Bollobás  theorem......Page 169
3.4 Saturation problems......Page 170
3.5 Stability problems......Page 171
3.6 The Zarankiewicz problem......Page 172
3.7 Paths and cycles......Page 174
3.8 Hamilton paths and cycles......Page 176
3.9 Clique number and eigenvalues......Page 177
3.10 Number of cliques and eigenvalues......Page 178
4 Some useful tools......Page 180
5 Illustration proofs......Page 182
6 Notation and basic facts......Page 184
References......Page 186
1 What is the cyclic sieving phenomenon?......Page 193
2 An example and a proof......Page 194
3 Representation theory background and another proof......Page 198
4 A representation theory paradigm......Page 202
5 Coxeter groups and permutation statistics......Page 204
6 Complex reflection groups and Springer’s regular elements......Page 208
7 Promotion on rectangular standard Young tableaux......Page 212
8 Variations on a theme......Page 216
9 Multiple groups and multiple statistics......Page 220
10 Catalan CSPs......Page 224
11 A cyclic sieving miscellany......Page 230
12.1 Alternate definitions......Page 233
12.2 More on Catalan CSPs......Page 234
12.3 A combinatorial proof......Page 236
References......Page 237
Contents......Page 245
1 Introduction......Page 246
2 Some notions from Group Theory......Page 250
3.1 Axiomatic projective spaces......Page 252
3.3 Collineations of spaces......Page 253
3.4 Reconstructing the space from its group......Page 254
3.6 Representation by diagram......Page 255
4.2.1 Coxeter groups......Page 256
4.2.3 Coxeter diagrams......Page 257
4.3.2 G as an automorphism group......Page 258
4.4 Buildings as colored graphs......Page 259
4.4.5 Buildings as edge colored graphs......Page 260
5 Buildings of rank 1......Page 261
5.1 The finite doubly transitive groups......Page 262
5.2 Moufang sets......Page 263
5.3 General Moufang sets......Page 269
6.1 Combinatorial definition
......Page 270
6.3 Feit-Higman......Page 271
6.7 Polygons as graphs......Page 272
7 The classical examples and their duals......Page 273
7.2.2 Hermitian quadrangles......Page 274
7.3.2 Twisted triality hexagons......Page 275
8 Split BN-pairs and the Moufang condition......Page 276
8.2 The Moufang condition......Page 278
8.3 The power of primes......Page 279
9.1 Free constructions......Page 280
9.2 Amalgamation......Page 281
9.3 BN-Pairs......Page 283
10.2 Finite order......Page 284
10.3 Innite order......Page 285
10.4 Generalized translation planes......Page 286
10.6 Ostrom-Wagner......Page 287
10.7 Flag-transitive and point-primitive planes......Page 288
10.8 Fermat surfaces and Fermat curves......Page 291
10.9 Singer groups......Page 296
11.2 Regularity and antiregularity......Page 297
11.3 Subquadrangles......Page 298
12 Parameters of generalized quadrangles......Page 299
12.3 Generalized quadrangles with small parameters......Page 300
12.4 From quadrangles to planes......Page 301
13 Elation quadrangles......Page 302
13.2 Kantor families......Page 303
13.3 Parameters of elation quadrangles......Page 305
13.4 Infinite EGQs......Page 307
14.1 The kernel......Page 308
14.2 T(n,m,q)s and translation quadrangles......Page 310
14.3 Infinite TGQs......Page 311
15.1 F-Factors......Page 313
15.2 Parameters of STGQs......Page 314
15.3 Singer groups for quadrangles......Page 315
15.4 Appendix: Translation and elation polygons......Page 316
16.1 Locally nite polygons......Page 317
16.2 Indiscernibles......Page 318
16.3 Quadrangles of orthogonal type......Page 319
16.4 Projective spaces PG(|N|,q)......Page 320
17 Thin buildings and the field F1......Page 321
17.1 Bad approach......Page 322
17.2 The projective space PG(n, F1), and PGLn+1(F1)......Page 323
17.3 Algebraic varieties over F1......Page 325
17.4 Algebraic groups over F1 and F1-buildings......Page 326
17.5 Zeta functions over F1......Page 329
17.6 The hyperring of adele classes......Page 330
17.7 Hyperfield extensions of the Krasner hyperfield K......Page 331
References......Page 333
1 Coloured graphs......Page 343
2.1 Extremal multigraphs in former times......Page 344
2.3 The two extremal functions......Page 345
3 Types......Page 347
3.1 Types and extremal functions......Page 349
4.1 Hereditary graph properties......Page 350
4.2 Edit distance......Page 353
4.3 Ramsey games......Page 355
5.2 Stability......Page 357
6 Working with types......Page 358
7 Examples......Page 359
7.1 Graphs with three vertices......Page 360
7.2 Graphs with four vertices......Page 361
7.4 Types other than τ (a, b): two specimen cases......Page 362
7.5 Split graphs......Page 363
7.6 Short cycles......Page 364
7.7 More than one forbidden graph......Page 365
7.8 Complete bipartite graphs......Page 366
8 Richer’s conjectures......Page 367
9.1 Szemer´edi’s Regularity Lemma — is it needed?......Page 368
9.2 The relationship between κp and μp......Page 370
References......Page 371
1 Introduction......Page 375
1.1 Motivation......Page 376
1.2 Notation and conventions......Page 377
2.1 Degrees......Page 378
2.2 Clique number......Page 379
2.3 The Giant Component......Page 381
2.4 Connectivity......Page 385
2.5 Higher Connectivity......Page 389
2.6 Hamiltonicity and Matchings......Page 390
2.7 Chromatic number......Page 391
2.8 Coverage......Page 392
2.10 Other norms and neighbourhoods......Page 393
2.11 Sharpness of Monotone Properties......Page 394
2.12 Boundary Effects......Page 395
3.1 Neighbourhood Radius......Page 396
3.2 Connectivity......Page 397
3.3 The Giant Component......Page 402
3.4 Related Models......Page 404
3.5 Other results......Page 405
References......Page 406
1 Introduction......Page 413
2 The Delta Lemma......Page 414
3 Entries not in transversals......Page 416
4 Disjoint transversals......Page 418
5 Partial transversals......Page 421
6.1 Complete Mappings and Orthomorphisms......Page 422
6.2 Which groups have transversals?......Page 425
6.3 How many transversals does a group have?......Page 426
6.4 Congruences and divisors......Page 427
6.5 Groups of small order......Page 429
7 Number of transversals......Page 430
8 Generalised transversals......Page 432
9 Covering radii for sets of permutations......Page 436
10 Generalisations of latin squares......Page 438
References......Page 441