Loading Events

« All Events

  • This event has passed.
:

Karl Heuer, Even Circuits in Oriented Matroids

Wednesday, December 9, 2020 @ 4:30 PM - 5:30 PM KST

Zoom ID: 934 3222 0374 (ibsdimag)

Speaker

In this talk I will state a generalisation of the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. Motivated by this problem, I will define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then I will present and discuss our two results regarding these notions:

First we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids.

Second and with the main focus for this talk, we shall characterise the class of non-even oriented bond matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen. The second result makes use of a new concept of minors for oriented matroids, which generalises butterfly minors for digraphs to oriented matroids.

The part of this talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory.

This talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht.

[1] K. Heuer, R. Steiner and S. Wiederrecht, Even Circuits in Oriented Matroidsarxiv:2010.08988

Details

Date:
Wednesday, December 9, 2020
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 934 3222 0374 (ibsdimag)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.