Teoria lui Ramsey
Teoria lui Ramsey , numită după Frank Plumpton Ramsey , este o ramură a matematicii discrete care se ocupă de probleme de formă: care sunt cele mai puține elemente necesare pentru ca o anumită proprietate să fie adevărată?
Exemple
Să presupunem, de exemplu, că n porumbei au fost plasați în m porumbei. Cât de mare are n trebuie să fie pentru a fi sigur că cel puțin o casa de porumbel contine cel putin doi porumbei? În mod clar, acest lucru se întâmplă cu certitudine numai dacă n > m . Teoria lui Ramsey este preocupată de generalizarea acestui principiu.
Un alt exemplu este teorema lui Ramsey . Se afirmă că, dacă colorăm un grafic complet suficient de mare cu un anumit număr (fix) de culori, acesta va conține un subgraf monocromatic (non-trivial) complet. De exemplu, dacă se aleg 2 culori, cum ar fi roșu și albastru, avem că pentru n ≥ 6 fiecare grafic complet cu n vârfuri conține cel puțin un triunghi (care nu este altceva decât un grafic complet cu 3 vârfuri) toate albastre sau toate roșu. O formă echivalentă și mai intuitivă a acestui caz este următorul fapt: într-o petrecere cu cel puțin șase persoane există întotdeauna cel puțin trei persoane care se cunosc (adică fiecare le cunoaște pe celelalte două) sau care nu se cunosc (adică fiecare nu-i cunoaște pe ceilalți doi).
Bibliografie
- R. Graham , B. Rothschild, JH Spencer , Ramsey Theory , John Wiley and Sons, New York (1990)
- Landman și A. Robertson, Teoria lui Ramsey asupra numerelor întregi , Biblioteca matematică a studenților Vol. 24, AMS (2004)
- FP Ramsey, Despre o problemă a logicii formale , Proc. London Math. Soc., Vol. S2-30, nr. 1 (1930),
- P. Erdös, G. Szekeres, O problemă combinatorie în geometrie , Compositio Math., Vol. 2, p. 463-470 (1935)
- G. Boolos, JP Burgess și R. Jeffrey, Computabilitate și logică , Cambridge: Cambridge University Press. (1974, revizuit 2004)
