Global Methods for Combinatorial Isoperimetric Problems

Half-title......Page 2
Series-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 8
Preface......Page 10
1.2.1 K, the complete graph on n vertices......Page 16
1.2.2 Z, the n-cycle......Page 17
1.2.3 The d-cube, Q......Page 19
1.3.1.1 Example......Page 24
1.3.1.2 Another representation of wl......Page 25
1.3.2 The deBruijn graph of order 4......Page 27
1.3.3 Partitioning problems......Page 29
1.3.3.1 Examples......Page 31
1.4 Comments......Page 33
2.1.1 Basic definitions......Page 35
2.2 Algorithms......Page 36
2.2.2 Positive weights: Dijkstra\'s algorithm......Page 37
2.2.4 The general case......Page 38
2.3 Reduction of wirelength to minpath......Page 39
2.4.1 Definitions......Page 40
2.4.2 Examples......Page 41
2.4.3 Steiner operations......Page 42
2.5 Comments......Page 44
3.2.1.1 The n-gon, Z......Page 47
3.2.3.1 The dihedral group, D......Page 48
3.2.4 Definition......Page 49
3.2.5 Basic properties of stabilization......Page 51
3.2.6 Multiple stabilizations......Page 52
3.2.7 Stability order......Page 53
3.2.7.2 Examples......Page 54
3.2.8 Ideals......Page 55
3.2.9 The derived network......Page 56
3.2.10 Summary......Page 58
3.3.1 Introduction......Page 59
3.3.2 Definition......Page 60
3.3.3 Basic properties of compression......Page 61
3.3.4 The compressibility order......Page 62
3.3.4.2 Example......Page 63
3.4 Comments......Page 64
4.1.1.1 Exercise......Page 67
4.2 Stabilization and VIP......Page 68
4.3 Compression for VIP......Page 71
4.3.1 Compressibility order......Page 73
4.4 Optimality of Hales numbering......Page 74
4.5.1.1 Example......Page 76
4.5.2 Reducing bandwidth to minimum path......Page 77
4.5.3 Partitioning to minimize pins......Page 79
4.6 Comments......Page 81
5.1 Graphs of regular solids......Page 83
5.1.1 The dodecahedron and icosahedron......Page 85
5.2 A summary of Coxeter theory......Page 89
5.2.1.2 Generators and relations......Page 90
5.2.1.4 Length......Page 91
5.2.1.6 Example......Page 92
5.2.1.7 Parabolic subgroups......Page 93
5.3 The structure of stability orders......Page 94
5.3.1.1 Definition......Page 95
5.4.1 The algorithm......Page 97
5.4.2 The deBruijn graph revisited......Page 98
5.5.1 The 24-vertex (24-cell)......Page 100
5.5.1.1 Generating the stability order......Page 105
5.5.1.2 Generating the derived network......Page 106
5.5.2 The 120-vertex......Page 107
5.5.3 Cayley graphs of Coxeter groups......Page 110
5.6 Extended stabilization......Page 111
5.6.1.1 Example......Page 114
5.7 Comments......Page 115
5.7.1 Stabilization compared to isomorph rejection......Page 116
5.7.2 More on deBruijn graphs......Page 117
6.1 Additivity......Page 118
6.2.1 Definitions......Page 122
6.3 The Ahlswede–Cai theorem......Page 124
6.3.1 Applications......Page 125
6.3.1.1 Products of complete graphs......Page 127
6.3.1.2 Products of complete bipartite graphs......Page 128
6.3.1.3 Products of crosspolytopes......Page 129
6.4.2 The solution for d = 1......Page 130
6.4.3 The solution for d = 2......Page 131
6.4.4 Solution for all d > 2......Page 133
6.5 Comments......Page 140
7 Isoperimetric problems on infinite graphs......Page 143
7.1.1 Cubical......Page 144
7.1.1.3 d > 2......Page 145
7.1.2 Triangular......Page 148
7.1.2.2 The stability order of V......Page 149
7.1.2.3 Solutions for all k......Page 150
7.1.3 The hexagonal tessellation......Page 154
7.2 Comments......Page 157
7.2.3 Tessellations of hyperbolic space......Page 158
7.2.4 The VIP on Z......Page 159
8 Isoperimetric problems on complexes......Page 160
8.1.1.1 The face lattice of the d-cube......Page 161
8.1.2 Shadows......Page 162
8.1.3 Duality......Page 163
8.1.4 The Kruskal–Katona theorem......Page 164
8.1.5 Macaulay posets......Page 165
8.2 Steiner operations for MSP......Page 167
8.2.1 Stabilization......Page 168
8.2.2 Compression......Page 170
8.2.3 Lindstrom\'s theorem......Page 171
8.2.4.1 The theorems of Leeb and Bezrukov–Elsasser......Page 175
8.2.4.2 The theorems of Vasta and Leck......Page 176
8.3.1 Profile scheduling......Page 177
8.3.2 Bandwidth scheduling and wirelength scheduling......Page 180
8.4.1 More MSPs......Page 181
8.4.2 Other complexes......Page 182
8.4.4 Combinatorics since the 1960s......Page 183
9.1.1 Quotients......Page 184
9.1.2.1 Strong MWI-morphisms......Page 186
9.1.2.2 Weak MWI-morphisms......Page 187
9.2.1 EIP on the dodecahedron......Page 188
9.2.2 EIP on BS......Page 190
9.2.3 EIP on the 24-cell......Page 192
9.2.4 Z × Z......Page 193
9.3.1 The product of Petersen graphs......Page 195
9.4.1 How to repair broken inequalities......Page 197
9.5.1.1 Representation......Page 200
9.5.1.4 Basic reflections......Page 201
9.5.2.1 Finding phi......Page 203
9.5.2.2 The MinShadow function......Page 204
9.5.3.1 Generating ideals......Page 205
9.5.3.2 Generating ideals of Q......Page 206
9.6 Comments......Page 209
10.1 The Bollobas–Leader theorem......Page 211
10.2.1 Simplifying Kleitman–West by stabilization......Page 217
10.3 VIP on the Hamming graph......Page 223
10.4 Sapozhenko\'s problem......Page 224
10.4.1 The crooked neighborhood of .........Page 225
10.4.2.1 The Didonean embedding of L (n) into [0, 1]......Page 226
10.5.1.1 Modeling the brain......Page 228
10.5.1.4 The doctor\'s waiting room problem......Page 229
10.5.2 The Hwang–Lagarias theorem......Page 230
10.5.4 Kleitman–West again......Page 231
Afterword......Page 232
A.5 Steiner symmetrization......Page 234
A.6 The legend of the founding of Carthage......Page 235
A.6.1 Dido\'s principle......Page 236
References......Page 238
Index......Page 244