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$

closed as unclear what you're asking by Andrés E. Caicedo, Marco Golla, András Bátkai, Stefan Kohl, Chris Godsil Feb 5 '16 at 18:05

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What do you mean by Ramsey for sets? For hypergraphs? $\endgroup$ – Fedor Petrov 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$
  • $\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.