Mathematics of Ramsey Theory

ISBN-13: 9783642729072 / Angielski / Miękka / 2012 / 269 str.

Jaroslav Nesetril; Vojtech R. DL

Opis

One of the important areas of contemporary combinatorics is Ramsey theory. Ramsey theory is basically the study of structure preserved under partitions. The general philosophy is reflected by its interdisciplinary character. The ideas of Ramsey theory are shared by logicians, set theorists and combinatorists, and have been successfully applied in other branches of mathematics. The whole subject is quickly developing and has some new and unexpected applications in areas as remote as functional analysis and theoretical computer science. This book is a homogeneous collection of research and survey articles by leading specialists. It surveys recent activity in this diverse subject and brings the reader up to the boundary of present knowledge. It covers virtually all main approaches to the subject and suggests various problems for individual research.

Spis treści

Ramsey Theory Old and New.- 1. Ramsey Numbers.- 2. Transfinite Ramsey Theory.- 3. Chromatic Number.- 4. Classical Theorems.- 5. Other Classical Theorems.- 6. Structural Generalizations.- 7. Infinite Ramsey Theorem.- 8. Unprovability Results.- 9. Non-Standard Applications.- I. Classics.- Problems and Results on Graphs and Hypergraphs: Similarities and Differences.- 1. Extremal Problems of Turán Type.- 2. Density Problems.- 3. Ramsey’s Theorem.- 4. Ramsey-Turán Type Problems.- 5. Chromatic Numbers.- Note on Canonical Partitions.- II. Numbers.- On Size Ramsey Number of Paths, Trees and Circuits. II.- 1. Introduction.- 2. Proof of Theorem 1 — Part One.- 3. Proof of Theorem 1 — Part Two.- 4. Proof of Theorem 2.- 5. Proof of Theorem 3.- On the Computational Complexity of Ramsey-Type Problems.- 1. Introduction.- 2. NP-Complete Ramsey Problems.- 3. Polynomial-Bounded Ramsey Problems.- 4. Discussion.- Constructive Ramsey Bounds and Intersection Theorems for Sets.- 1. Introduction.- 2. Families of Sets with Prescribed Intersections.- 3. The Proof of Theorem 2.3.- 4. The Proof of Theorem 1.1.- Ordinal Types in Ramsey Theory and Well-Partial-Ordering Theory.- 1. Introduction.- 2. Sheaves.- 3. Ramsey Systems.- 4. Well-Partial-Ordering.- 5. Erdös-Szekeres Theorem.- 6. Ramsey Systems.- 7. Canonical Ramsey Theorem.- III. Structural Theory.- Partite Construction and Ramsey Space Systems.- 1. Introduction.- 2. Statement of Results.- 3. Partite Lemma.- 4. Partite Construction.- 5. Applications.- Graham-Rothschild Parameter Sets.- 1. Introduction.- 2. Parameter Sets and Parameter Words (Definition and Basic Examples).- 3. Hales-Jewett’s Theorem.- 4. Graham-Rothschild’s Theorem.- 5. Infinite Versions.- 6. Other Structures.- Shelah’s Proof of the Hales-Jewett Theorem.- IV. Noncombinatorial Methods.- Partitioning Topological Spaces.- 1. Introduction.- 2. Partitioning Singletons.- 3. Partitioning Pairs.- 4. Open Problems.- Topological Ramsey Theory.- 1. Introduction.- 2. Ramsey Spaces and Ellentuck’s Theorem.- 3. Finitary Consequences of Ellentuck Type Theorems.- 4. The Axiom of Choice and the Construction of Non-Ramsey Sets.- 5. Finite Dimensional Analogues of Ellentuck Type Theorems.- 6. Canonical Partitions.- Ergodic Theory and Configurations in Sets of Positive Density.- 1. Introduction.- 2. Correspondence Between Subsets of ?2 and ?2-Actions.- 3. Ergodic Averages for Subsets of ?2.- 4. First Application to Subsets of Positive Density in ?2.- 5. Proof of Theorem A.- 6. A Recurrence Property of ?2-Actions.- 7. Proof of Theorem B.- V. Variations and Applications.- Topics in Euclidean Ramsey Theory.- 1. Introduction.- 2. Preliminaries.- 3. Ramsey Sets.- 4. Sphere-Ramsey Sets.- 5. Concluding Remarks.- On Pisier Type Problems and Results (Combinatorial Applications to Number Theory).- 1. Introduction.- 2. Multiplicative Bases and Szemerédi-Ruzsa Theorem.- 3. Graphical Sequences and Examples of Their Use.- 4. Pisier Type Theorems.- 5. Pisier Problem — Positive Results.- 6. Special Ramsey Graphs — the Partite Construction.- Combinatorial Statements Independent of Arithmetic.- 1. Introduction.- 2. Notation.- 3. Arithmetic.- 4. Conclusions.- Boolean Complexity and Ramsey Theorems.- 1. General Remarks.- 2. An Example of a Lower Bound to Formula Size Complexity.- Uncrowded Graphs.- 1. Graphs.- 2. Hypergraphs.- 3. Heilbronn’s Conjecture.- Author Index.