BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240827T163000
DTEND;TZID=Asia/Seoul:20240827T173000
DTSTAMP:20260416T071028
CREATED:20240530T224746Z
LAST-MODIFIED:20240729T124158Z
UID:8730-1724776200-1724779800@dimag.ibs.re.kr
SUMMARY:Dillon Mayhew\, Monadic second-order definability for gain-graphic matroids
DESCRIPTION:Every (finite) matroid consists of a (finite) set called the ground set\, and a collection of distinguished subsets called the independent sets. A classic example arises when the ground set is a finite set of vectors from a vector space\, and the independent subsets are exactly the subsets that are linearly independent. Any such matroid is said to be representable. We can think of a representable matroid as being a geometrical configuration where the points have been given coordinates from a field. Another important class arises when the points are given coordinates from a group. Such a class is said to be gain-graphic.  \nMonadic second-order logic is a natural language for matroid applications. In this language we are able to quantify only over subsets of the ground set. The importance of monadic second-order logic comes from its connections to the theory of computation\, as exemplified by Courcelle’s Theorem. This theorem provides polynomial-time algorithms for recognising properties defined in monadic second-order logic (as long as we impose a bound on the structural complexity of the input objects). It is natural to ask which classes of matroids can be defined by sentences in monadic second-order logic. When the class consists of the matroids that are coordinatized by a field we have a complete answer to this question. When the class is coordinatized by a group the problem becomes much harder. \nThis talk will contain a brief introduction to matroids. Based on work with Sapir Ben-Shahar\, Matt Conder\, Daryl Funk\, Angus Matthews\, Mike Newman\, and Gabriel Verret.
URL:https://dimag.ibs.re.kr/event/2024-08-27/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR