Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Wednesday, May 22, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Marc Noy (Universitat Politècnica de Catalunya)
Let G be a minor-closed class of graphs all whose forbidden minors are 2-connected. We prove a zero-one law in monadic second-order logic for random connected graphs in G, and a convergence law for all graphs in G. For each surface S, we prove a zero-one law in first order logic for random connected graphs embeddable in S, and a convergence law for all graphs embeddable in S.
The proofs are based on several properties that hold for almost all graphs in a minor-closed class.
(Joint work with Peter Heinig, Tobias Müller and Anusch Taraz).
Automatic MiSe System Software Version 1.4803M | admin login