More Sets, Graphs and Numbers: A Salute to Vera Sòs and András Hajnal

Cover......Page 1
More Sets, Graphs and Numbers: A Salute to Vera Sòs and András Hajnal......Page 4
Copyright page......Page 5
Table of Contents......Page 6
PREFACE......Page 8
1. SPERNER-TYPE THEOREMS......Page 10
2. LYIVI INEQUALITIES......Page 14
3. PROOF OF THE MAIN THEOREMS......Page 16
4. CONSEQUENCES......Page 19
5. THE MAXIMUM NUMBER OF COMPOSITIONS......Page 21
REFERENCES......Page 24
A QUICK PROOF OF SPRINDZHUK'S DECOMPOSITION THEOREM......Page 26
REFERENCES......Page 32
1. INTRODUCTION......Page 34
2. DISCREPANCY OF GRAPHS......Page 36
3. HYPERGRAPH DISCREPANCY......Page 43
4. SUBGRAPH DISCREPANCY......Page 52
REFERENCES......Page 57
1. INTRODUCTION......Page 58
2.1. Variants of Euler's formula......Page 60
2.2. Other lower bounds......Page 61
2.3. Drawings, upper bounds......Page 62
3. RESULTS AND PROBLEMS ON COMPLETE BIPARTITE GRAPHS......Page 63
3.2. Exact results for complete bipartite graphs......Page 64
3.3. Conjectured exact results for complete bipartite graphs......Page 68
3.4. The best known drawings for other complete bipartite graphs......Page 71
4.1. Complete graphs......Page 73
4.2 . Hypercubes......Page 74
4.3. Meshes......Page 75
REFERENCES......Page 76
AN EXERCISE ON THE AVERAGE NUMBER OF REAL ZEROS OF RANDOM REAL POLYNOMIALS......Page 80
1.THE GENERAL SETTING......Page 81
2. A SPECIAL CASE......Page 82
3. A FIRST RES ULT......Page 84
4. COMMENTS......Page 85
5. RANDOM SEQUENCES AND DETERMINISTIC SEQUENCES......Page 87
6. THE PAPERFOLDING CASE AND A GENERAL THEOREM......Page 89
REFERENCES......Page 92
1. INTRODUCTION......Page 94
3. Cons tructive characterization......Page 95
2. RELATIONS BETWEEN OLD RESULTS......Page 99
2.1. Splitting and augmentation......Page 101
2.2. Connectivity orientation and augmentation......Page 103
2.3. Constructive characterization and splitting......Page 106
3. SPLITTING AND DETACHMENT......Page 107
3.1.1. Constructive characterizations.......Page 108
3.1.2. Orientation.......Page 110
3.1.3. Augmentation.......Page 112
3.2. Directed splitting......Page 113
3.3. Undirected detachment......Page 114
3.4. Directed detachment......Page 118
4. UNCROSSING-BASED RESULTS......Page 119
4.1. Orientations and augmentations through submodular flows......Page 121
4.2. Connectivity orientation and augmentation combined......Page 125
4.3. Directed edge-connectivity augmentation......Page 130
5. CONSTRUCTIVE CHARACTERIZATIONS......Page 131
6. HYPERGRAPHS......Page 134
6.1. Directed hypergraphs......Page 137
REFERENCES......Page 138
1. INTRODUCTION......Page 144
II. PRODUCTS OF CONSECUTIVE INTEGERS......Page 145
III. PRODUCTS OF CONSECUTIVE TERMS IN ARITHMETIC PROGRESSION......Page 148
IV. AN APPLICATION OF THEOREMS 3 AND 4......Page 150
V. THE METHOD OF PROOFS OF THEOREMS 1 TO 4......Page 151
REFERENCES......Page 154
1. INTRODUCTION......Page 158
2. THE THEOREM FOR LOCALLY COMPACT SPACES......Page 159
3. A POSSIBLE GENERALIZATION......Page 166
4 . STATIONARY SET DECOMPOSITION......Page 171
REFERENCES......Page 175
1. INTRODUCTION......Page 176
2.PRELIMINARIES......Page 177
3. DIRAC-TYPE BOUNDS......Page 179
4. GALLAI-TYPE BOUNDS......Page 183
5. CRITICAL GRAPH S WITH NO LARGE CLIQUES......Page 185
6. CRITICAL HYPERGRAPHS WITH FEW EDGES......Page 186
7. ON CRITICAL SIMPLE HYPERGRAPHS......Page 189
8. VARIATIONS: PANCHROMATIC AND STRONG COLORINGS......Page 192
REFERENCES......Page 195
1. INTRODUCTION......Page 200
2.1. Random graphs......Page 202
2.2. Thomason's jumbled graphs......Page 205
2.3. Equivalent definitions of weak pseudo-randomness......Page 207
2.4. Eigenvalues and pseudo-random graphs......Page 212
2.5. Strongly regular graphs......Page 218
3. EXAMPLES......Page 220
4.1. Connectivity and perfect matchings......Page 228
4.2. Maximum cut......Page 231
4.3. Independent sets and the chromatic number......Page 233
4.4. Small subgraphs......Page 237
4.5. Extremal properties......Page 242
4.6. Factors and fractional factors......Page 244
4.7. Hamiltonicity......Page 247
4.8. Random subgraphs of pseudo-random graphs......Page 250
4.9. Enumerative aspects......Page 254
REFERENCES......Page 258
1. INTRODUCTION......Page 264
2. RELATIONAL STRUCTURES......Page 267
3. BOUNDED DEGREES......Page 269
4. DEGENERATED CLASSES OF GRAPHS......Page 272
5. MINOR CLOSED CLASSES OF GRAPHS......Page 274
6. BOUNDS, SUPREMA AND DUALITIES FOR FINITE STRUCTURES......Page 278
7. SUMMARY AND CONCLU DING REMARKS......Page 282
REFERENCES......Page 283
1. INTRODUCTION......Page 286
2. ORDINARY AND TOPOLOGICAL MINORS......Page 287
3. QUASI-PLANAR GRAPHS......Page 288
4. GENERALIZED THRACKLES AND THEIR RELATIVES......Page 291
5. LOCALLY PLANAR GRAPHS......Page 293
6. STRENGTHENING THEOREM 3.6......Page 294
7. STRENGTHENING THEOREM 3.7......Page 295
REFERENCES......Page 299
1.1. CNS polynomials......Page 302
1.2. Integral interpolation......Page 305
2. PROOF OF THEOREMS 1 AND 2......Page 310
REFERENCES......Page 315
1. INTRODUCTION......Page 318
2.1. Single Row Routing......Page 319
2.2. Channel Routing......Page 321
2.3. Switchbox Routing......Page 322
3. 3-DIMENSIONAL ROUTING......Page 324
3.1. The sn = 1 case......Page 325
3.2. The Sn, Sw >2 case......Page 326
REFERENCES......Page 328
1. INTRODUCTION......Page 330
2. THE EARLY DAYS......Page 331
3. VERA JOINS US (AND A CURE FOR AN INCURABLE DISEASE)......Page 333
4. RECENT DEVELOPMENTS AND UNSOLVED PROBLEMS......Page 337
REFERENCES......Page 339
1. INTRODUCTION......Page 342
2. A METHOD TO FORCE THIN LCS SPACES WITH PRESCRIBED CARDINAL SEQUENCE......Page 344
3. LIFTING THEOREM......Page 347
1. INTRODUCTION......Page 360
1.1. Background......Page 361
1.2. Recent developments......Page 362
1.3. Contents of this article......Page 363
2. INITIAL OBSERVATIONS......Page 364
3. R.ANDOM GRAPHS......Page 365
4. COMPLETE MINORS OF DENSE GRAPHS......Page 366
5. PSEUDO-RANDOMNESS AND SOS'S QUESTION......Page 368
6. THE EXTREMAL PROBLEM FOR GENERAL H......Page 371
6.1. General H minors......Page 372
6.2. Estimating '"'((H)......Page 373
7. LINKING......Page 375
8. MINORS AND GIRTH......Page 376
9. MINORS AND CONNECTIVITY......Page 378
REFERENCES......Page 379
1. ENTREE......Page 382
2. TILINGS......Page 383
3. THE FINE AND WILF THEOREM......Page 384
4. BI-SPECIAL WORDS......Page 385
5. BALANCED WORDS......Page 386
6. FRAENKEL WORDS......Page 388
7. STIFF WORDS......Page 389
8. THREE DISTANCES THEOREMS......Page 390
9. LINEAR COMP LEXITY WORDS......Page 391
10. FINE AND WILF WORDS FOR SEVERAL PERIODS......Page 393
12. BALANCEDNESS......Page 396
13. COMPLEXITY......Page 397
14. FINE AND WILF WORDS......Page 398
15. FROBENIUS ' LINEAR DIOPHANTINE PROBLEM......Page 399
16. BV-WORDS......Page 400
REFERENCES......Page 403