The largest PCC graph has 208 vertices: a proof inspired by the notion of 'transportation plan' in measure theory
Seminario
Aula: Aula 5 - Ore: 14.30
Condividi su:
Programma
Introduce:
Maurizio PAOLINI
Università Cattolica del Sacro Cuore
Interviene:
Luca GHIDELLI
University of Ottawa
Abstract
In questo talk considereremo una classe di grafi planari che generalizza i solidi di Johnson. Su questi grafi è definita una nozione di curvatura riemanniana discreta studiata da Higuchi (2001), dimodoché ogni vertice ha curvatura strettamente positiva. DeVos e Mohar (2008) hanno mostrato che tali grafi sono necessariamente finiti e hanno posto il seguente quesito: quanti vertici può avere al massimo un tale grafo, che non sia prisma, né antiprisma? La risposta è 208. Mostreremo prima un approccio computazionale e parzialmente risolutivo tramite Integer Linear Programming. Poi illustreremo un approccio combinatorico-analitico conclusivo, nel quale viene utilizzato un processo di "scarica" e "smoothing" per ridurre il problema alla stima di certe medie ponderate.
Informazioni utili
In collaborazione con:
- FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E NATURALI
- DIPARTIMENTO DI MATEMATICA E FISICA NICCOLÒ TARTAGLIA"