Ebook: Building Bridges: Between Mathematics and Computer Science
- Tags: Combinatorics, Number Theory, Numeric Computing, Discrete Mathematics in Computer Science
- Series: Bolyai Society Mathematical Studies 19
- Year: 2008
- Publisher: Springer-Verlag Berlin Heidelberg
- Edition: 1
- Language: English
- 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.
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.
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.
Content:
Front Matter....Pages 1-29
On the Power of Linear Dependencies....Pages 31-45
Surplus of Graphs and the Lov?sz Local Lemma....Pages 47-102
Deformable Polygon Representation and Near-Mincuts....Pages 103-135
Variations for Lov?sz’ Submodular Ideas....Pages 137-164
Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries....Pages 165-203
The Finite Field Kakeya Problem....Pages 205-218
An Abstract Szemer?di Regularity Lemma....Pages 219-240
Isotropic PCA and Affine-Invariant Clustering....Pages 241-281
Small Linear Dependencies for Binary Vectors of Low Weight....Pages 283-307
Pl?nnecke’s Inequality for Different Summands....Pages 309-320
Decoupling and Partial Independence....Pages 321-331
Combinatorial Problems in Chip Design....Pages 333-368
Structural Properties of Sparse Graphs....Pages 369-426
Recent Progress in Matching Extension....Pages 427-454
The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n + 1) ? n ....Pages 455-486
Graph Invariants in the Edge Model....Pages 487-498
Incidences and the Spectra of Graphs....Pages 499-513
The Maturation of the Probabilistic Method....Pages 515-524
A Structural Approach to Subset-Sum Problems....Pages 525-545
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.
Content:
Front Matter....Pages 1-29
On the Power of Linear Dependencies....Pages 31-45
Surplus of Graphs and the Lov?sz Local Lemma....Pages 47-102
Deformable Polygon Representation and Near-Mincuts....Pages 103-135
Variations for Lov?sz’ Submodular Ideas....Pages 137-164
Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries....Pages 165-203
The Finite Field Kakeya Problem....Pages 205-218
An Abstract Szemer?di Regularity Lemma....Pages 219-240
Isotropic PCA and Affine-Invariant Clustering....Pages 241-281
Small Linear Dependencies for Binary Vectors of Low Weight....Pages 283-307
Pl?nnecke’s Inequality for Different Summands....Pages 309-320
Decoupling and Partial Independence....Pages 321-331
Combinatorial Problems in Chip Design....Pages 333-368
Structural Properties of Sparse Graphs....Pages 369-426
Recent Progress in Matching Extension....Pages 427-454
The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n + 1) ? n ....Pages 455-486
Graph Invariants in the Edge Model....Pages 487-498
Incidences and the Spectra of Graphs....Pages 499-513
The Maturation of the Probabilistic Method....Pages 515-524
A Structural Approach to Subset-Sum Problems....Pages 525-545
....