Dimensione di un insieme parzialmente ordinato

Con questo lavoro si studia l'argomento della dimensione di un insieme parzialmente ordinato P, introdotta nel 1941 da Dushnik e Miller, tramite diagrammi di Hasse, in modo da avere una visione geometrica di un concetto algebrico. Il Teorema di Szpilrajn permette di linearizzare un qualsiasi insieme parzialmente ordinato P: questo anticipa la definizione di dimensione, siccome tutte le linearizzazioni sono realizzatori: le loro coppie comuni sono presenti anche in P. La dimensione viene definita come il minimo numero cardinale m di realizzatori per P. Vengono rivisti alcuni dei risultati già pubblicati da M. Barnabei, F. Bonetti e R. Pirastu e ripresi da M. Silimbani nella sua Tesi di Dottorato: ci si concentra sulla dimensione 2 in cui può essere definito un etichettamento doppio, che si può utilizzare per avere un algoritmo poco costoso atto a sapere se un insieme parzialmente ordinato ha dimensione 2 : esso pone le basi per una corrispondenza biunivoca tra un insieme parzialmente ordinato di cardinalità n dotato di un etichettamento doppio e l'insieme delle permutazioni su n elementi. Infine viene spiegato un altro modo per scoprire se un insieme parzialmente ordinato P ha dimensione al massimo 2 servendosi del solo diagramma di Hasse: ciò succede se e solo se il grafo di inconfrontabilità di P ammette un orientamento transitivo.