Università Cattolica del Sacro Cuore Università Cattolica del Sacro Cuore

Campus di Brescia

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

Via Musei 41, Brescia

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"