Ramsey theory for discrete structures Hans Jürgen Prömel

Format:

Book

Author/Creator:

Prömel, H. J.

Language:

English

Subjects (All):

Ramsey theory.

Mathematics.

Combinatorics.

Discrete Mathematics.

Discrete Mathematics in Computer Science.

Local Subjects:

Mathematics.

Combinatorics.

Discrete Mathematics.

Discrete Mathematics in Computer Science.

Physical Description:

1 online resource

Place of Publication:

Cham Springer 2013

System Details:

PDF

text file

Summary:

This monograph covers some of the most important developments in Ramsey theory from its beginnings in the early 20th century via its many breakthroughs to recent important developments in the early 21st century

Contents:

Roots of Ramsey Theory Ramsey's Theorem From Hilbert's Cube Lemma to Rado's Thesis A Starting Point of Ramsey Theory: Parameter Sets Definitions and Basic Examples Hales-Jewett's Theorem Graham-Rothschild's Theorem Canonical Partitions Back to the Roots: Sets Ramsey Numbers Rapidly Growing Ramsey Functions Product Theorems A Quasi Ramsey Theorem Partition Relations for Cardinal Numbers Graphs and Hypergraphs Finite Graphs Infinite Graphs Hypergraphs on Parameter Sets Ramsey Statements for Random Graphs Sparse Ramsey Theorems Density Ramsey Theorems Szemerédi's Theorem Density Hales-Jewett Theorem

Machine generated contents note: pt. I Roots of Ramsey Theory

1. Ramsey's Theorem

1.1. Frank Plumpton Ramsey

1.2. Ramsey's Theorem

1.3. Erdos-Szekeres' Theorem

1.4. Erdos-Rado's Canonization Theorem

2. From Hilbert's Cube Lemma to Rado's Thesis

2.1. Hilbert's Cube Lemma

2.2. Schur's Lemma

2.3. Van der Waerden's Theorem

2.4. Schur's Extension of Van der Waerden's Theorem

2.5. Rado's Thesis

2.5.1. Partition Regular Systems of Homogenous Linear Equations

2.5.2. (m, p, c)-Sets

2.5.3. Proof of Rado's Theorem

2.5.4. Finite and Infinite Sums

pt. II Starting Point of Ramsey Theory: Parameter Sets

3. Definitions and Basic Examples

3.1. Parameter Words

3.1.1. Parameter Words Over the Empty Alphabet

3.1.2. Parameter Words Over a One-Element Alphabet

3.1.3. Parameter Words Over a Two-Element Alphabet

3.1.4. Parameter Words Over a k-Element Alphabet

3.1.5. Parameter Words Over GF(q)

3.2. Parameter Words and Finite Groups

3.2.1. Parameter Words Over [{0}, GF(q)*]

3.2.2. Parameter Words Over [{a}, G]

3.2.3. Parameter Words Over [k, {e, π}]

4. Hales-Jewett's Theorem

4.1. Hales-Jewett's Theorem

4.2. Some Applications

4.2.1. Arithmetic Progressions

4.2.2. Gallai-Witt's Theorem

4.2.3. Deuber's (m, p, c)-Sets

4.2.4. Idempotents in Finite Algebras

4.2.5. Lattices and Posets

4.3. *-Version

5. Graham-Rothschild's Theorem

5.1. Graham-Rothschild's Theorem

5.2. Applications

5.2.1. Ramsey's Theorem

5.2.2. Dual Ramsey Theorem

5.2.3. Distributive Lattices

5.2.4. Finite Unions and Finite Sums

5.2.5. Linear and Affine Spaces

6. Canonical Partitions

6.1. Canonizing Hales-Jewett's Theorem

6.2. Canonizing van der Waerden's Theorem

6.3. Canonizing Graham-Rothschild's Theorem

6.4. Applications

6.4.1. Finite Unions and Finite Sums

6.4.2. Boolean Lattices

6.4.3. Finite Sets

pt. III Back to the Roots: Sets

7. Ramsey Numbers

7.1. Finite Ramsey Theorem: A Constructive Proof

7.2. Some Exact Values

7.3. Lower Bound for Diagonal Ramsey Numbers

7.4. Asymptotics for Off-Diagonal Ramsey Numbers

7.5. More than Two Colors

8. Rapidly Growing Ramsey Functions

8.1. Hardy Hierarchy

8.2. Paris-Harrington's Unprovability Result

9. Product Theorems

9.1. Product Ramsey Theorem

9.2. Diversification

9.3. Product Erdos-Rado Theorem

10. Quasi Ramsey Theorem

10.1. Upper Bound

10.2. Lemma of Erdos

10.3. Lower Bound: The Graph Case

10.4. Lower Bound: The General Case

11. Partition Relations for Cardinal Numbers

11.1. Erdos-Rado's Partition Theorem for Cardinals

11.2. Negative Partition Relations

11.3. Dushnik-Miller's Theorem

11.4. Weakly Compact Cardinals

11.5. Canonical Partition Relations for Cardinals

pt. IV Graphs and Hypergraphs

12. Finite Graphs

12.1. Vertex Colorings

12.2. Colorings of Edges

12.3. Colorings of Subgraphs

12.4. Unbounded Colorings of Subgraphs

13. Infinite Graphs

13.1. Rado's Graph

13.2. Countable-Universal Kl-Free Graphs

13.3. Colorings of Edges

14. Hypergraphs on Parameter Sets

14.1. Induced Hales-Jewett Theorem

14.1.1. Applications

14.2. Colorings of Subgraphs: An Alternative Proof

14.2.1. Partite Graphs

14.2.2. Amalgamation of Partite Graphs

14.3. Induced Graham-Rothschild Theorem

14.3.1. Partite Hypergraphs

14.3.2. Amalgamation of Partite Graphs

14.3.3. Proof of the Induced Graham-Rothschild Theorem

15. Ramsey Statements for Random Graphs

15.1. Rodl-Rucinski's Theorem

15.2. Proof of the 1-Statement

15.3. Proof of the 0-Statement

16. Sparse Ramsey Theorems

16.1. Sparse Graphs and Hypergraphs

16.2. Sparse Ramsey Families

16.3. Arithmetic Structures

16.4. Parameter Sets

pt. V Density Ramsey Theorems

17. Szemeredi's Theorem

18. Density Hales-Jewett Theorem

18.1. Lines Imply Spaces

18.2. Boolean Case: Sperner's Lemma

18.3. General Case: Alphabets of Size k [≥] 3

18.3.1. Proof of Lemma 18.6

18.3.2. Proof of Lemma 18.7

18.3.3. Proof of Lemma 18.8.

Part I. Roots of Ramsey theory

Part II. A starting point of Ramsey theory: Parameter sets

Part III. Back to the roots: Sets

Part IV. Graphs and hypergraphs

Part V. Density Ramsey theorems

Notes:

Includes bibliographical references and index

Print version record

Other Format:

Print version Prömel, Hans Jürgen. Ramsey Theory for Discrete Structures

ISBN:

9783319013152

3319013157

3319013149

9783319013145

OCLC:

870244444

Publisher Number:

10.1007/978-3-319-01315-2

Access Restriction:

Restricted for use by site license