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:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20191210T163000
DTEND;TZID=Asia/Seoul:20191210T173000
DTSTAMP:20260420T145615
CREATED:20191004T104834Z
LAST-MODIFIED:20240707T084332Z
UID:1488-1575995400-1575999000@dimag.ibs.re.kr
SUMMARY:Jakub Gajarský\, First-order interpretations of bounded expansion classes
DESCRIPTION:The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular\, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs\, we introduce classes of graphs with structurally bounded expansion\, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment\, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions\, replacing treedepth by its dense analogue called shrubdepth.
URL:https://dimag.ibs.re.kr/event/2019-12-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20191212T163000
DTEND;TZID=Asia/Seoul:20191212T173000
DTSTAMP:20260420T145615
CREATED:20191122T071803Z
LAST-MODIFIED:20240707T084259Z
UID:1872-1576168200-1576171800@dimag.ibs.re.kr
SUMMARY:Hong Liu\, A proof of Mader's conjecture on large clique subdivisions in $C_4$-free graphs
DESCRIPTION:Given any integers $s\,t\geq 2$\, we show there exists some $c=c(s\,t)>0$ such that any $K_{s\,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ vertices. In particular\, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general\, the widely conjectured asymptotic behaviour of the extremal density of $K_{s\,t}$-free graphs suggests our result is tight up to the constant $c(s\,t)$. This is joint work with Richard Montgomery.
URL:https://dimag.ibs.re.kr/event/2019-12-12/
LOCATION:Room 1401\, Bldg. E6-1\, KAIST
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20191219T163000
DTEND;TZID=Asia/Seoul:20191219T173000
DTSTAMP:20260420T145615
CREATED:20191119T013103Z
LAST-MODIFIED:20240707T084251Z
UID:1801-1576773000-1576776600@dimag.ibs.re.kr
SUMMARY:Attila Joó\, Base partition for finitary-cofinitary matroid families
DESCRIPTION:Let ${\mathcal{M} = (M_i \colon i\in K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$. \nWe prove the following Cantor-Bernstein-type result: if $E$ can be covered by sets ${(B_i \colon i\in K)}$ which are bases in the corresponding matroids and there are also pairwise disjoint bases of the matroids $M_i$ then $E$ can be partitioned into bases with respect to $\mathcal{M}$.
URL:https://dimag.ibs.re.kr/event/2019-12-19/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20191226T163000
DTEND;TZID=Asia/Seoul:20191226T173000
DTSTAMP:20260420T145615
CREATED:20191122T072031Z
LAST-MODIFIED:20240705T203023Z
UID:1875-1577377800-1577381400@dimag.ibs.re.kr
SUMMARY:Jaiung Jun (전재웅)\, The Hall algebra of the category of matroids
DESCRIPTION:To an abelian category A satisfying certain finiteness conditions\, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a non-additive setting\, Dyckerhoff and Kapranov introduced the notion of proto-exact categories\, as a non-additive generalization of an exact category\, which is shown to suffice for the construction of an associative Hall algebra. In this talk\, I will discuss the category of matroids in this perspective.
URL:https://dimag.ibs.re.kr/event/2019-12-26/
LOCATION:Room 1401\, Bldg. E6-1\, KAIST
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR