Combinatorial Theorems on Classifications of Subsets of a Given Set
Es sei \(\Omega_n(S)\) die Menge aller Teilmengen einer Menge \(S\), die genau \(n\) Elemente enthalten. F. P. Ramsey zeigte: Zu irgend drei natürlichen Zahlen \(k,n,N\) gibt es eine natürliche Zahl \(M\) derart, daß für \(S=\{1,2,...,M\}\) und irgendeine Verteilung \(\Delta\) von \(\Omega_n(S)\) in \(k\) Klassen stets ein Element \(S'\) von \(\Omega_n(S)\) existiert mit der Eigenschaft, daß die \({N \choose n}\) Elemente von \(\Omega_n(S')\) derselben Klasse von \(\Delta\) angehören. Verff. geben als erstes für das kleinste \(M\) dieser Art eine Abschätzung nach oben (Satz 1), die besser ist als die bisherigen und sich vor allem explizit durch algebraische Grundoperationen [\((n-1)\)-fache Potenzierung ] ausdrücken läßt. Weiter untersuchen sie bestimmte als invariant bzw. kanonisch bezeichnete Verteilungen von \(\Omega_n(S)\). In einer früheren Arbeit der Verff. (Zbl 0038.15301) wurde gezeigt, daß für \(S=\{1,2,3,...\}\) beide Arten von Verteilungen zusammenfallen. Hier ergibt sich, daß dies für endliche \(S\) nicht zutrifft, und es werden (Satz 2) notwendige und hinreichende Bedingungen für \(n\) und \(N\) angegeben, damit jede invariante Verteilung von \(\Omega_n\; (1,2,...,N)\) auch kanonisch ist. Mittels Satz 1 und Satz 2 gelingt (Satz 3) eine finite Fassung des von den Verff. a.a.O. verallgemeinerten Ramseyschen Satzes (Anzahl \(k\) der Klassen beliebig bei abzählbar unendlichen \(S\) und \(S'\)). Es folgt eine Ausdehnung der Untersuchungen für \(k=n=2\) ins Transfinite. Hier geht es z.B. um die Frage, ob bei vorgeschriebenem Ordnungstypus stets eine Menge \(X\) reeller Zahlen von diesem Typus existiert derart, daß eine der Klassen die Menge \(\Omega_2(X)\) enthält. Insbesondere ergibt sich (Satz 7), daß dies bei jedem Ordnungstypus \(\omega +m\) (\(m\) endlich) zutrifft. Andere Sätze deuten daraufhin, daß bei jeder Verteilung jede abzählbare Ordinalzahl in diesem Sinne verwirklicht werden könnte. Weiter wird durch Beispiele gezeigt, daß Ramseys Satz in gewissen Richtungen nicht zu verallgemeinern geht. Hier ergeben sich interessante, noch ungelöste Fragen. Als letztes wird eine Abschätzung nach unten angegeben für das kleinste (in einem Satz von van der Waerden auftretende) \(m=m(k,l)\) mit der Eigenschaft, daß bei jeder Verteilung von \(\{1,2,...,m\}\) in \(k\) Klassen mindestens eine Klasse eine arithmetische Progression von \(l+1\) Gliedern enthält.
- Combinatorial Dichotomies in Set Theory
- scientific article; zbMATH DE number 3675897
- Combinatorial set theory
- Combinatorics of set partitions
- Combinations of distinguished subsets and conullity
- Enumerative aspects of combinatorics of finite sets
- scientific article; zbMATH DE number 3974960
- scientific article; zbMATH DE number 1987942
- scientific article; zbMATH DE number 970812
- scientific article; zbMATH DE number 940705
- Phase transitions for Gödel incompleteness
- Van der Waerden and Ramsey type games
- Partition relations for partially ordered sets
- Values and bounds for Ramsey numbers associated with polynomial iteration
- Some applications of Ramsey's theorem to additive number theory
- A lower estimate for the achromatic number of irreducible graphs
- Analyzing Nash-Williams' partition theorem by means of ordinal types
- Partition theorems for factorizations of ascending parameter words
- Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
- A new lower bound for van der Waerden numbers
- Heterogeneous Ramsey algebras and classification of Ramsey vector spaces
- Set mappings on 4-tuples
- Variations on a game
- On Erdős-Rado numbers
- On partitioning integers into progression free sets
- A partition problem on colored sets
- Lower bounds for hypergraph Ramsey numbers
- Lower bounds on the clique-chromatic numbers of some distance graphs
- Ramsey degrees of ultrafilters, pseudointersection numbers, and the tools of topological Ramsey spaces
- The Erdős-Hajnal hypergraph Ramsey problem
- Two Erdős-Hajnal-type theorems in hypergraphs
- Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs
- Counting set classes with Burnside's lemma
- Off-diagonal hypergraph Ramsey numbers
- On colorings of variable words
- The dynamic descriptive complexity of k-clique
- Erdős-Hajnal conjecture for graphs with bounded VC-dimension
- Multicolor Ramsey numbers for triple systems
- Higher-order Erdős-Szekeres theorems
- 3-uniform hypergraphs of bounded degree have linear Ramsey numbers
- Combining monotonicity and strong equity: construction and representation of orders on infinite utility streams
- Ordinary partition relations for ordinal numbers
- Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results
- Phase transition results for three Ramsey-like theorems
- Transforming comparison model lower bounds to the parallel-random-access-machine
- Combinatorial Dichotomies in Set Theory
- Ramsey-type results for semi-algebraic relations
- A note on order-type homogeneous point sets
- PRIMITIVE RECURSIVE BOUNDS FOR THE FINITE VERSION OF GOWERS’ THEOREM
- A partition calculus in set theory
- On the structure of set-mappings
- Ramsey Games
- On edge-ordered Ramsey numbers
- Relationship between Kanamori-McAloon principle and Paris-Harrington theorem
- Hypergraph Ramsey numbers
- On the lower bound for the van der Waerden function
- Note on Canonical Partitions
- Primitive Recursive Bounds for Van Der Waerden Numbers
- Van der Waerden function and colorings of hypergraphs with large girth
- A Partition Theorem for the Infinite Subtrees of a Tree
- Two extensions of Ramsey's theorem
- On construction of equitable social welfare orders on infinite utility streams
- A note on induced Ramsey numbers
- Colourings of uniform hypergraphs with large girth and applications
- Refinement of homogeneity and Ramsey numbers
- scientific article; zbMATH DE number 4118364 (Why is no real title available?)
- On construction of social welfare orders satisfying Hammond equity and weak Pareto axioms
- Ramsey properties of algebraic graphs and hypergraphs
- STRUCTURAL CONSIDERATIONS OF RAMSEY ALGEBRAS
- A note on the Erdős-Hajnal hypergraph Ramsey problem
- On multicolor Ramsey numbers and subset coloring of hypergraphs
- Ramsey growth in some NIP structures
- A refinement of the Ramsey hierarchy via indescribability
- Proof of a conjecture of Galvin
- Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems
- On Ramsey numbers of hedgehogs
- Large almost monochromatic subsets in hypergraphs
- A canonical Ramsey-type theorem for finite subsets of \(\mathbb N\).
- On generalized Ramsey numbers for 3-uniform hypergraphs
- Partition relations for cardinal numbers
- A Combinatorial Theorem
- Ramsey numbers of sparse hypergraphs
- A two-coloring of Cartesian products
- Ramsey numbers of sparse hypergraphs
- Local approximation of the maximum cut in regular graphs
- Rainbow generalizations of Ramsey theory: A survey
- Tower Gaps in Multicolour Ramsey Numbers
- Ramsey numbers of semi-algebraic and semi-linear hypergraphs
- On 3‐graphs with no four vertices spanning exactly two edges
- Concentration estimates for functions of finite high‐dimensional random arrays
- Hypergraph Ramsey numbers of cliques versus stars
- On the canonical Ramsey theorem of Erdős and Rado and Ramsey ultrafilters
- On quantitative aspects of a canonisation theorem for edge‐orderings
- Erdős-Szekeres theorem for multidimensional arrays
- Sharp thresholds for hypergraph regressive Ramsey numbers
- Ramsey numbers of cliques versus monotone paths
- Two-cardinal ideal operators and indescribability
- The growth rate of multicolor Ramsey numbers of 3-graphs
- Conflict-free colouring of subsets
- On the degree of Boolean functions as polynomials over \(\mathbb{Z}_m\)
- Colorings of k-sets with low discrepancy on small sets
- Cofinal types of ultrafilters over measurable cardinals
- Borel sets of Rado graphs and Ramsey's theorem
- Happy families and completely Ramsey sets
- Induced subgraph density. VI: Bounded VC-dimension
- On Ramsey (2K₂, W_n)-minimal graphs of smallest order
- The generic multiverse is not going away
- Topological games in Ramsey spaces
- On the canonical Ramsey theorem of Erdős and Rado: a short proof using ultrafilter theory
- Semi-algebraic and semi-linear Ramsey numbers (extended abstract)
This page was built for publication: Combinatorial Theorems on Classifications of Subsets of a Given Set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5814905)