COMBINATORIA

Claudia Malvenuto – Daniele A. Gewurz Scheda di esercizi n. 8

1. Si pongano

N(k, k) := max{|V (G)| : G grafo, α(G) < k e ω(G) < k}

e

R(k, k) := min{n ∈ ℕ : per ogni G con |V (G)| = n, α(G) ≥ k oppure ω(G) ≥ k}.

Dimostrare che N(k, k) = R(k, k) − 1.

2. Calcolare R(3, 3).

3. Supponiamo che a una cena i commensali siano seduti a un tavolo rotondo. Se vi sono dei segnaposto con scritti i loro nomi, e nessuno è seduto davanti al proprio nome, è possibile ruotare il tavolo in modo che almeno due persone siano sedute davanti al proprio nome?

4. Dimostrare per induzione il “principio dei cassetti” (detto anche principio di Dirichlet; pigeonhole principle in inglese): se si hanno m oggetti da distribuire tra n cassetti e m > n, allora in almeno un cassetto ci sarà più di un oggetto.

5. Dimostrare le seguenti varianti del principio dei cassetti.

(a) Se m > n, non esistono funzioni iniettive da [m] a [n].

(b) Data comunque una partizione di un insieme di cardinalità maggiore di kn in n classi, c’è una classe contenente più di k oggetti.

(c) [Principio di Fubini] Se ogni cassetto contiene in media p oggetti, allora c’è almeno un cassetto con almeno p oggetti e almeno un cassetto con al più p oggetti.

6. Dimostrare che in ogni grafo vi sono due vertici con lo stesso grado.

7. Coloriamo i punti del piano con due colori; dimostrare che esiste un rettangolo coi vertici dello stesso colore.

8. (a) Dimostrare con il principio dei cassetti che comunque si scelgano n+1 interi distinti compresi tra 1 e 2n: i. ce ne sono due consecutivi; ii. ce ne sono due la cui somma è 2n + 1; iii. ce ne sono due la cui somma è dispari; iv. ce ne sono due primi tra loro (cioè il cui M.C.D. è 1); v. ce ne sono due uno dei quali è multiplo dell’altro. (Suggerimento: ogni intero è della forma 2^{k}h con k ≥ 0 e h dispari; allora, per ogni intero dispari h, si può definire un cassetto che…).

(b) Per ognuna di queste proprietà, mostrare esplicitamente un insieme di n interi in {1, 2, …, 2n} che non la possiede.

9. [Teorema di Erdős-Szekeres] Sia A = (a_{1}, …, a_{n}) una successione di n numeri reali distinti. Se n ≥ sr + 1 allora A contiene una sottosuccessione crescente di s+1 termini o una sottosuccessione decrescente di r+1 termini (o entrambe).

(Suggerimento: per ogni a_{i}, si consideri la coppia di numeri (x_{i}, y_{i}), dove x_{i} è la lunghezza della più lunga sottosuccessione crescente che finisce con a_{i}, e y_{i} quella della più lunga sottosuccessione decrescente che comincia con a_{i}. Ci interessano sr di queste coppie (x_{i}, y_{i})…)