Seminario
Interdipartimentale di Algoritmica
Lunedì 19 Gennaio 2001 ore 12:00
Sul disordine nelle grandi famiglie
Prof. Janos Korner
Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, II piano
Aula C2
Abstract:
Consideriamo degli insiemi sempre più grandi di stringhe binarie di
lunghezza n e osserviamo che inevitabilmente, in essi appaiono sempre di
più delle piccole configurazioni ``indesiderate'' di 3 stringhe. Le
piccole configurazioni da evitare saranno, di volta in volta:
-
tre stringhe senza una coordinata con esattamente due bits uguali a 1
(famiglie di insiemi senza girasole o``strong Delta--systems'',
Erdos--Szemeredi, (1978))
-
tre stringhe senza l diverse colonne di coordinate, per 3< l e in
particolare per l=8 (famiglie di bipartizioni qualitativamente indipendenti
a tre, Kleitman--Spencer (1973))
Utilizzando la tecnica di costruzione ad ``intreccio'' di Gargano, Korner
e Vaccaro (JCT Ser. A, 1994) il relatore e A. Monti mostrano che la prima
e la seconda configurazione (per l=6) appaiono alla stessa soglia
esponenziale di crescita. L'obiettivo del seminario è di spiegare la
tecnica per intrecciare costruzioni arbitrarie che rispettano diversi
vincoli in una sola nuova costruzione che soddisfa tutti i vincoli
considerati. Le grandi famiglie di partizioni qualitativamente
indipendenti sono applicate in informatica per approssimare in miniatura
determinati spazi di probabilità, per il testing di circuiti elettrici e
nell'ambito di architetture fault--tolerant di processori.