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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200407T163000
DTEND;TZID=Asia/Seoul:20200407T173000
DTSTAMP:20260420T063230
CREATED:20200403T043936Z
LAST-MODIFIED:20240707T084138Z
UID:2269-1586277000-1586280600@dimag.ibs.re.kr
SUMMARY:Pascal Gollin\, Disjoint dijoins for classes of dibonds in finite and infinite digraphs
DESCRIPTION:A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dibonds in that digraph. We call such sets dijoins. \nWoodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a digraph equals the minimum size of a dibond.\nWe study a modification of this question where we restrict our attention to certain classes of dibonds\, i.e. whether for a class $\mathfrak{B}$ of dibonds of a digraph the maximum number of disjoint edge sets meeting every dibond in $\mathfrak{B}$ equal the size a minimum dibond in $\mathfrak{B}$. \nIn particular\, we verify this questions for nested classes of dibonds\, for the class of dibonds of minimum size\, and for classes of infinite dibonds.
URL:https://dimag.ibs.re.kr/event/2020-04-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200414T163000
DTEND;TZID=Asia/Seoul:20200414T173000
DTSTAMP:20260420T063230
CREATED:20200409T030201Z
LAST-MODIFIED:20240705T201139Z
UID:2322-1586881800-1586885400@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Saturation problems in the Ramsey theory of graphs\, posets and point sets
DESCRIPTION:In 1964\, Erdős\, Hajnal and Moon introduced a saturation version of Turán’s classical theorem in extremal graph theory. In particular\, they determined the minimum number of edges in a $K_r$-free\, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the Erdős-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets. \nWe also consider semisaturation problems\, wherein we allow the family to have the forbidden configuration\, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting\, we prove a semisaturation version of the Erdős-Szekeres theorem on convex $k$-gons\, as well as multiple semisaturation theorems for sequences and posets. \nThis project was joint work with Gábor Damásdi\, Balázs Keszegh\, David Malec\, Zhiyu Wang and Oscar Zamora.
URL:https://dimag.ibs.re.kr/event/2020-04-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200421T163000
DTEND;TZID=Asia/Seoul:20200421T173000
DTSTAMP:20260420T063230
CREATED:20200417T000545Z
LAST-MODIFIED:20240705T201135Z
UID:2349-1587486600-1587490200@dimag.ibs.re.kr
SUMMARY:Sang-il Oum (엄상일)\, Survey on vertex-minors
DESCRIPTION:For a vertex v of a graph G\, the local complementation at v is an operation to obtain a new graph denoted by G*v from G such that two distinct vertices x\, y are adjacent in G*v if and only if both x\, y are neighbors of v and x\, y are non-adjacent\, or at least one of x\, y is not a neighbor of v and x\, y are adjacent. A graph H is a vertex-minor of a graph G if H is obtained from G by a sequence of local complementation and vertex deletions. Interestingly vertex-minors have been used in the study of measurement-based quantum computing on graph states. \nMotivated by the big success of the graph minor structure theory developed deeply by Robertson and Seymour since 1980s\, we propose a similar theory for vertex-minors. This talk will illustrate similarities between graph minors and graph vertex-minors and give a survey of known theorems and open problems on vertex-minors of graphs.
URL:https://dimag.ibs.re.kr/event/2020-04-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200428T163000
DTEND;TZID=Asia/Seoul:20200428T173000
DTSTAMP:20260420T063230
CREATED:20200417T080351Z
LAST-MODIFIED:20240707T084026Z
UID:2361-1588091400-1588095000@dimag.ibs.re.kr
SUMMARY:Seunghun Lee (이승훈)\, Leray numbers of complexes of graphs with bounded matching number
DESCRIPTION:Given a graph $G$ on the vertex set $V$\, the non-matching complex of $G$\, $\mathsf{NM}_k(G)$\, is the family of subgraphs $G’ \subset G$ whose matching number $\nu(G’)$ is strictly less than $k$. As an attempt to generalize the result by Linusson\, Shareshian and Welker on the homotopy types of $\mathsf{NM}_k(K_n)$ and $\mathsf{NM}_k(K_{r\,s})$ to arbitrary graphs $G$\, we show that (i) $\mathsf{NM}_k(G)$ is $(3k-3)$-Leray\, and (ii) if $G$ is bipartite\, then $\mathsf{NM}_k(G)$ is $(2k-2)$-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex $\mathsf{NM}_k(G)$\, which vanishes in all dimensions $d\geq 3k-4$\, and all dimensions $d \geq 2k-3$ when $G$ is bipartite. As a corollary\, we have the following rainbow matching theorem which generalizes the result by Aharoni et. al. and Drisko’s theorem: Let $E_1\, \dots\, E_{3k-2}$ be non-empty edge subsets of a graph and suppose that $\nu(E_i\cup E_j)\geq k$ for every $i\ne j$. Then $E=\bigcup E_i$ has a rainbow matching of size $k$. Furthermore\, the number of edge sets $E_i$ can be reduced to $2k-1$ when $E$ is the edge set of a bipartite graph. \nThis is a joint work with Andreas Holmsen.
URL:https://dimag.ibs.re.kr/event/2020-04-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR