Monday, June 15, 2015
Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
Let A be a class of combinatorial structures equipped, for each N,
with a probability distribution on the collection of objects of size
N.
Given a sentence S in some logical language, we are interested in the
limiting probability P(S) that S is satisfied among all objects of
size N, as N goes to infinity. If P(S) is either 0 or 1 for each
sentence S, we say that the zero-one law holds. The first result of
this kind was obtained by Glebskii et al. in 1969 for the class of
labelled graphs and sentences in first order logic (FO). Compton
(1987) obtained in some cases zero-one laws solely from properties of
the counting function of the class A. Later he extended it to monadic
second order logic (MSO), which is FO logic plus quantification over
unary relations.
More recently McCoy (2002) proved a zero-one law in MSO logic for
labelled trees. We provide a significant extension of McCoy's result
to classes of graphs closed under taking minors. As an example, we
prove the MSO zero-one law for connected planar graphs and a
convergence law (every sentence has a limit, not necessarily 0 or 1)
for all planar graphs. We also determine the closure of the set of all
possible limiting probabilities, both in FO and MSO. For the proofs we
use classical tools from combinatorial logic, in particular
Ehrenfeucht-Fraïssé games, and properties of random graphs from a
minor-closed class.
Colloquium - 16:00
Abstract:
We are given a bipartite graph G = (A ∪ B, E) where each vertex has a strict preference list ranking its neighbors. A matching M is popular if there is no matching M' such that the number of vertices that prefer M' to M exceeds the number of vertices that prefer M to M'. A matching M is stable if there is no unmatched pair ab, so that a and b both prefer each other to their partners in M. While stable matchings capture the notion of local optimality, popular matchings provide a useful alternative to the well-studied stable matchings in the collective setting, aiming at the welfare of an entire group. In this talk we will present some basic results on popular matchings and also show new structural properties that build a bridge between the sets of stable and popular matchings on an instance.
Joint work with Kavitha Telikepalli.