Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, June 15, 2015

Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005



Lecture - 14:15

Marc Noy - UPC Barcelona

Logic limit laws in combinatorics

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

Ágnes Cseh - TU Berlin

Popular matchings

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.



Letzte Aktualisierung: 09.06.2015