Geometria combinatoria

Con il termine geometria combinatoria (o geometria combinatorica) si intende il settore della matematica che studia insiemi finiti di oggetti semplici (interi, stringhe, nodi e collegamenti, punti e linee, configurazioni discrete, insiemi finiti, ...) che soddisfano proprietà ben definite e tendenzialmente semplici. Esempi di collezioni di oggetti studiate nell'ambito della geometria combinatoria sono:

• le permutazioni di n oggetti,
• le combinazioni con ripetizione di 5 dei primi 7 interi,
• i grafi poliedrali,
• i quadrati magici e i quadrati latini.

La geometria combinatoria si propone di studiare sul piano matematico le situazioni pratiche ed i relativi problemi i cui aspetti essenziali si possono esprimere con modelli discreti. Alcuni esempi di queste situazioni sono:

• le disposizioni delle persone intorno ad un tavolo circolare,
• le estrazioni di palline di colori diversi da un'urna,
• le disposizioni dei pezzi del gioco degli scacchi su una scacchiera,

Un aspetto di primaria importanza in questi studi riguarda l'enumerazione delle configurazioni: per alcuni esempi di questa problematica si vedano ad esempio fattoriale, coefficiente binomiale, numeri di Catalan e numeri di Fibonacci. Un altro aspetto fondamentale della combinatoria è quello algoritmico: innanzi tutto la conoscenza delle caratteristiche combinatorie di un tipo di configurazioni è essenziale per individuare i meccanismi che consentano di manipolarle; inoltre ogni algoritmo può essere oggetto di indagini combinatorie, come quelle di natura enumerativa richieste per valutare la sua efficienza.

T-disegni e BIBD

Un $t-(v,k,\lambda )$-disegno con $t\leq k\leq v$ è una coppia ordinata $(''V'',''B'')$ in cui V è un insieme di cardinalità $v>0$ di elementi detti vertici o punti e B è una famiglia di parti di V ciascuna di cardinalità k dette blocchi e non necessariamente distinte con la proprietà che ciascuna t-upla di vertici è contenuta in esattamente $\lambda$ blocchi. Ad un $t-(v,k,\lambda )$-disegno si può associare una matrice detta di incidenza $A=(a_{ij})$ dove $a_{ij}=1$ se il blocco j contiene il vertice i e $a_{ij}=0$ altrimenti.

Un $t-(v,k,\lambda )$-disegno con t = 2 e k < v si chiama $(v,k,\lambda )$ BIBD o $(v,k,\lambda )$ disegno. Un disegno con blocchi di cardinalità $k_{1},k_{2},\ldots ,k_{n}$ si chiama $(v,\{k_{1},k_{2},\ldots ,k_{n}\},\lambda )$ PBD.