Building Bridges
Between Mathematics and Computer Science
1st Edition
Published on 28. May 2010
595 pages
978-3-540-85221-6 (ISBN)
Description
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.
More details
Other editions
Additional editions
Book
09/2008
Springer
€106.99
Shipment within 7-9 days
Persons
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
Content
On the Power of Linear Dependencies.- Surplus of Graphs and the Lovász Local Lemma.- Deformable Polygon Representation and Near-Mincuts.- Variations for Lovász' Submodular Ideas.- Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries.- The Finite Field Kakeya Problem.- An Abstract Szemerédi Regularity Lemma.- Isotropic PCA and Affine-Invariant Clustering.- Small Linear Dependencies for Binary Vectors of Low Weight.- Plünnecke's Inequality for Different Summands.- Decoupling and Partial Independence.- Combinatorial Problems in Chip Design.- Structural Properties of Sparse Graphs.- Recent Progress in Matching Extension.- The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n + 1) × n.- Graph Invariants in the Edge Model.- Incidences and the Spectra of Graphs.- The Maturation of the Probabilistic Method.- A Structural Approach to Subset-Sum Problems.
"Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-organizing Libraries (p. 161-162)
ANDERS BJOERNER
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."
ANDERS BJOERNER
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."
