Custom cover image
Fete of Combinatorics and Computer Science / edited by Gyula O. H. Katona, Alexander Schrijver, Tamás Szőnyi, Gábor Sági
Contributor(s): Resource type: Ressourcentyp: Buch (Online)Book (Online)Language: English Series: Bolyai Society Mathematical Studies ; 20 | SpringerLink BücherPublisher: Berlin, Heidelberg : János Bolyai Mathematical Society and Springer-Verlag, 2010Description: Online-Ressource (450p. 41 illus, digital)ISBN:- 9783642135804
- 1283076268
- 9781283076265
- 511.1 23
- 511.6
- QA164
Contents:
Summary: High Degree Graphs Contain Large-Star Factors -- Iterated Triangle Partitions -- PageRank and Random Walks on Graphs -- Solution of Peter Winkler’s Pizza Problem*† -- Tight Bounds for Embedding Bounded Degree Trees -- Betti Numbers are Testable* -- Rigid and Globally Rigid Graphs with Pinned Vertices -- Noise Sensitivity and Chaos in Social Choice Theory -- Coloring Uniform Hypergraphs with Small Edge Degrees -- Extremal Graphs and Multigraphs with Two Weighted Colours -- Regularity Lemmas for Graphs -- Edge Coloring Models as Singular Vertex Coloring Models -- List Total Weighting of Graphs -- Open Problems.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.PPN: PPN: 1650779933Package identifier: Produktsigel: ZDB-2-SEB | ZDB-2-SXMS | ZDB-2-SMA
Title Page; Copyright Page; 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; 2.2.1. The smallest angle.; 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 GRAPHS1. 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 strategy2.4.2. Alice's strategy in the first phase.; 2.4.3. Alice's strategy in the second phase.; 2.4.4. Analysis of Alice's gain.; 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 subtree2.2.1. Preparations; 2.2.2. Decomposition of; 2.2.3. Sketch of the embedding algorithm.; 2.2.4. Finishing the embedding of T.; 2.2.5. The Main Mapping Procedure.; 2.2.6. The Second Mapping Procedure.; 2.2.7. The Third Mapping Procedure.; 2.2.8. Description of the Embedding Algorithm.; 2.3. The second non-extremal case: T has a long subtree; 2.3.1. Preparations for the embedding; 2.3.2. Embedding T into G.; 2.3.3. Finishing the embedding.; 3. THE EXTREMAL CASE; 3.1. The First Extremal Case; 3.2. The Second Extremal Case
4. LOWER BOUND FOR THE MINIMUM DEGREE IN G4.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
No physical items for this record