Combinatorics of Nonnegative Matrices

Combinatorics of Nonnegative Matrices

by Vladimir Nikolaevich Sachkov, V. E. Tarakanov
     
 

ISBN-10: 082182788X

ISBN-13: 9780821827888

Pub. Date: 08/13/2002

Publisher: American Mathematical Society

In this book, the authors focus on the relation of matrices with nonnegative elements to various mathematical structures studied in combinatorics. In addition to applications in graph theory, Markov chains, tournaments, and abstract automata, the authors consider relations between nonnegative matrices and structures such as coverings and minimal coverings of sets

Overview

In this book, the authors focus on the relation of matrices with nonnegative elements to various mathematical structures studied in combinatorics. In addition to applications in graph theory, Markov chains, tournaments, and abstract automata, the authors consider relations between nonnegative matrices and structures such as coverings and minimal coverings of sets by families of subsets. They also give considerable attention to the study of various properties of matrices and to the classes formed by matrices with a given structure. The authors discuss enumerative problems using both combinatorial and probabilistic methods. They also consider extremal problems related to matrices and problems where nonnegative matrices provide suitable investigative tools. The book contains some classical theorems and a significant number of results not previously published in monograph form, including results obtained by the authors in the last few years. It is appropriate for graduate students, researchers, and engineers interested in combinatorics and its applications.

Product Details

ISBN-13:
9780821827888
Publisher:
American Mathematical Society
Publication date:
08/13/2002
Series:
Translations of Mathematical Monographs, #213
Pages:
269
Product dimensions:
72.50(w) x 10.00(h) x 7.50(d)

Table of Contents

Prefacevii
List of Notationix
Chapter 1.Matrices and Configurations1
Introduction1
1.1.Definitions and examples2
1.2.Term rank. Arrangement of positive elements9
1.3.Combinatorial theory of cyclic matrices27
Chapter 2.Ryser Classes45
Introduction45
2.1.A constructive description of Ryser classes46
2.2.Invariant sets58
2.3.Estimates of the term rank69
Chapter 3.Nonnegative Matrices and Extremal Combinatorial Problems83
Introduction83
3.1.Forbidden configurations84
3.2.Covering problem90
3.3.The van der Waerden-Egorychev-Falikman Theorem106
Chapter 4.Asymptotic Methods in the Study of Nonnegative Matrices117
Introduction117
4.1.Nonnegative matrices and graphs118
4.2.Asymptotics of the number of primitive (0, 1)-matrices131
4.3.Asymptotics of the permanent of a random (0, 1)-matrix135
4.4.Random lattices and Boolean algebras138
4.5.Coverings of sets and (0, 1)-matrices143
4.6.Random coverings of sets151
Chapter 5.Totally Indecomposable, Chainable, and Prime Matrices159
Introduction159
5.1.Totally indecomposable and chainable matrices161
5.2.Rectangular nonnegative matrices170
5.3.Rectangular nonnegative chainable matrices184
5.4.Extension of partial diagonals192
5.5.Prime Boolean matrices199
5.6.Prime nonnegative matrices208
Chapter 6.Sequences of Nonnegative Matrices213
Introduction213
6.1.Directed graphs of nonnegative matrices215
6.2.Irreducible and primitive matrices221
6.3.Tournament matrices227
6.4.Associated operator232
6.5.Sequences of powers of a nonnegative matrix243
6.6.Ergodicity of sequences of nonnegative matrices250
Bibliography263
Index267

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >