Fabrizio PUGLIESE | TEORIA DEI MATROIDI
Fabrizio PUGLIESE TEORIA DEI MATROIDI
cod. 8860300013
TEORIA DEI MATROIDI
| 8860300013 | |
| DIPARTIMENTO DI MATEMATICA | |
| Corso di Dottorato (D.M.226/2021) | |
| MATHEMATICS | |
| 2022/2023 |
| YEAR OF COURSE 1 | |
| YEAR OF DIDACTIC SYSTEM 2022 | |
| FULL ACADEMIC YEAR |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| MAT/03 | 2 | 10 | LESSONS |
| Objectives | |
|---|---|
| THE AIM OF THE COURSE IS TO INTRODUCE THE NOTION OF MATROID, BOTH IN ITS COMBINATORIAL AND GEOMETRIC ASPECTS, AND PRESENT SOME OF ITS NUMEROUS APPLICATIONS TO COMBINATORIAL OPTIMIZATION. FURTHERMORE, WE WILL GIVE SOME HINT ABOUT RECENT RESULTS LINKING MATROIDS TO ALGEBRAIC GEOMETRY. |
| Prerequisites | |
|---|---|
| THE PREREQUITES ARE BASIC LINEAR ALGEBRA AND SOME RUDIMENTARY NOTION OF GRAPH THEORY (BUT THE LATTER IS NOT STRICTLY NECESSARY). |
| Contents | |
|---|---|
| MATROID THEORY, CREATED IN 1935 BY H. WHITNEY WITH THE AIM OF AXIOMATIZING THE NOTION OF INDEPENDENCE BOTH IN LINEAR ALGEBRA AND GRAPH THEORY, HAS SINCE THEN UNDERGONE QUITE AN IMPRESSIVE DEVELOPMENT, IN DIRECTIONS OFTEN VERY DIFFERENT FROM THOSE FOR WHICH IT WAS BORN; FOR EXAMPLE, NOWADAYS MATROIDS PLAY A FUNDAMENTAL ROLE IN COMBINATORIAL OPTIMIZATION. RECENTLY, J. HUH AND HIS COLLABORATORS HAVE FOUND OUT SPECTACULAR LINKS BETWEEN MATROIDS AND ALGEBRAIC GEOMETRY; FOR SUCH RESULTS HUH WON THE FIELDS MEDAL IN 2022. THE AIM OF THE COURSE IS TO PROVIDE THE ELEMENTS OF MATROID THEORY AND SHOW SOME OF ITS REMARKABLE APPLICATIONS (IN PARTICULAR, IN THE FIELD OF OPTIMIZATION). THE TENTATIVE PROGRAM IS: - MATROIDS AND THEIR VARIOUS CHARACTERIZATIONS (VIA BASES, CIRCUITS, RANK, FLATS, ETC.) - MAIN TYPES OF MATROID (LINEAR, GRAPHICAL, TRANSVERSAL) - LINEAR REPRESENTABILITY OF MATROIDS - GREEDY ALGORITHMS - MATROID INTERSECTION; WEIGHTED INTERSECTION, EDMONDS THEOREMS - POLYMATROIDS AND SUBMODULAR FUNCTIONS - MATROIDS AND TROPICAL GEOMETRY |
| Teaching Methods | |
|---|---|
| FRONTAL LECTURES, WITH A NUMBER OF EXERCISES PROPOSED IN THE CLASSROOM OR GIVEN AS HOMEWORK. |
| Verification of learning | |
|---|---|
| THE LEVEL OF LEARNING REACHED BY THE STUDENT WILL BE CHECKED EITHER VIA A TRADITIONAL ORAL EXAM OR A SEMINAR ON A SUBJECT LINKED TO THE PROGRAM OF THE COURSE. |
| Texts | |
|---|---|
| - A. SCHRIJVER, "A COURSE IN COMBINATORIAL OPTIMIZATION", NOTES DOWNLOADABLE FROM HTTPS://HOMEPAGES.CWI.NL/~LEX/ - E.L. LAWLER, "COMBINATORIAL OPTIMIZATION: NETWORKS AND MATROIDS" (HOLT, RINEHART AND WINSTON 1976) - J. OXLEY, "MATROID THEORY" (O.U.P. 2011) - J. A. WELSH, "MATROIDS: FUNDAMENTAL CONCEPTS", IN "HANDBOOK OF COMBINATORICS", VOL. 1 (NORTH HOLLAND 1995) - F. ARDILA, "THE GEOMETRY OF MATROIDS" NOTICES AMER. MATH. SOC. 65 (2018), NO. 8, 902–908 - F. ARDILA, "THE GEOMETRY OF GEOMETRIES", 2021, PREPRINT ARXIV:2111.08726V1 |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2024-08-21]
