Combinatorial matrix classes

Cover......Page 1
ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS 108......Page 2
Combinatorial Matrix Classes......Page 4
9780521865654......Page 5
Contents......Page 6
Preface......Page 10
1.1 Fundamental Concepts......Page 12
1.2 Combinatorial Parameters......Page 16
1.3 Square Matrices......Page 19
1.4 An Existence Theorem......Page 23
1.5 An Existence Theorem for Symmetric Matrices......Page 25
1.6 Majorization......Page 26
1.7 Doubly Stochastic Matrices and Majorization......Page 30
References......Page 34
2.1 The Gale–Ryser and Ford–Fulkerson Theorems......Page 36
2.2 Tournament Matrices and Landau’s Theorem......Page 43
2.3 Symmetric Matrices......Page 50
References......Page 53
3.1 A Special Matrix in A(R, S)......Page 56
3.2 Interchanges......Page 61
3.3 The Structure Matrix T(R, S)......Page 68
3.4 Invariant Sets......Page 73
3.5 Term Rank......Page 80
3.6 Widths and Multiplicities......Page 90
3.7 Trace......Page 97
3.8 Chromatic Number......Page 102
3.9 Discrepancy......Page 108
3.10 Rank......Page 111
3.11 Permanent......Page 126
3.12 Determinant......Page 132
References......Page 140
4.1 Cardinality of A(R, S) and the RSK Correspondence......Page 146
4.2 Irreducible Matrices in A(R, S)......Page 174
4.3 Fully Indecomposable Matrices in A(R, S)......Page 180
4.4 A(R, S) and Z^+(R, S) with Restricted Positions......Page 185
4.5 The Bruhat Order on A(R, S)......Page 201
4.6 The Integral Lattice L(R, S)......Page 215
4.7 Appendix......Page 221
References......Page 226
5.1 Algorithm for a Matrix in T(R)......Page 230
5.2 Basic Properties of Tournament Matrices......Page 233
5.3 Landau’s Inequalities......Page 238
5.4 A Special Matrix in T(R)......Page 241
5.5 Interchanges......Page 245
5.6 Upsets in Tournaments......Page 249
5.7 Extreme Values of \tilde{u}(R) and \bar{u}(R)......Page 258
5.8 Cardinality of T(R)......Page 267
5.9 The Class T(R; 2) of 2-Tournament Matrices......Page 278
5.10 The Class A(R, *)_0 of (0, 1)-Matrices......Page 285
References......Page 293
6.1 Diameter of Interchange Graphs G(R, S)......Page 296
6.2 Connectivity of Interchange Graphs......Page 302
6.3 Other Properties of Interchange Graphs......Page 306
6.4 The Δ-Interchange Graph G_Δ(R)......Page 311
6.5 Random Generation of Matrices in A(R,S) and T(R)......Page 316
References......Page 319
7.1 Symmetric Interchanges......Page 322
7.2 Algorithms for Symmetric Matrices......Page 325
7.3 The Class A(R)_0......Page 333
7.4 The Class A(R)......Page 342
References......Page 345
8.1 Transportation Polytopes......Page 348
8.2 Symmetric Transportation Polytopes......Page 359
8.3 Term Rank and Permanent......Page 367
8.4 Faces of Transportation Polytopes......Page 376
References......Page 387
9.1 Random Functions......Page 390
9.2 Basic Properties......Page 391
9.3 Faces of the Assignment Polytope......Page 396
9.4 Graph of the Assignment Polytope......Page 414
9.5 Majorization Polytopes......Page 428
9.6 A Special Subpolytope of Ω_n......Page 437
9.7 The Even Subpolytope of Ω_n......Page 444
9.8 Doubly Substochastic and Superstochastic Matrices......Page 459
9.9 Symmetric Assignment Polytope......Page 464
9.10 Doubly Stochastic Automorphisms......Page 468
9.11 Diagonal Equivalence......Page 475
9.12 Applications of Doubly Stochastic Matrices......Page 482
9.13 Permanent of Doubly Stochastic Matrices......Page 493
9.14 Additional Related Results......Page 506
References......Page 511
Master Bibliography......Page 522
Index......Page 547