## Dillon Mayhew gave a talk on analogues of Courcelle’s theorem, in particular to hypergraphs and matroids at the discrete math seminar

On January 28, 2020, Dillon Mayhew from Victoria University of Wellington, New Zealand gave a talk on problems and results motivated by Courcelle’s theorem, with an emphasis on hypergraphs and matroids. The title of his talk is “Courcelle’s Theorem for hypergraphs“.

## Dillon Mayhew, Courcelle’s Theorem for hypergraphs

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. 기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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