Don't take life too seriously: it's just a temporary situation

Ramsey orientati (numeri di)

Matematica combinatoria  Teoria dei grafi 

Per i grafi orientati, nei quali gli archi vanno pensati come cammini percorribli in un solo senso, vale un teorema analogo a quello di Ramsey (v. numeri di Ramsey): per ogni valore di n esiste un numero R’(n) tale che un grafo orientato completo con R’(n) nodi, colorato con due colori, contiene un sottografo aciclico completo di n nodi.

La tabella seguente riporta i valori noti di R’(n), che possiamo chiamare “numeri di Ramsey orientati”.

n

R’(n)

1

1

2

2

3

4

4

8

5

14

6

28

7

[32 .. 55]

 

Vedi anche

Numeri di Ramsey.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.