112. Mathematical Colloquium

Marc Noy

Universitat Politecnica de Catalunya, Barcelona

LOGIC AND RANDOM GRAPHS

Abstract

A well-known theorem from the 1960s says that for any property of graphs A expressible in first order logic, the probability that a random graph with N vertices satisfies A tends either to 0 or to 1 as N goes to infinity. This result has been widely extended in several directions, either considering logics with more expressive power, or different models of random graphs. In the talk we will survery several results in the area, including recent ones on planar graphs and graphs on surfaces.

About the speaker

Marc Noy studoval v Barceloně (jak na universitě tak na technice UPC) a rovněž na Brandeis University v USA. Je řádným profesorem na Katalánské technice v Barceloně (UPC), kde zastával řadu významných akademických funkcí. Zmiňme zde pouze, že byl jedním ze zakladatelů Barcelona Graduate School in Mathematics, kde byl předsedou vědecké rady a posléze ředitelem.

Vědecká činnost Marca Noye je výrazně mezioborová. Významných výsledků dosáhl v kombinatorice a teorii grafů (zde vyřešil starý problém asymptotické enumerace rovinných grafů, příslušná práce vyšla v Amer. J. Math.), ale rovněž v diskrétní geometrii (kde podal řešení známého problému z teorie matroidů) a rovněž v pravděpodobnostních metodách a teoretické informatice. V poslední době se věnuje souvislostem logiky a kombinatoriky a z této oblasti je rovněž jeho pražské kolokvium.

Marc Noy přednesl řadu plenárních přednášek na mezinárodních konferencích, včetně zvané přednášky na Mezinárodním kongresu matematiků (2014). O kvalitě jeho přednášek se můžete přesvědčit sami.