Herausgeber: Martin Grötschel, Gyula Katona
Titel: Building Bridges Between Mathematics and Computer Science
Verlag: Springer-Verlag
ISBN/ISSN: 9783540852216
Auflage: 1
Preis : CHF 110.90
Kategorie: Informatik, EDV Buch
Sprache: English
Technische Daten
Seiten: 595
Kopierschutz: DRM
Geräte: PC/MAC/eReader/Tablet
Formate: PDF

Discrete mathematics and theoretical computer science are closely linked research areas with strong impacts on applications and various other scientific disciplines. Both fields deeply cross fertilize each other. One of the persons who particularly contributed to building bridges between these and many other areas is László Lovász, a scholar whose outstanding scientific work has defined and shaped many research directions in the last 40 years. A number of friends and colleagues, all top authorities in their fields of expertise and all invited plenary speakers at one of two conferences in August 2008 in Hungary, both celebrating Lovász's 60th birthday, have contributed their latest research papers to this volume. This collection of articles offers an excellent view on the state of combinatorics and related topics and will be of interest for experienced specialists as well as young researchers.

Gyula O.H. Katona, President of the Bolyai Society, member of the Hungarian Academy of Sciences, honorary member of the Bulgarian Academy of Sciences

Martin Grötschel, Secretary of the International Mathematical Union, Vice President of Konrad-Zuse-Zentrum Berlin

"Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-organizing Libraries (p. 161-162)


To L´aszl´o Lov´asz on his 60th birthday The starting point is the known fact that some much-studied random walks on permutations, such as the Tsetlin library, arise from walks on real hyperplane arrangements. This paper explores similar walks on complex hyperplane arrangements. This is achieved by involving certain cell complexes naturally associated with the arrangement. In a particular case this leads to walks on libraries with several shelves. We also show that interval greedoids give rise to random walks belonging to the same general family. Members of this family of Markov chains, based on certain semigroups, have the property that all eigenvalues of the transition matrices are non-negative real and given by a simple combinatorial formula. Background material needed for understanding the walks is reviewed in rather great detail.

1. Introduction

The following random walk, called Tsetlin’s library, is a classic in the theory of combinatorial Markov chains. Consider books labeled by the integers 1, 2, . . . , n standing on a shelf in some order. A book is withdrawn according to some probability distribution w and then placed at the beginning of the shelf. Then another book is withdrawn according to w and placed at the beginning of the shelf, and so on. This Markov chain is of interest also for computer science, where it goes under names such as dynamic ?le management and cache management.

Much is known about the Tsetlin library, for instance good descriptions of its stationary distribution, good estimates of the rate of convergence to stationarity, exact formulas for the eigenvalues of its transition matrix Pw, and more. These eigenvalues are nonnegative real and their indexing and multiplicities, as well as their value, are given by very explicit combinatorial data. The Tsetlin library is the simplest of a class of Markov chains on permutations that can be described in terms of books on a shelf. Instead of one customer visiting the library to borrow one book which when returned is placed at the beginning of the shelf, we can picture several customers who each borrows several books. When the books are returned, the books of the ?rst borrower are placed at the beginning of the shelf in the induced order (i.e. the order they had before being borrowed).

Then the books of the second borrower are placed in their induced order, and so on. Finally, the remaining books that noone borrowed stand, in the induced order, at the end of the shelf. The analysis of such a “dynamic library” became part of a vastly more general theory through the work of Bidigare, Hanlon and Rockmore [2], continued and expanded by Brown and Diaconis [13, 14, 15, 16]. They created an attractive theory of random walks on hyperplane arrangements A in Rd, for which the states of the Markov chain are the regions making up the complement of ∪A in Rd. When adapted to the braid arrangement, whose regions are in bijective correspondence with the permutations of {1, 2, . . . , n}, their theory specializes precisely to the “self-organizing”, or “dynamic”, one-shelf library that we just described. The theory was later further generalized by Brown [13, 14] to a class of semigroups.

The genesis of this paper is the question: what about random walks on complex hyperplane arrangements? It is of course not at all clear what is meant. The complement in Cd of the union of a ?nite collection of hyperplanes is a 2d-dimensional manifold, so what determines a ?nite Markov chain? The idea is to consider not the complement itself, but rather a certain ?nite cell complex determining the complement up to homotopy type. In addition, we need that this complex extends to a cell complex for the whole singularity link, since much of the probability mass is typically placed in that extension. Such complexes were introduced by Ziegler and the author in [11]. The construction and basic properties partly run parallel to a similar construction in the real case, well-known from the theory of oriented matroids."
Title Page4
Copyright Page5
Table of Contents6
Curriculum Vitae of László Lovász11
Publications of László Lovász14
Research papers:15
Expository papers:27
On the Power of Linear Dependencies IMRE BÁRÁNY29
1. Introduction29
2. The Steinitz lemma30
3. The story of the Steinitz lemma32
4. Signed sum34
5. Signing vector sequences