23.10.2017 09:30 @ Other Seminars
Graphons are the main objects in the theory of graph limits introduced in 2006 by Lovász and Szegedy, and recently developed by Borgs, Chayes, Lovász, Sós and Vesztergombi. Graphons are limits of graph sequences in the cut metric. Graphs are particular types of graphons and the space of graphons is compact with respect the cut metric. This is equivalent to strong forms of Szemerédi’s Regularity Lemma. That implies that the space of graphons is indeed the completion of the space of finite graphs with the cut metric. Naturally, one wants to extend the classical graph parameters to graphons and hope to find continuity. Even though some parameters are continuous, as the density of triangles, some are not, as the matching number. Whenever we do not have continuity, properties do not follow directly from graphs. We introduce graphon counterparts of the chromatic and the clique number, the fractional chromatic number, the b-chromatic number, and the b-fractional clique number. Turns out these parameters are not continuous. In this talk I will explain how this can be done, the properties we can obtain, and the significant differences between the proofs for graphs and for graphons.
25.10.2017 10:00 @ Applied Mathematical Logic
It is well known that every propositional logic L has an algebra-based semantics Alg(L) with respect to which it is sound and complete. Well-behaved logics L tend to have also a relations semantics, which is given in terms of relational structures that are in some sense dual to the algebras in Alg(L). This is indeed the case both for intutitionistic and normal modal logics, since it is well known that every Heyting algebra can be turned into an intuitionistic frame, and that every modal algebra can be turned into a Kripke frame, and viceversa. The aim of this talk is to describe a general method to provide relational semantics Rel(L) for almost arbitery prosositional logics L, and to do it in such a way that the relational semantics Rel(L) consists exactly in the class of suitably de_ned relational duals of algebras in Alg(L).
