Metraipolis › archive › dc_3951fda2bafe

Ramsey's theorem — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Ramsey%27s_theorem
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T13:03:46.582Z
SHA-256 of the archived text
8dba5f7d9334f3d04b21f061702a5d97aab5bfdc84e9b9b04de2f4d08214a03e
Stable URL of this page
https://metraipolis.com/documento/dc_3951fda2bafe

How to cite

Ramsey's theorem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Ramsey%27s_theorem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_3951fda2bafe (Metraipolis archive dc_3951fda2bafe, sha256 8dba5f7d9334f3d04b21f061702a5d97aab5bfdc84e9b9b04de2f4d08214a03e)
BibTeX
@misc{dc3951fda2bafe,
  title = {Ramsey's theorem — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Ramsey%27s_theorem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_3951fda2bafe; sha256 8dba5f7d9334f3d04b21f061702a5d97aab5bfdc84e9b9b04de2f4d08214a03e},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Ramsey%27s_theorem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. As the simplest example, consider two colours (say, blue and red). Let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.) Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by Frank Ramsey. This initiated the combinatorial theory now called Ramsey theory, that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of monochromatic subsets, that is, subsets of connected edges of just one colour. An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colours, c, and any given integers n1, …, nc, there is a number, R(n1, …, nc), such that if the edges of a complete graph of order R(n1, …, nc) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all colour i. The special case above has c = 2 (and n1 = r and n2 = s).

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «combinatorics»).
Fonte: Wikipedia in inglese, voce «Ramsey's theorem» — https://en.wikipedia.org/wiki/Ramsey%27s_theorem
Wikidata Q918099 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q918099
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Ramsey%27s_theorem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1373140603, consultata il 2026-10-07T12:34:31.958Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e41ed5ce50400ac7d7cae5716f6cf8f2faabc2f1697aafb3b55b302f0403d7c4