Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1990 | Buch

Introduction Ramsey Theory Old and New Kapitel lesen Erstes Kapitel lesen

Mathematics of Ramsey Theory

herausgegeben von: Jaroslav Nešetřil, Vojtěch Rödl

Verlag: Springer Berlin Heidelberg

Buchreihe : Algorithms and Combinatorics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Introduction Ramsey Theory Old and New

Introduction Ramsey Theory Old and New
Abstract
The purpose of this introduction is to outline scope and intentions of this volume. We also state some classical results. This historical perspective will be of some use to a (non-specialist) reader.
Jaroslav Nešetřil, Vojtěch Rödl

Classics

Frontmatter
Problems and Results on Graphs and Hypergraphs: Similarities and Differences
Abstract
Many papers and also the excellent book of Bollobás, recently appeared on extremal problems on graphs. Two survey papers of Simonovits are in the press and Brown, Simonovits and I have several papers, some appeared, some in the press and some in preparation on this subject.
Paul Erdös
Note on Canonical Partitions
Abstract
1. For every set X and every cardinal number r we put
$${\left[ X \right]^r} = \left\{ {P \subseteq X:|P| = r} \right\}.$$
Richard Rado

Numbers

Frontmatter
On Size Ramsey Number of Paths, Trees and Circuits. II
Abstract
In this paper we shall demonstrate that random graphs satisfy some interesting Ramsey type properties. This paper deals with finite, simple and undirected graphs only. If G and H are graphs, write G → H to mean that if the edges of G are coloured by two colours, then G contains a monochromatic copy of H.
József Beck
On the Computational Complexity of Ramsey—Type Problems
Abstract
If F, G and H are graphs, write F → (G, H) to mean that if the edges of F are colored red and blue, either a red G or a blue H must occur. It is shown that, if G and H are fixed 3-connected graphs (or triangles), then deciding whether F \(\not \to \) (G, H) is an NP-complete problem. On the other hand, if G and H are arbitrary stars, or if G is fixed matching and H is any fixed graph, the complexity of the problem is polynomial bounded.
Stefan A. Burr
Constructive Ramsey Bounds and Intersection Theorems for Sets
Abstract
A classical result of Erdös says that R(k, k)>2 k /2. However, Erdos’s proof is probabilistic, and the only known graphs showing that R(k, k) is greater than any polynomial of k were constructed via set-intersections. Here we show, that almost all such constructions yield non-polynomial lower bounds for R(k, k).
Peter Frankl
Ordinal Types in Ramsey Theory and Well-Partial-Ordering Theory
Abstract
There is a gap between the infinite Ramsey’s theorem ω → (ω) k n and its finite version
$$R\left( {n;{l_1}...,{l_k}} \right) \to \left( {{l_1}...,{l_k}} \right)_k^n.$$
Igor Kříž, Robin Thomas

Structural Theory

Frontmatter
Partite Construction and Ramsey Space Systems
Abstract
We prove several Ramsey type theorems for parameter sets, affine and vector spaces by an amalgamation technique known as Partite Construction. This approach yields solution of several open problems and uniform treatment of several strongest results in the area. Particularly we prove Ramsey theorem for systems of spaces.
Jaroslav Nešetřil, Vojtěch Rödl
Graham-Rothschild Parameter Sets
Abstract
In their, by now classical, paper ‘Ramsey’s theorem for n-parameter sets’ (Trans. Amer. Math. Soc. 159 (1971), 257–291) Graham and Rothschild introduced a combinatorial structure which turned out be central in Ramsey theory. In this paper we survey the development related to the structure of Graham-Rothschild parameter sets.
Hans J. Prömel, Bernd Voigt
Shelah’s Proof of the Hales-Jewett Theorem
Abstract
This communication contains a description of Shelah’s recent proof for the Hales-Jewett Theorem, in a condensed (and yet self contained) form. For simplicity we include here only the proof of the one dimensional case of the theorem, which solves a problem of Graham by showing that the Hales-Jewett function is primitive recursive. The general cases will appear in the full paper of Shelah.
Alon Nilli

Noncombinatorial Methods

Frontmatter
Partitioning Topological Spaces
Abstract
The study of partitions of topological spaces is a relatively new addition to Ramsey theory, but one which promises interesting things in the future. We partition topological spaces and hope to obtain a homogeneous set which is topologically relevant — for instance, a set homeomorphic to a well known topological space. We thus add something new to the ordinary partition calculus of set theory. We do, however, borrow the arrow notation. We write
$$X\, \to \,(Y)_\lambda ^n$$
to mean the following statement.
William Weiss
Topological Ramsey Theory
Abstract
We survey the interplay between topology and Ramsey Theory which began with Ellentuck’s Theorem (Ellentuck 1974) (and was anticipated by work of Nash-Williams (1965), Galvin and Prikry (1973) and Silver (1970) by giving a fairly abstract treatment of what have become known as Ellentuck type theorems.
Timothy J. Carlson, Stephen G. Simpson
Ergodic Theory and Configurations in Sets of Positive Density
Abstract
We shall present here two examples from “geometric Ramsey theory” which illustrate how ergodic theoretic techniques can be used to prove that subsets of Euclidean space of positive density necessarily contain certain configurations. Specifically we will deal with subsets of the plane, and our results will be valid for subsets of “positive upper density”.
Hillel Fürstenberg, Yitzchak Katznelson, Benjamin Weiss

Variations and Applications

Frontmatter
Topics in Euclidean Ramsey Theory
Abstract
Many questions in Ramsey Theory can be placed in the following context. We are given a set X, a family F of distinguished subsets of X, and a positive integer r. We would like to decide whether or not the following statement holds: For any partition of X = X 1 ∪…∪ X r into r classes, there is an F ∈ F and an index i such that F ⊆ X i .
Ronald L. Graham
On Pisier Type Problems and Results (Combinatorial Applications to Number Theory)
Abstract
Several number theoretical results are (sometimes a bit surprisingly) consequences of purely combinatorial statements. In this paper we deal with some of these results. Particularly we solve several problems related to Pisier-type problems.
Paul Erdös, Jaroslav Nešetřil, Vojtěch Rödl
Combinatorial Statements Independent of Arithmetic
Abstract
When Peano’s first order axioms of arithmetic (P) were originally formulated it was generally felt that these axioms summed up all that was obviously true about the natural numbers (ℕ) with addition and multiplication and that any true first order statement of arithmetic would follow from these axioms. This belief held sway until in 1931 Gödel exhibited a first order statement of arithmetic (or as we shall now call it an arithmetic statement) Θ G which was true but neither it nor its negation could be proved for P. That is Θ G was an arithmetic statement independent of arithmetic.
Jeff Paris
Boolean Complexity and Ramsey Theorems
Abstract
The aim of this paper is to bring attention to some connections between these two fields. In the complexity theory there are difficult open problems most of which are essentially of combinatorial character. It is generally believed that some interaction between complexity theory and combinatorics may help to solve these problems.
Pavel Pudlák
Uncrowded Graphs
Abstract
Turán’s Theorem provides a relation between the number of vertices n, the number of edges e, and the independence number α of a graph G. In the simplest case, when e = tn/2 and (t + 1)|n, Turan’s Theorem yields α ≥ n/(t +1). This inequality is best possible. An extremal graph is given by letting G be the union of n/(t + 1) vertex disjoint cliques, each on t + 1 vertices.
Joel Spencer
Backmatter
Metadaten
Titel
Mathematics of Ramsey Theory
herausgegeben von
Jaroslav Nešetřil
Vojtěch Rödl
Copyright-Jahr
1990
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-72905-8
Print ISBN
978-3-642-72907-2
DOI
https://doi.org/10.1007/978-3-642-72905-8