The study of duality relationships between finite graphs has reached very satisfactory results that have allowed a deeper knowledge of these mathematical structures. The same can be said for the phenomenon of duality between finite matroids, and in particular for graph-related matroids, the so-called graphic matroids. The attempt to generalize duality theorems in the context of infinite graphs and infinite matroids has proved to be a difficult task since the middle of the last century. After several unsuccessful attempts, the topic was almost ignored until a few years ago, when a new definition of infinite matroids was proposed which made it possible to extend the duality theorems for finite matroids to infinite ones. In the further attempt to extend to the case of infinite graphs some results that worked well in the finite case, the definition of PSI-matroid was born. The existence of these objects requires the construction of adequate topological spaces starting from infinite graphs. In particular, some matroidal properties have proved to be equivalent to issues related to game theory: specifically the existence of these PSI-matroids is linked to Borel Determinacy, an important theorem on two players infinite games with perfect information.

Nell'ambito dei grafi finiti lo studio delle relazioni di dualità tra grafi ha ottenuto risultati molto soddisfacenti che hanno permesso una più profonda conoscenza di queste strutture matematiche. Lo stesso si può dire per il fenomeno della dualità tra matroidi finite, ed in particolare per le matroidi legate ai grafi, le cosiddette matroidi grafiche. Il tentativo di generalizzare i teoremi di dualità nell'ambito di grafi infiniti e matroidi infinite si è rilevato essere un arduo problema già dalla metà del secolo scorso. Dopo svariati tentativi fallimentari l'argomento è stato pressochè ignorato fino pochi anni fa, quando è stata proposta una nuova definizione di matroidi infinite che ha reso possibile l'estensione dei teoremi di dualità per le matroidi. Nell'ulteriore tentativo di estendere al caso di grafi infiniti alcuni risultati che funzionano bene nel caso finito è nata la definizione di PSI-matroide. L'esistenza di questi oggetti richiede la costruzione di adeguati spazi topologici a partire dai grafi infiniti. In particolare, alcune proprietà matroidali si sono rivelate equivalenti a questioni legate alla teoria dei giochi: nello specifico l'esistenza di queste PSI-matroidi è legata alla Borel Determinacy, un importante teorema relativo alla teoria dei giochi infiniti, a informazione perfetta, a due giocatori.

Borel Determinacy, Grafi Infiniti e PSI-matroidi

GRECHI, ETTORE
2018/2019

Abstract

The study of duality relationships between finite graphs has reached very satisfactory results that have allowed a deeper knowledge of these mathematical structures. The same can be said for the phenomenon of duality between finite matroids, and in particular for graph-related matroids, the so-called graphic matroids. The attempt to generalize duality theorems in the context of infinite graphs and infinite matroids has proved to be a difficult task since the middle of the last century. After several unsuccessful attempts, the topic was almost ignored until a few years ago, when a new definition of infinite matroids was proposed which made it possible to extend the duality theorems for finite matroids to infinite ones. In the further attempt to extend to the case of infinite graphs some results that worked well in the finite case, the definition of PSI-matroid was born. The existence of these objects requires the construction of adequate topological spaces starting from infinite graphs. In particular, some matroidal properties have proved to be equivalent to issues related to game theory: specifically the existence of these PSI-matroids is linked to Borel Determinacy, an important theorem on two players infinite games with perfect information.
2018
Borel Determinacy, Infinite Graphs and PSI-matroids
Nell'ambito dei grafi finiti lo studio delle relazioni di dualità tra grafi ha ottenuto risultati molto soddisfacenti che hanno permesso una più profonda conoscenza di queste strutture matematiche. Lo stesso si può dire per il fenomeno della dualità tra matroidi finite, ed in particolare per le matroidi legate ai grafi, le cosiddette matroidi grafiche. Il tentativo di generalizzare i teoremi di dualità nell'ambito di grafi infiniti e matroidi infinite si è rilevato essere un arduo problema già dalla metà del secolo scorso. Dopo svariati tentativi fallimentari l'argomento è stato pressochè ignorato fino pochi anni fa, quando è stata proposta una nuova definizione di matroidi infinite che ha reso possibile l'estensione dei teoremi di dualità per le matroidi. Nell'ulteriore tentativo di estendere al caso di grafi infiniti alcuni risultati che funzionano bene nel caso finito è nata la definizione di PSI-matroide. L'esistenza di questi oggetti richiede la costruzione di adeguati spazi topologici a partire dai grafi infiniti. In particolare, alcune proprietà matroidali si sono rivelate equivalenti a questioni legate alla teoria dei giochi: nello specifico l'esistenza di queste PSI-matroidi è legata alla Borel Determinacy, un importante teorema relativo alla teoria dei giochi infiniti, a informazione perfetta, a due giocatori.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

È consentito all'utente scaricare e condividere i documenti disponibili a testo pieno in UNITESI UNIPV nel rispetto della licenza Creative Commons del tipo CC BY NC ND.
Per maggiori informazioni e per verifiche sull'eventuale disponibilità del file scrivere a: unitesi@unipv.it.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14239/11734