Matroid Theory and Its Applications : Lectures Given at a Summer School of the Centro Internazionale Matematico Estivo (C.I.M.E.) Held in Varenna (Como), Italy, August 24 - September 2, 1980

Lectures: T.h. Brylawski: The Tutte Polynomial.- D.j.a. Welsh: Matroids And Combinatorial Optimisation.- Seminars: M. Barnabei, A. Brini, G.-c. Rota: Un’introduzione Alla Teoria Delle Funzioni Di Möbius.- A. Brini: Some Remarks On The Critical Problem.- J. Oxley: On 3-connected Matroids And Graphs.- R. Peele: The Poset Of Subpartitions And Cayley’s Formula For The Complexity Of A Complete Graph.- A. Recski: Engineering Applications Of Matroids.- T. Zaslavisky: Voltage-graphic Matroids. M. Barnabei, A. Brini, G.-c. Rota: Un’introduzione Alla Teoria Delle Funzioni Di Möbius -- A. Brini: Some Remarks On The Critical Problem -- T.h. Brylawski: The Tutte Polynomial -- J. Oxley: On 3-connected Matroids And Graphs -- R. Peele: The Poset Of Subpartitions And Cayley’s Formula For The Complexity Of A Complete Graph -- A. Recski: Engineering Applications Of Matroids -- D.j.a. Welsh: Matroids And Combinatorial Optimisation -- T. Zaslavisky: Voltage-graphic Matroids. A. Barlotti (ed.) Originally Published: Napoli: Liguori, 1980. Includes Bibliographical References. Cover......Page 1 Matroid Theory and Its Applications......Page 2 ISBN 9783642111099......Page 3 CONTENTS......Page 4 1. Introduzione......Page 6 2. Reticoli distributivi ed insiemi parzialmente ordinati......Page 8 3. Coni di valutazione......Page 13 4. Anello di valutazione di un reticolo distributivo......Page 20 5. La funzione di Mebius......Page 28 6. L'algebra di Mebius......Page 45 7. La funzione di Mebius nei reticoli semimodulari......Page 57 8. L'anello di Tutte-Grothendieck......Page 68 9. Un'applicazione geometrica......Page 79 Bibliografia......Page 94 Introduction......Page 110 References......Page 120 The Tutte Polynomial Part I: General Theory......Page 122 1. Introduction......Page 123 2. A Prototypical Example......Page 128 3. The Tutte Polynomial......Page 139 4. Matroid Constructions......Page 169 5. Reconstruction......Page 182 6. Identities, Inequalities, and Extrenal Matroid Theory......Page 211 Bibliography......Page 260 Introduction......Page 273 References......Page 281 I. Introduction......Page 284 II. The Subpartition of a Function......Page 285 III. Cayley's Formula for Tree(n)......Page 286 References......Page 289 I. Various Problems......Page 292 II. Various Remarks......Page 294 III. Formulation of the Network Analysis Problem......Page 295 V. A Stronger Necessary Condition......Page 297 VI. How Can One Check Conditions (C1) and (C2) ?......Page 300 VII. Is (C2) Sufficient?......Page 301 VIII. Should We Always Accept 'Generality'?......Page 302 IX. Some Remarks on Question 3B......Page 303 X. Applications to Network Synthesis......Page 304 References......Page 306 Matroids and Combinatorial Optimisation......Page 313 2. Low level complexity......Page 316 3. The class NP......Page 317 4. NP-complete problems......Page 320 5. Some Examples......Page 321 6. P-space......Page 323 1. Definitions......Page 326 2. Classes of matroids......Page 329 3 . Special Matroids......Page 333 4. Excluded minor theorems......Page 335 5. Matroid polyhedra......Page 336 1. greedy algorithm......Page 339 2. The union of matroids......Page 340 3. The Shannon switching game......Page 342 4. A polynomial algorithm for k-connectivity......Page 343 1. The parity problem......Page 346 2. 2-polymatroids......Page 348 3. The Gallai - Lovasz Identity......Page 350 4. A min-max theorem for linear 2-polymatroids......Page 353 5. On a polynomial algorithm for the 2-parity problem......Page 357 6. Pinning planar structures......Page 359 1 The concept of an oracle......Page 362 2. Examples and further results......Page 364 3. The 2-PARITY problem is exponential......Page 365 1 Binary and regular matroids......Page 368 2. Splitters......Page 369 3. The decomposition theorem......Page 372 4. A polynomial algorithm to test whether a matrix is totally unimodular......Page 376 1. The blocking problem......Page 378 2. Colouring graphs......Page 381 3. Flows taking values in an abelian group......Page 382 4. Tangential Blocks......Page 385 5. A problem on the Desargues Configuration......Page 388 1. The max-flow min-cut theorem......Page 389 2. Multicommodity flows......Page 393 3. Multicommodity flows in matroids......Page 395 4. A summary of results......Page 398 References......Page 401 Voltage-Graphic Matroids......Page 407 References......Page 411