The many facets of logic with two variables

Datum

22.06.2017

Zeit

13:15 - 14:15

Sprecher

Oleg Verbitsky

Zugehörigkeit

HU Berlin

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Prof. Dr. M. Bodirsky / Prof. Dr. A. Thom

Beschreibung

First-order logic with two variables has surprising connections to seemingly distant concepts of discrete mathematics. For example, two graphs are indistinguishable by sentences with two first-order variables and counting quantifiers if and only if they are fractionally isomorphic and if and only if their universal covers are isomorphic. Due to these connections, 2-variable logic provides a convenient framework for analysis of various problems in theory of computing. We will survey these applications with a focus on the graph isomorphism problem. In particular, we will discuss the following result and its algorithmic consequences: If a graph is definable in 2-variable logic with counting quantifiers, then the polytope of the fractional automorphisms of this graph is integral, i.e., all extreme points of this polytope have integer coordinates (or, in other terms, every definable graph is compact in the sense of Tinhofer). The talk is based on joint work with A.Krebs, V.Arvind, J.Köbler, and G.Rattan.

Links

• Seminar Algebra, Geometrie und Kombinatorik

Letztmalig verändert: 26.05.2017, 12:36:20