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:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210105T163000
DTEND;TZID=Asia/Seoul:20210105T173000
DTSTAMP:20260419T131627
CREATED:20201126T024545Z
LAST-MODIFIED:20240707T082022Z
UID:3313-1609864200-1609867800@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Directed tangles and applications
DESCRIPTION:The canonical tree-decomposition theorem\, proved by Robertson and Seymour in their seminal graph minors series\, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper\, we prove the analogous result for digraphs\, the directed tangle tree-decomposition theorem. More precisely\, we introduce directed tangles and provide a directed tree-decomposition of digraphs $G$ that distinguishes all maximal directed tangles in $G$. Furthermore\, for any integer $k$\, we construct a directed tree-decomposition that distinguishes all directed tangles of order $k$\, for any integer $k$. \nBy relaxing the bound slightly\, we can make the previous result algorithmic: for fixed $k$\, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order $3k$ separated by some separation of order less than $k$. \nWe provide two direct applications of this tangle tree-decomposition theorem. First\, we show that the family of directed odd cycles has the half-integral Erdős-Pósa property\, that is\, there is a function $f:\mathbb{N}\rightarrow \mathbb{R}$ such that for every digraph $G$ and every integer $k$\, either $G$ contains a family of $k$ directed odd cycles where every vertex of $G$ is contained at most two cycles\, or a vertex subset of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral Erdős-Pósa property for undirected odd cycles\, shown by Reed [Mangoes and blueberries. Combinatorica 1999]. \nSecond\, for every fixed $k$ we show that there is a polynomial-time algorithm which\, on input $G$\, and source and sink vertices $(s_1\, t_1)\, \dots\, (s_k\, t_k)$\, either finds a family of paths $P_1\, \dots\, P_k$ such that each $P_i$ links $s_i$ to $t_i$ and every vertex of $G$ is contained in at most two paths\, or determines that there is no set of pairwise vertex-disjoint paths each connecting $s_i$  to $t_i$. This result improves previous results (with “two” replaced by “three”)\, and given known hardness results\, our result is best possible in a sense that we cannot hope for fixed parameter tractability or fully vertex-disjoint directed paths. \nThis is joint work with Archontia C. Giannopoulou\, Ken-ichi Kawarabayashi\, Stephan Kreutzer\, and Qiqin Xie.
URL:https://dimag.ibs.re.kr/event/2021-01-05/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210112T163000
DTEND;TZID=Asia/Seoul:20210112T173000
DTSTAMP:20260419T131627
CREATED:20201231T074146Z
LAST-MODIFIED:20240705T191150Z
UID:3431-1610469000-1610472600@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Discrete geometry in convexity spaces
DESCRIPTION:The notion of convexity spaces provides a purely combinatorial framework for certain problems in discrete geometry. In the last ten years\, we have seen some progress on several open problems in the area\, and in this talk\, I will focus on the recent results relating to Tverberg’s theorem and the Alon-Kleitman (p\,q) theorem.
URL:https://dimag.ibs.re.kr/event/2021-01-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210119T163000
DTEND;TZID=Asia/Seoul:20210119T173000
DTSTAMP:20260419T131627
CREATED:20210114T070412Z
LAST-MODIFIED:20240705T191136Z
UID:3498-1611073800-1611077400@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Perfect matchings and derangements on graphs
DESCRIPTION:We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G. This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph\, and in terms of derangements and permutations on graphs. We give several related results and open questions. This is joint work with Matija Bucic\, Pat Devlin\, Mo Hendon\, and Dru Horne.
URL:https://dimag.ibs.re.kr/event/2021-01-19/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210126T043000
DTEND;TZID=Asia/Seoul:20210126T173000
DTSTAMP:20260419T131627
CREATED:20210125T042312Z
LAST-MODIFIED:20240707T081932Z
UID:3545-1611635400-1611682200@dimag.ibs.re.kr
SUMMARY:Tuan Tran\, Minimum saturated families of sets
DESCRIPTION:A family $\mathcal F$ of subsets of [n] is called s-saturated if it contains no s pairwise disjoint sets\, and moreover\, no set can be added to $\mathcal F$ while preserving this property. More than 40 years ago\, Erdős and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least $(1 – 2^{-(s-1)})2^n$. It is a simple exercise to show that every s-saturated family has size at least $2^{n-1}$\, but\, as was mentioned by Frankl and Tokushige\, even obtaining a slightly better bound of $(1/2 + \varepsilon)2^n$\, for some fixed $\varepsilon > 0$\, seems difficult. We prove such a result\, showing that every s-saturated family of subsets of [n] has size at least $(1 – 1/s)2^n$. In this talk\,  I will present two short proofs. This is joint work with M. Bucic\, S. Letzter and B. Sudakov.
URL:https://dimag.ibs.re.kr/event/2021-01-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR