Book Cover
E-book

Title Fete of combinatorics and computer science / Gyula O.H. Katona, Alexander Schrijver, Tamás Szőnyi (eds.)
Published Berlin ; Heidelberg ; New York : Springer, 2010
Online access available from:
Springer eBooks    View Resource Record  

Copies

Description 1 online resource (365 pages) : illustrations
Series Bolyai Society mathematical studies ; 20
Bolyai Society mathematical studies ; 20
Contents Cover -- Table of Contents -- Preface -- High Degree Graphs Contain Large-Star Factors -- 1. Introduction -- 2. Regular Graphs -- 3. The Proof Of The Main Result -- 4. Concluding Remarks And Open Problems -- References -- Iterated Triangle Partitions -- 1. Introduction -- 2. Subdividing By Bisectors -- 2.1. Subdividing Into Three Daughters -- 2.2. Dividing Into Six Triangles -- 3. Subdividing By Medians -- 3.1. Analytic Approach -- 3.2. Hyperbolic Approach -- 4. Subdividing By The Gergonne Point -- 5. Subdividing By The Lemoine Point -- 6. Concluding Remarks -- References -- Pagerank And Random Walks On Graphs -- 1. Introduction -- 2. Laplacian, The Green'S Function And Pagerank -- 3. Pagerank, The Hitting Time And The Effective Resistance In Electrical Networks -- 4. Several Matrix-Forest Theorems -- 5. Pagerank And Other Invariants In Terms Of Rooted Spanning Forests -- 6. Using The Generalized Hitting Time To Find Sparse Cuts -- 7. Using Pagerank To Estimate The Effective Resistance -- References -- Solution Of Peter Winkler'S Pizza Problem*! -- 1. Introduction -- 2. The Lower Bound -- 2.1. Preliminaries -- 2.2. Minimal Triples -- 2.3. An Auxiliary One-Jump Strategy -- 2.4. A Two-Jump Strategy -- 2.5. Proof of the Lower Bound -- 3. The Upper Bound -- 4. Fixed Number Of Slices -- 5. Cuttings Into 15 And 21 Slices -- 6. One-Jump Strategies -- 6.1. Lower Bound -- 6.2. Upper Bound -- 7. Algorithms -- 7.1. Linear Algorithm -- 7.2. Optimal Strategies -- References -- Tight Bounds For Embedding Bounded Degree Trees -- 1. Introduction -- 2. The Non-Extremal Case -- 2.1. Some Tools for the Proofs in the Non-Extremal Cases -- 2.2 . The First Non-Extremal Case: T Has a Broad Subtree -- 2.3. The Second Non-Extremal Case: T Has a Long Subtree -- 3. The Extremal Case -- 3.1. The First Extremal Case -- 3.2. The Second Extremal Case -- 4. Lower Bound For The Minimum Degree In G -- 4.1. The First Extremal Case -- 4.2. The Second Extremal Case -- References -- Betti Numbers Are Testable* -- 1. Introduction -- 2. The Convergence Of Simplicial Complexes -- 3. Betti Numbers And Combinatorial Laplacians -- 4. Weak Convergence Of Probability Measures -- 5. Spectral Convergence -- 6. The Proof Of Theorem 1 -- References -- Rigid And Globally Rigid Graphs With Pinned Vertices -- 1. Introduction -- 2. Rigid Frameworks With Pinned Vertices -- 3. Rigid Graphs With Pinned Vertices -- 4. The Two-Dimensional Rigidity Matroid -- 5. Optimal Families Of Tracks And Smallest Pinning Sets -- 6. The Network Localization Problem -- 7. Graphs With A Connected Rigidity Matroid -- 7.1. M-Connected Graphs With Pinned Vertices -- 8. Low Cost Anchor Sets In Uniquely Localizable Networks -- References -- Noise Sensitivity And Chaos In Social Choice Theory -- 1. Introduction -- 2. Proofs Of The Equivalence Theorems -- 2.1. A Coupling Argument -- 2.2. An Elementary Harmonic Analysis Argument -- 2.3. Individual Power -- 3. Multi-Level Majority -- T$
Summary 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, whose outstanding scientific work has defined and shaped many research directions in the past 40 years. A number of friends and colleagues, all top authorities in their fields of expertise gathered at the two conferences in August 2008 in Hungary, celebrating Lovász' 60th birthday. It was a real fete of combinatorics and computer science. Some of these plenary speakers submitted their research or survey papers prior to the conferences. These are included in the volume "Building Bridges". The other speakers were able to finish their contribution only later, these are collected in the present volume
Bibliography Includes bibliographical references
Notes Print version record
Subject Combinatorial analysis.
Computer science -- Mathematics.
Genre/Form Kongress.
Form Electronic book
Author Katona, G.
Schrijver, A.
Szőnyi, T.
LC no. 2010928477
ISBN 1283076268
3642135803 (electronic bk.)
9639453129 (JBMS)
9781283076265
9783642135804 (electronic bk.)
9789639453128 (JBMS)