Archive (winter term 2023/24)
- December 20, 2023
-
Clara Pichler
title: The Tutte Polynomial
abstract:
Matroids provide a notion of independence that generalises concepts from linear
algebra, graph theory and other subjects.
This presentation will concentrate on the connection between the Tutte
polynomial, a bivariate polynomial defined on matroids, and the chromatic
polynomial, a univariate polynomial defined on graphs. It also provides an
introduction to matroids and their association to graphs, so that prior
knowledge in matroid theory is not necessary.
- November 29, 2023
-
Juan Aguilera
title: The compactness number of Gödel logic
abstract:
We give a proof of the theorem that the compactness number of first-order Gödel logic with identity is the least \omega_1-strongly compact cardinal.
- November 22, 2023
-
Thibaut Kouptchinsky
title: Reverse Mathematics: Limits of Determinacy Axioms in Second-Order Arithmetic and Beyond
abstract:
I will introduce the method of Reverse Mathematics trough the question: « What are the right axioms to play infinite games ». We will then generalise a theorem of Montalbán and Shore. They showed what was the limit of determinacy when one work in the realm of natural numbers and set of natural numbers. We will use their arguments and add ours to prove that (almost) the same bounds show up in higher order set theoretic settings.
- November 8, 2023
-
Selwyn (Keng Meng) Ng
title: The strength of the 4 colour theorem
abstract:
We study the reverse mathematical strength of the 4-colour theorem and various related principles. We show that the 4 colour theorem effectively reverses to WKL0, but the 8-colour theorem reverses, but not effectively. We also study the relationship between the k-colour theorem for all values of k.
- Tuesday, October 10, 2023, 10:00am, Besprechungsraum
-
Dino Rossegger
title: Learning equivalence relations
abstract:
I will report on an ongoing project with Ted Slaman and Tomasz Steifer that aims to develop a framework for the algorithmic learning of equivalence relations studied in descriptive set theory. Inspired by recent work of Fokina, Kötzing and San Mauro who formulated a framework to learn the isomorphism relation on countable classes of structures, we introduce frameworks that aim to formalize what it means for an equivalence relation on a Polish space to be learnable. Our main results connect learnability in this framework to the descriptive complexity of the equivalence relation. We also show that the set of learnable Borel equivalence relations is co-analytic complete in the codes and rediscover longstanding open questions about Borel equivalence relations.
Last Change: 2024-06-05, Stefan Hetzl