Loading Events

« All Events

  • This event has passed.
:

Dillon Mayhew, Courcelle’s Theorem for hypergraphs

Tuesday, January 28, 2020 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Courcelle’s Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic second-order logic of graphs, and as long as the input is restricted to a class of graphs with bounded tree-width. There are several properties that are NP-complete in general, but which can be expressed in monadic logic (3-colourability, Hamiltonicity…), so Courcelle’s Theorem implies that these difficult properties can be tested in polynomial time when the structural complexity of the input is limited.

Matroids can be considered as a special class of hypergraphs. Any finite set of vectors over a field leads to a matroid, and such a matroid is said to be representable over that field. Hlineny produced a matroid analogue of Courcelle’s Theorem for input classes with bounded branch-width that are representable over a finite field.

We have now identified the structural properties of hypergraph classes that allow a proof of Hliněný’s Theorem to go through. This means that we are able to extend his theorem to several other natural classes of matroids.

This talk will contain an introduction to matroids, monadic logic, and tree-automata.

This is joint work with Daryl Funk, Mike Newman, and Geoff Whittle.

Details

Date:
Tuesday, January 28, 2020
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
View Organizer Website
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.