BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250805T163000
DTEND;TZID=Asia/Seoul:20250805T173000
DTSTAMP:20260419T224835
CREATED:20250713T060700Z
LAST-MODIFIED:20250725T225751Z
UID:11148-1754411400-1754415000@dimag.ibs.re.kr
SUMMARY:Tony Huynh\, Rainbow triangles and the Erdős-Hajnal problem in projective geometries
DESCRIPTION:We formulate a geometric version of the Erdős-Hajnal conjecture that applies to finite projective geometries rather than graphs.  In fact\, we give a natural extension of the ‘multicoloured’ version of the Erdős-Hajnal conjecture. Roughly\, our conjecture states that every colouring of the points of a finite projective geometry of dimension $n$ not containing a fixed colouring of a fixed projective geometry $H$ must contain a subspace of dimension polynomial in $n$ avoiding some colour. \nWhen $H$ is a ‘triangle’\, there are three different colourings\, all of which we resolve.  We handle the case that $H$ is a ‘rainbow’ triangle by proving that rainbow-triangle-free colourings of projective geometries are exactly those that admit a certain decomposition into two-coloured pieces. This is closely analogous to a theorem of Gallai on rainbow-triangle-free coloured complete graphs. The two non-rainbow colourings of $H$ are handled via a recent breakthrough result in additive combinatorics due to Kelley and Meka.  \nThis is joint work with Carolyn Chun\, James Dylan Douthitt\, Wayne Ge\, Matthew E. Kroeker\, and Peter Nelson.
URL:https://dimag.ibs.re.kr/event/2025-08-05/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250812T163000
DTEND;TZID=Asia/Seoul:20250812T173000
DTSTAMP:20260419T224835
CREATED:20250702T055012Z
LAST-MODIFIED:20250702T055027Z
UID:11088-1755016200-1755019800@dimag.ibs.re.kr
SUMMARY:Chien-Chung Huang\, Robust Sparsification for Matroid Intersection with Applications
DESCRIPTION:The matroid intersection problem is a fundamental problem in combinatorial optimization. In this problem we are given two matroids and the goal is to find the largest common independent set in both matroids. This problem was introduced and solved by Edmonds in the 70s. The importance of matroid intersection stems from the large variety of combinatorial optimization problems it captures; well-known examples in computer science include bipartite matching and packing of spanning trees/arborescences. \nIn this talk\, we introduce a “sparsifer” for the matroid intersection problem and use it to design algorithms for two problems closely related to streaming: a one-way communication protocol and a streaming algorithm in the random-order streaming model. \nThis is a joint-work with François Sellier.
URL:https://dimag.ibs.re.kr/event/2025-08-12/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250829T163000
DTEND;TZID=Asia/Seoul:20250829T173000
DTSTAMP:20260419T224835
CREATED:20250813T120105Z
LAST-MODIFIED:20250813T122838Z
UID:11368-1756485000-1756488600@dimag.ibs.re.kr
SUMMARY:Sang-il Oum (엄상일)\, The Erdős-Pósa property for circle graphs as vertex-minors
DESCRIPTION:We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$\, there exists an integer $t=t(k\,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$\, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. Using the same techniques\, we also prove that for any planar multigraph $H$\, every binary matroid either has a minor isomorphic to the cycle matroid of $kH$\, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of $H$. This is joint work with Rutger Campbell\, J. Pascal Gollin\, Meike Hatzel\, O-joung Kwon\, Rose McCarty\, and Sebastian Wiederrecht.
URL:https://dimag.ibs.re.kr/event/2025-08-29/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR