Logical methods in combinatorics - Finanziamento dell’Unione Europea – NextGenerationEU – missione 4, componente 2, investimento 1.1.

Il nostro progetto di ricerca è incentrato sull'interazione tra logica matematica e combinatoria. Le connessioni tra queste due aree sono state storicamente fondamentali per molti dei loro sviluppi; probabilmente, l'esemplificazione più famosa di questo fatto è il teorema di Ramsey. Il nostro gruppo di ricerca è composto da quattro unità di ricerca (Milano, Roma, Torino, Pisa) e da 11 membri, che vanno da dottorandi a professori associati, ognuno con un forte background sugli argomenti specifici del progetto. Per portare avanti il progetto assumeremo inoltre due ricercatori post-doc e organizzeremo la quarta edizione del workshop internazionale "RaTLoCC: Ramsey Theory in Logic, Combinatorics and Complexity". Abbiamo in programma di approfondire cinque diverse linee di ricerca. La prima linea riguarda la cosiddetta Teoria di Ramsey aritmetica, ovvero la regolarità di partizione delle configurazioni combinatorie sugli interi, un argomento che ha attirato l'interesse della comunità matematica negli ultimi anni. Ci concentreremo su problemi specifici riguardanti le configurazioni polinomiali ed esponenziali, sui numeri naturali e sulle strutture astratte. La seconda linea riguarda la forza logico-computazionale del Teorema di Hindman (HT). Questo teorema è caratterizzato da una profonda interazione di metodi logici, computazionali e combinatori. In particolare, si prevede di studiare la forza (nel senso della matematica inversa e computabile) di alcune restrizioni e di alcune versioni finite di HT, e il ruolo della condizione di apartitudine. La terza linea riguarda le densità e le misure di Keisler. Si tratta di misure finitamente additive su algebre di insiemi definibili. I campioni di Loeb saranno il nostro strumento principale. In primo luogo confronteremo le proprietà dei campioni di Loeb con le proprietà note delle misure di Keisler e poi studieremo le applicazioni alla combinatoria, comprese le estensioni della famosa proprietà B+C degli insiemi di densità positiva. La quarta linea riguarda i quasi-ordini e le loro applicazioni; si tratta di un'area ricca di problemi aperti con ramificazioni in una vasta gamma di settori, tra cui la matematica inversa, la teoria di Ramsey e il model checking. Abbiamo in programma di studiare i minori dei grafi, gli α-miglior quasi-ordini e le proprietà di conservazione dei miglior quasi-ordini. La quinta linea è incentrata sullo studio dei limiti computazionali della dimostrabilità finita, analizzando la complessità della dimostrazione di enunciati combinatori in diversi sistemi di dimostrazione logica. La complessità della prova è la nostra linea guida. Si tratta di un'area di ricerca centrale al confine tra logica, combinatoria e complessità, che mira principalmente a risolvere il problema se NP è uguale a P. La sua questione principale è dimostrare che ogni sistema di dimostrazione fallisce nel dimostrare in modo efficiente almeno una famiglia di teoremi e si basa su tecniche tratte dalla logica, dalla combinatoria e dalla teoria della complessità. Esploreremo la complessità dei sistemi di dimostrazione e delle procedure di dimostrazione dei teoremi, concentrandoci sulla loro classificazione in base alla loro forza di dimostrabilità e sullo sviluppo di nuovi metodi logico-combinatori per ottenere nuovi limiti inferiori per i limiti di dimostrabilità.