Results 1 to 10 of about 1,180 (130)

Ramsey's Theorem for a Class of Categories. [PDF]

Proc Natl Acad Sci U S A, 1972
Ramsey's Theorem states that for a sufficiently large set S , and for any splitting of the k -element subsets of S into r classes, there is a subset T [unk] S , [unk] T [unk]
Graham RL, Leeb K, Rothschild BL.
europepmc   +8 more sources

Is Ramsey's theorem omega-automatic?

, 2009
We study the existence of infinite cliques in omega-automatic (hyper-)graphs. It turns out that the situation is much nicer than in general uncountable graphs, but not as nice as for automatic graphs. More specifically, we show that every uncountable omega-automatic graph contains an uncountable co-context-free clique or anticlique, but not necessarily
Dietrich Kuske
core   +9 more sources

An additive version of Ramsey's theorem [PDF]

Journal of Combinatorics, 2012
We show that, for every $r, k$, there is an $n = n(r,k)$ so that any $r$-coloring of the edges of the complete graph on $[n]$ will yield a monochromatic complete subgraph on vertices ${a + \sum_{i \in I} d_i \mid I \subseteq [k]}$ for some choice of $a, d_1,..., d_k$. In particular, there is always a solution to $x_1 + ... + x_\ell = y_1 + ... + y_\ell$
Andy Parrish
openalex   +5 more sources

On the Strength of Ramsey's Theorem [PDF]

Notre Dame Journal of Formal Logic, 1995
We show that, for every partition F of the pairs of natural numbers and for every set C, if C is not recursive in F then there is an infinite set H, such that H is homogeneous for F and C is not recursive in H. We conclude that the formal statement of Ramsey's Theorem for Pairs is not strong enough to prove $ACA_0$, the comprehension scheme for ...
David Seetapun, Theodore A. Slaman
openalex   +3 more sources

Ramsey's Theorem [PDF]

Formalized Mathematics, 2008
Summary. The goal of this article is to formalize two versions of Ramsey’s theorem. The theorems are not phrased in the usually pictorial representation of a coloured graph but use a set-theoretic terminology. After some useful lemma, the second section presents a generalization of Ramsey’s theorem on infinite set closely following the book [9].
Marco Riccardi
openalex   +4 more sources

Stable Ramsey's theorem and measure [PDF]

Notre Dame Journal of Formal Logic, 2010
The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are non-null in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for non-
Damir D. Dzhafarov
  +8 more sources

Using Ramsey's Theorem Once [PDF]

Archive for Mathematical Logic, 2016
We show that RT(2,4) cannot be proved with one typical application of RT(2,2) in an intuitionistic extension of RCA0 to higher types, but that this does not remain true when the law of the excluded middle is added. The argument uses Kohlenbach's axiomatization of higher order reverse mathematics, results related to modified reducibility, and a ...
Jeffry L. Hirst, Carl Mummert
openalex   +5 more sources

An Application of Ramsey's Theorem [PDF]

Canadian Mathematical Bulletin, 1970
By an r-graph, we mean a finite set V of elements called vertices and a collection of some of the r-subsets of V called edges with the property that each vertex is incident with at least one edge. An A-chromatic r-graph is an r-graph all of whose edges are coloured A.Theorem. Let G1, …, Gt denote r-graphs.
E. J. Cockayne
openalex   +3 more sources

Two remarks on Ramsey's theorem

Discrete Mathematics, 1985
AbstractWe present a very simple proof of the fact (due to P. Erdös and R. Rado) that Ramsey's theorem doesn't hold for partitions of infinite subsets. We also present a proof of an induced Ramsey theorem for partitions of complete subgraphs (due to W. Deuber and authors) based on the theorem of R. Graham and B. Rothschild on parameter sets.
Jaroslav Nešetřil, Vojtěch Rödl
openalex   +3 more sources

On a topological Ramsey theorem [PDF]

Canadian Mathematical Bulletin, 2022
AbstractWe introduce natural strengthenings of sequential compactness, the r-Ramsey property for each natural number $r\geq 1$ . We prove that metrizable compact spaces are r-Ramsey for all r and give examples of compact spaces that are r-Ramsey but not $(r+1)$ -Ramsey for each $r\geq 1$ (assuming Continuum Hypothesis (CH) for all $r>1 ...
Wiesław Kubiś, Paul Szeptycki
openaire   +2 more sources