1
$\begingroup$

i am searching for an on- line paper or a book, or maybe just a paper or a book which consists a proof of finite Ramsey's theorem for sets (not for graphs). i need a combinatorial proof which is not written as a consenquence of the infinite Ramsey's theorem. i know that such paper exits because i have had it few years ago, but i can't remember the name of the paper or the author.

$\endgroup$
4
  • $\begingroup$ What do you mean by Ramsey for sets? For hypergraphs? $\endgroup$ Feb 5 '16 at 10:53
  • $\begingroup$ no. it is not in the language of graphs. $\endgroup$
    – Ana
    Feb 5 '16 at 11:28
  • $\begingroup$ Would you please state the form of Ramsey's theorem you want proved? As for the classical finite Ramsey theorem that was already proved (not as a consequence of the infinite Ramsey theorem) in Ramsey's original 1930 paper. $\endgroup$
    – bof
    Feb 5 '16 at 11:35
  • $\begingroup$ For all natural numbers e, r and k there exists a recursive function R(e,r,k) so that for all M subsets of N such that size of M is greater or equal to R(e,r,k) and all subsets of M of size e are coloured with one of r colours, there is a subset H (of M) of size k such that all e- sized subsets of H are coloured with the same colour.... it can be said in the language of tje hypergraphs, but i need a combinatorial proof for the statement stated as above. $\endgroup$
    – Ana
    Feb 5 '16 at 11:39
1
$\begingroup$

The proof that Ramsey gives in 'On a problem of formal logic' (Theorem B) does not use the infinite version. In 'Ein kombinatorischer Satz mit Anwendung auf ein logisches Entscheidungsproblem' Skolem gives a simpler proof (in German, though). Since this is the classical Ramsey Theorem, references and proofs can certainly be found in almost any book containing the name 'Ramsey' in its title.

$\endgroup$
1
  • $\begingroup$ thank you, i have found the theorem B. but i need a specific proof of a two colour problem: finding R(e,2, k1, k2)- means there exits H1 of the size k1 with all of the e- subsets coloured with the first colour or H2 of the size k2 with all of it's subsets coloured with the second colour. i am proving finite Ramsey theorem using this particular theorem as this is part of my thesis. i was writing this part of the thesis years ago an i can't remember the source but some parts of my prior work are uncomplete and not 100% accurate, Ramsey original paper is quite different than version i have to do. $\endgroup$
    – Ana
    Feb 5 '16 at 14:51
0
$\begingroup$

Douglas West - Introduction to graph theory, Theorem 8.3.7. It is Ramsey's theorem for sets, in the form $R(e, p_1, ..., p_k)$. That is, for all sets $N$ with size at least $R(e, p_1, ..., p_k)$, and all colorings of the $e$-subsets of $N$, there exists an i, and a set M of size p_i, such that all the $e$-subsets of $M$ get color $i$. However the actual proof only does $R(e, p_1, p_2)$, which appears to be what you are looking for.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.