Esercizio - triangoli, vertici isolati e cricche in un grafo casuale

Soluzione

In tutti i casi si scrive il conteggio come somma di indicatrici, una per oggetto possibile, e si somma la probabilità di ciascuna. Gli eventi sono dipendenti (due triangoli possono condividere un arco), ma non importa.

1. Archi. $\binom{10}2=45$ coppie, ciascuna con probabilità $0{,}3$: $45\cdot0{,}3=13{,}5$.

2. Triangoli. Le terne di vertici sono $\binom{10}3=120$. Una terna è un triangolo se i suoi $3$ archi ci sono tutti, con probabilità $p^3=0{,}027$ (indipendenza degli archi). Quindi $E=120\cdot0{,}027=3{,}24$. In generale $\binom n3p^3$.

3. Vertici isolati. Un vertice è isolato se nessuno dei suoi $n-1=9$ archi è presente: probabilità $(1-p)^9=0{,}7^9=0{,}04035$. Per $10$ vertici $E=10\cdot0{,}04035\approx0{,}4035$.

Cammini a V. Si sceglie il vertice centrale ($10$ modi) e due suoi vicini tra gli altri $9$ ($\binom92=36$ modi): $360$ configurazioni, ciascuna con probabilità $p^2=0{,}09$ (due archi). $E=360\cdot0{,}09=32{,}4$.

4. $K_4$. Gruppi di quattro vertici: $\binom{10}4=210$; ciascuno richiede $\binom42=6$ archi: $p^6=0{,}3^6=0{,}000729$. $E=210\cdot0{,}000729\approx0{,}1531$. Sia $X$ il numero di $K_4$. Poiché $X$ è intera e non negativa, $P(X\ge1)\le E[X]\approx0{,}153$ (disuguaglianza di Markov). Quindi in $G(10,0{,}3)$ un grafo senza alcun $K_4$ compare con probabilità almeno $0{,}847$, e in particolare ne esiste uno: è la base del metodo probabilistico (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 →).

5. Simulazione.

import numpy as np, itertools
rng = np.random.default_rng(1)
T = 20000; tri = iso = 0
for _ in range(T):
    A = np.triu(rng.random((10, 10)) < 0.3, 1); A = (A | A.T).astype(int)
    tri += np.trace(np.linalg.matrix_power(A, 3)) // 6    # ogni triangolo conta 6 volte
    iso += int((A.sum(1) == 0).sum())
print(tri / T, iso / T)    # circa 3.24 e 0.40

Risultato. Archi $13{,}5$; triangoli $\binom{10}3p^3=3{,}24$; vertici isolati $10\cdot0{,}7^9\approx0{,}4035$; cammini a V $32{,}4$; $K_4$ $\approx0{,}153$ (quindi $P(\text{almeno un }K_4)\le0{,}153$).

Verifica Python: valori esatti dalle formule e simulazione con $40\,000$-$50\,000$ grafi: archi $13{,}48$, triangoli $3{,}23$, vertici isolati $0{,}402$, cammini a V $32{,}29$, $K_4$ $0{,}148$.