A.A. 2013-2014

Teoria dei grafi/Graph Theory

Docente: FILIPPO VIVIANI 


SEMINARS (valid as exams):

-- Dario Spirito: "The characteristic set of a matroid", Wednesday 15 January, 10:30--12:30 (Room 211)
-- Maria Chiara Bertini: "Ribbon graphs and a cellular decomposition of the moduli space of curves", Monday 27 January, 15:00--17:00 (Room 211)
-- Valeriano Aiello: "The rank polynomial and its connections with knot theory: Kauffman bracket/polynomial, Jones polinomial, HOMFLY polynomial", Tuesday 28 January, 10:30--12:30 (Room 211)
-- Federico Wolenski: "Dessins d'enfants and the action of the absolute Galois group of the field of rational numbers", Tuesday 18 March, 16:30-18:30 (Room 211)
-- Paolo Arcangeli: "Embeddings of graphs on surfaces and the Heawood problem", Thursday 20 March, 17:00-19:00 (Room 211)



PROGRAM: 

The course is divided in 2 parts:

(1) ALGEBRAIC GRAPH THEORY: homology, the lattice and the space of cycles and of cuts, Laplacian, Jacobian group, duality, planar graphs, 2-isomorphism (Whitney's theorem). Torelli theorem for graphs.

(2) MATROIDS: representable matroids, graphic and cographic matroids, binary matroids and their space of circuits and of co-circuits, regular matroids and their lattice of circuits and co-circuits, excluded-minor characterizations of binary/regular/(co)graphic matroids, orientable matroids, zonotopes and central arrangment of hyperplanes associated to a realization of an oriented matroid, Voronoi polyope and Delaunay tiling of a lattice, Torelli theorem for simple regular matroids.


Prerequisiti: Algebra lineare (GE110), Algebra (AL210), Geometria e topologia di spazi euclidei (GE210, GE220).


Bibliography:  

A lezione si daranno indicazioni bibliografiche piu' precise per ciascun argomento trattato.

Diary of lectures:

(1,2) 01/10 : Definition of graphs. First (orientation depended) definition of homology. Rank and co-rank. The lattice of cycles and cuts.

(3,4) 07/10 : Second (orientation free) definition of homology. The space of cycles and cuts. Characterization of (minimal) cycles and of (minimal) cuts.

(5,6) 08/10 : Characteristic functions associated to cycles and cuts. Spanning trees and forests. Cycles and Cuts constructed from a spanning tree.

(7,8) 15/10 : Deletion and contraction principle for the lattice of cycles and of cuts. Topology of graphs: classification up to homotopy equivalence, fundamental group, universal cover. Parity of the lattice of cycles and of cuts: bipartite and Eulerian graphs.

(9,10) 16/10 : The Laplacian operator. The adjugate of the Laplacian matrix: Kirchoff's matrix tree theorem. The Jacobian group and the complexity number. Characteristic polynomial of the Laplacian: eingenvalues and coefficients. Examples.

(11,12,13) 04/11 : Expansion formula for the coefficients of the characteristic polynomial of the Laplacian. The determinant group of the lattice of cycles and of the one of cuts are isomorphic to the Jacobian group.

(14,15,16) 06/11 : The discriminant form of the lattice of cycles is the opposite of the discriminant form of the lattice of cuts. 3 operations that preserve the lattice of cycles (resp. of cuts): contracting separating edges (resp. removing loops), decomposing the graph into its inseparable blocks, twisting along a separating pair of vertices. Statement of the Whitney theorem: 2-isomorphism, (oriented) circuit equivalence and (oriented) bond equivalence coincide. Statement of the Torelli theorem for graphs.

(17,18,19) 11/11 Matroids: independent sets, basis, dependent sets, circuits. Examples: the vector matroid associated to a matrix, graphic matroid, cographic matroid. The rank of a matroid and the rank function. The closure operator and closed sets (or flats).

(20,21,22) 13/11 Dual matroids: bases, independent sets, dependent sets, circuits, rank fucntion, flats. The dual of a vector matroid is again a vector matroid. The graphic and cographic matroids are dual of each other and they are representable over any field.

(23,24,25) 18/11 Connected matroids and direct sum of matroids. The (co)graphic matroid is connected if and only if the graph is a block. First part of the proof of the Whitney theorem on 2-isomorphic graphs: reduction to blocks, proof in the 3-connected case.

(26,27) 20/11 Second part of the proof of the Whitney theorem on 2-isomorphic graphs: reduction to generalized circuits of blocks.

(28,29,30) 25/11 Third part of the proof of the Whitney theorem on 2-isomorphic graphs: the case of generalized circuits. Representability of a matroid over a field: equivalent representations. Binary matroids: uniqueness of their representation.

(31,32) 27/11 Criteria for a matroid to be binary: parity of the intersection of circuits and cocircuits; symmetric difference of circuits as disjoint union of circuits; realization of every circuit as symmetric difference of fundamental circuits. Partial representation of a matroid.

(33,34,35) 02/12 The cycle and co-cycle space associated to a binary matroid. Deletions, contractions and minors of matroids. The principle of excluded-minors for a given class of matroids closed under minors.

(36,37,38) 04/12 Uniform matroids. Second criteria for binary matroids: U_{2,4} is the unique excluded-minor for the class of binary matroids. Criteria for a matroid to be regular: being representable by a totally unimodular matrix, being binary and representable over a field of characteristic different from two.

(39,40, 41) 09/12 Unicity of totally unimodular signing of a (0,1)-matrix. Regular matroids are uniquely representable over any field. Finite projective spaces and their associated matroids. The Fano matroid and its dual.

(42, 43) 11/12 Unicity of the representations of a binary matroid. Regular matroids correspond bijectively to (totally) unimodular matrices up to equivalence. The list of minor excluded matroids for the following classes of matroids: binary, regular, graphic, cographic, graphic-cographic. Connection between planar graphs and graphic-cographic matroids.

(44, 45, 46) 16/12 Oriented matroids and their underlying matroids. Representability over the reals vs Orientability. Minors and dual of oriented matroids. Signable matroids. Regular matroids: unicity of their orientation; characterization as signable matroids or binary + orientable matroids. The poset of flats of a matroid. The poset of covectors of an oriented matroid.

(47, 48, 49) 18/12 Zonotopes and central arrangements of hyperplanes associated to a realization of an oriented matroid. The lattice of circuits and the lattice of co-circuits of a regular matroid. The Voronoi polytope and the Delaunay tiling of a lattice. Torelli theorem for simple regular matroids.