Filling cages: reverse mathematics and combinatorial principles

In the thesis some combinatorial statements are analysed from the reverse mathematics point of view. Reverse mathematics is a research program, which dates back to the Seventies, interested to find the exact strength, measured in terms of set-existence axioms, of theorems from ordinary non set-theoretic mathematics. --- After a brief introduction to the subject, an on-line (incremental) algorithm to transitivelly reorient infinite pseudo-transitive oriented graphs is defined. This implies that a theorem of Ghouila-Houri is provable in RCA0 and hence is computably true. --- Interval graphs and interval orders are the common theme of the second part of the thesis. A chapter is devoted to analyse the relative strength of different characterisations of countable interval graphs and to study the interplay between countable interval graphs and countable interval orders. In this context arises the theme of unique orderability of interval graphs, which is studied in the following chapter. The last chapter about interval orders inspects the strength of some statements involving the dimension of countable interval orders. --- The third part is devoted to the analysis of two theorems proved by Rival and Sands in 1980. The first principle states that each infinite graph contains an infinite subgraph such that each vertex of the graph is adjacent either to none, or to one or to infinitely many vertices of the subgraph. This statement, restricted to countable graphs, is proved to be equivalent to ACA0 and hence to be stronger than Ramsey's theorem for pairs, despite the similarity of the two principles. The second theorem proved by Rival and Sands states that each infinite partial order with finite width contains an infinite chain such that each point of the poset is comparable either to none or to infinitely many points of the chain. For each k greater or equal to three, the latter principle restricted to countable poset of width k is proved to be equivalent to ADS. Some complementary results are presented in the thesis.

Nella tesi sono analizzati alcuni principi di combinatorica dal punto di vista della reverse mathematics. La reverse mathematics è un programma di ricerca avviato negli anni settanta e interessato a individuare l'esatta forza, intesa come assiomi riguardanti l'esistenza di insiemi, di teoremi della matematica ordinaria. --- Dopo una concisa introduzione al tema, è presentato un algoritmo incrementale per reorientare transitivamente grafi orientati infiniti e pseudo-transitivi. L'esistenza di tale algoritmo implica che un teorema di Ghouila-Houri è dimostrabile in RCA0. --- Grafi e ordini a intervalli sono la comune tematica della seconda parte della tesi. Un primo capitolo è dedicato all'analisi di diverse caratterizzazioni di grafi numerabili a intervalli e allo studio della relazione tra grafi numerabili a intervalli e ordini numerabili a intervalli. In questo contesto emerge il tema dell'ordinabilità unica di grafi a intervalli, a cui è dedicato il capitolo successivo. L'ultimo capitolo di questa parte riguarda invece enunciati relativi alla dimensione degli ordini numerabili a intervalli. --- La terza parte ruota attorno due enunciati dimostrati da Rival e Sands in un articolo del 1980. Il primo teorema afferma che ogni grafo infinito contiene un sottografo infinito tale che ogni vertice del grafo è adiacente ad al più uno o a infiniti vertici del sottografo. Si dimostra che questo enunciato è equivalente ad ACA0, dunque più forte rispetto al teorema di Ramsey per coppie, nonostante la somiglianza dei due principi. Il secondo teorema dimostrato da Rival e Sands asserisce che ogni ordine parziale infinito con larghezza finita contiene una catena infinita tale che ogni punto dell'ordine è comparabile con nessuno o con infiniti elementi della catena. Quest'ultimo enunciato ristretto a ordini di larghezza k, per ogni k maggiore o uguale a tre, è dimostrato equivalente ad ADS. Ulteriori enunciati sono studiati nella tesi.