The many facets of logic with two variables

Date

Jun 22, 2017

Time

1:15 PM - 2:15 PM

Speaker

Oleg Verbitsky

Affiliation

HU Berlin

Language

en

Main Topic

Mathematik

Other Topics

Mathematik

Host

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

Description

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

Last modified: May 26, 2017, 12:36:20 PM