Esercizio - Limiti inferiori dei numeri di Ramsey con il metodo probabilistico

Teoria: Metodo probabilistico - valore atteso, alterazioni e derandomizzazioneMetodo probabilistico: se un oggetto casuale ha una proprietà con probabilità positiva (o una variabile ha media mu, quindi qualche esito la raggiunge) allora l'oggetto esiste; taglio di almeno |E|/2, MAX-SAT con 7/8, limite inferiore di Ramsey R(k,k) > 2^(k/2), alterazioni (insiemi indipendenti, Ramsey), derandomizzazione con le aspettative condizionate, lemma locale di Lovász solo enunciato.Metodo probabilistico - valore atteso, alterazioni e derandomizzazione → (limite inferiore di Ramsey, alterazione), Calcolo combinatorio per la probabilitàNegli spazi uniformi bisogna contare: principio di moltiplicazione, disposizioni con ripetizione n^k, disposizioni semplici n!/(n−k)!, permutazioni n!, combinazioni (n su k); estrazioni con e senza reinserimento e distribuzione ipergeometrica.Calcolo combinatorio per la probabilità →.

Testo. Il numero di Ramsey $R(k,k)$ è il minimo $n$ tale che ogni colorazione degli archi di $K_n$ con due colori contiene un $K_k$ monocromatico.

1. Dimostrare che se $\binom nk2^{1-\binom k2}<1$ allora $R(k,k)>n$.
2. Per $k=3,\dots,10$ calcolare il massimo $n$ per cui la condizione vale, e confrontarlo con $\lfloor2^{k/2}\rfloor$.
3. Dimostrare che $\lfloor2^{k/2}\rfloor$ soddisfa la condizione per ogni $k\ge3$.
4. Con l'alterazione (si toglie un vertice per ogni $K_k$ monocromatico) si ottiene $R(k,k)>n-\binom nk2^{1-\binom k2}$. Calcolare per $k=3,\dots,10$ il valore migliore.
5. Per $k=4$, $n=6$ contare tutte le $2^{15}$ colorazioni di $K_6$ senza $K_4$ monocromatico; per $k=5$, $n=11$ stimare con una simulazione la frazione di colorazioni senza $K_5$ monocromatico. Confrontare con l'attesa.

Soluzione

1. Dimostrazione. Si colora ogni arco di $K_n$ in rosso o blu con probabilità $\frac12$, indipendentemente. Fissato un insieme $S$ di $k$ vertici, i suoi $\binom k2$ archi sono tutti rossi con probabilità $2^{-\binom k2}$ e tutti blu con la stessa probabilità, quindi $S$ è monocromatico con probabilità $2\cdot2^{-\binom k2}=2^{1-\binom k2}$ (i due eventi sono disgiunti). Sia $X$ il numero di $k$-insiemi monocromatici: per la linearità $E[X]=\binom nk2^{1-\binom k2}<1$. Se ogni colorazione avesse $X\ge1$ la media sarebbe $\ge1$: esiste quindi una colorazione con $X=0$, cioè senza $K_k$ monocromatici, e $R(k,k)>n$.

2. Tabella. Il massimo $n$ con $E[X]<1$ e il valore di $E[X]$ in quel punto:

Esempi: $k=4$: $\binom64/2^5=\frac{15}{32}=0{,}469<1$ ma $\binom74/32=\frac{35}{32}>1$, quindi $n=6$. $k=5$: $\binom{11}5/2^9=\frac{462}{512}=0{,}902$; $\binom{12}5=792>512$. Il massimo $n$ è molto più grande di $2^{k/2}$ (a $k=10$ è $100$ contro $32$).

3. $\lfloor2^{k/2}\rfloor$ va bene. Con $n=\lfloor2^{k/2}\rfloor\le2^{k/2}$ e $\binom nk\le\frac{n^k}{k!}\le\frac{2^{k^2/2}}{k!}$: $$\binom nk2^{1-\binom k2}\le\frac{2^{k^2/2}\cdot2^{1-k(k-1)/2}}{k!}=\frac{2^{k/2+1}}{k!}.$$ Questo vale $\frac{2^{2{,}5}}6=0{,}943$ per $k=3$, $\frac{2^3}{24}=0{,}333$ per $k=4$, $0{,}094$ per $k=5$, ed è decrescente: $\frac{2^{(k+1)/2+1}}{(k+1)!}\Big/\frac{2^{k/2+1}}{k!}=\frac{\sqrt2}{k+1}<1$. Quindi $<1$ per ogni $k\ge3$ e $R(k,k)>\lfloor2^{k/2}\rfloor$. (Verifica diretta con numeri esatti per $k=3,\dots,79$.)

4. Alterazione. Dopo la colorazione casuale con $n$ vertici si toglie un vertice da ogni $K_k$ monocromatico: restano almeno $n-X$ vertici, senza $K_k$ monocromatici. In media $n-E[X]$; esiste una scelta con almeno $\lceil n-E[X]\rceil$ vertici rimasti, quindi $R(k,k)>\lceil n-E[X]\rceil$. Il massimo su $n$:

Per $k\le5$ l'alterazione non aiuta (stesso valore del metodo semplice: $3,6,11$); per $k\ge6$ guadagna $1,2,5,9,16$ sul massimo $n$ del punto 2. Per $k=10$: $116$ contro $100$, contro $32$ della formula $2^{k/2}$.

5. Conteggi esatti e simulazione.

• $k=4$, $n=6$: delle $2^{15}=32\,768$ colorazioni, $22\,484$ ($68{,}6\%$) non hanno $K_4$ monocromatici. L'attesa $E[X]=0{,}469<1$ garantisce soltanto una frazione $\ge1-E[X]=53{,}1\%$ (Markov): il valore vero è più grande.
• $k=5$, $n=11$: $3000$ colorazioni casuali hanno in media $0{,}87$ $K_5$ monocromatici (attesa $0{,}902$) e il $61{,}5\%$ ne ha zero (Markov garantisce $\ge1-0{,}902=9{,}8\%$). Per $k$ piccolo il limite probabilistico è debole (si sa che $R(5,5)\ge43$ per costruzioni esplicite): il suo interesse è la crescita esponenziale in $k$.

Codice di verifica

import itertools, math, random
from math import comb

for k in range(3, 11):
    nmax = max(n for n in range(k, 500) if comb(n, k) < 2 ** (comb(k, 2) - 1))
    alt = max((n - comb(n, k) / 2 ** (comb(k, 2) - 1), n) for n in range(k, 500))
    print(k, nmax, round(comb(nmax, k) / 2 ** (comb(k, 2) - 1), 4), math.isqrt(2 ** k),
          alt[1], round(alt[0], 2), math.ceil(alt[0]))

def mono(n, k, col):
    return sum(len({col[x] for x in itertools.combinations(S, 2)}) == 1
               for S in itertools.combinations(range(n), k))

archi = list(itertools.combinations(range(6), 2))
buone = sum(mono(6, 4, {e: (m >> i) & 1 for i, e in enumerate(archi)}) == 0 for m in range(1 << 15))
print(buone, buone / (1 << 15))

random.seed(3)
n, k, T = 11, 5, 3000
sub = [list(itertools.combinations(S, 2)) for S in itertools.combinations(range(n), k)]
tot = zero = 0
for _ in range(T):
    col = {e: random.getrandbits(1) for e in itertools.combinations(range(n), 2)}
    c = sum(len({col[x] for x in pr}) == 1 for pr in sub)
    tot += c
    zero += c == 0
print(tot / T, zero / T, comb(n, k) / 2 ** 9)

Risultato: otto righe k nmax E[X] floor n_alt n-E[X] ceil come nelle tabelle (per $k=10$: 10 100 0.984 32 127 115.11 116), poi 22484 0.6862, poi 0.8717 0.6147 0.9023.