"Combinatòria, probabilitat i lògica" a càrrec de Marc Noy (Dept. de Matemàtiques de la UPC)

Marc Noy és llicenciat en Matemàtiques per la Universitat de Barcelona, màster en Matemàtiques per la Brandeis University (Estats Units) i doctor en Ciències de Computació per la UPC, és catedràtic del Departament de Matemàtiques de la UPC. Ha estat cap d'estudis de la llicenciatura de matemàtiques a l'FME de l'any 2009 a l'any 2011. La seva àrea de recerca és contextualitza dins de la matemàtica discreta, havent realitzat contribucions importants en la geometria combinatoria, en la combinatoria enumerativa i en el camp de les estructures discretes aleatòries.

Dimecres 19 de febrer de 2020 a les 12 h a la sala d'actes de l'FME. Activitat oberta.

Combinatòria, probabilitat i lògica

Resum: L’anàlisi d’estructures discretes aleatòries és un dels grans temes de la combinatòria moderna. Especialment actiu és l’estudi dels grafs aleatoris, on l’èmfasi és en determinar les propietats típiques d’un graf aleatori gran i en comprendre les “transicions de fase” quan canvia la densitat d’arestes d’un graf o altres paràmetres. D’altra banda, interessen propietats de grafs que poden expressar-se en el llenguatge de la lògica de primer ordre o bé en llenguatges lògics més potents. Un punt de trobada d’aquests temes és la famosa llei 0-1 dels anys 1960: per a qualsevol propietat expressable en lògica de primer ordre, la probabilitat límit que un graf aleatori la satisfaci existeix i és necessàriament igual a 0 o igual a 1. Aquest sorprenent resultat es pot provar de diverses maneres, d’entre les quals la més “combinatòria” fa servir els jocs d’Ehrenfeucht-Fraïssé. Des de llavors s’han obtingut molts altres resultats similars fent servir eines combinatòries, probabilístiques, analítiques i lògiques. Ens proposem donar una panoràmica de l’àrea tot presentant alguns desenvolupaments recents. La xerrada serà accessible per a una audiència general.