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:20201103T163000
DTEND;TZID=Asia/Seoul:20201103T173000
DTSTAMP:20260424T013056
CREATED:20201022T132652Z
LAST-MODIFIED:20240705T193042Z
UID:3188-1604421000-1604424600@dimag.ibs.re.kr
SUMMARY:Jaeseong Oh (오재성)\, A 2-isomorphism theorem for delta-matroids
DESCRIPTION:Whitney’s 2-Isomorphism Theorem characterises when two graphs have isomorphic cycle matroids. In this talk\, we present an analogue of this theorem for graphs embedded in surfaces by characterising when two graphs in surface have isomorphic delta-matroids. This is based on the joint work with Iain Moffatt.
URL:https://dimag.ibs.re.kr/event/2020-11-03/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201105T100000
DTEND;TZID=Asia/Seoul:20201105T110000
DTSTAMP:20260424T013056
CREATED:20200818T142112Z
LAST-MODIFIED:20240707T082448Z
UID:2820-1604570400-1604574000@dimag.ibs.re.kr
SUMMARY:Daniel Cranston\, Vertex Partitions into an Independent Set and a Forest with Each Component Small
DESCRIPTION:For each integer $k\ge 2$\, we determine a sharp bound on\n$\operatorname{mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$\, where $I$ is an independent set and $G[F_k]$ is a forest in which each component has at most k vertices. For each $k$ we construct an infinite family of examples showing our result is best possible. Hendrey\, Norin\, and Wood asked for the largest function $g(a\,b)$ such that if $\operatorname{mad}(G) < g(a\,b)$ then $V(G)$ has a partition into sets $A$ and $B$ such that $\operatorname{mad}(G[A]) < a$ and $\operatorname{mad}(G[B]) < b$. They specifically asked for the value of $g(1\,b)$\, which corresponds to the case that $A$ is an independent set. Previously\, the only values known were $g(1\,4/3)$ and $g(1\,2)$. We find the value of $g(1\,b)$ whenever $4/3 < b < 2$. This is joint work with Matthew Yancey.
URL:https://dimag.ibs.re.kr/event/2020-11-05/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201110T163000
DTEND;TZID=Asia/Seoul:20201110T173000
DTSTAMP:20260424T013056
CREATED:20201028T010325Z
LAST-MODIFIED:20240705T193037Z
UID:3212-1605025800-1605029400@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Extremal forbidden poset problems in Boolean and linear lattices
DESCRIPTION:Extending the classical theorem of Sperner on the maximum size of an antichain in the Boolean lattice\, Katona and Tarján introduced a general extremal function $La(n\,P)$\, defined to be the maximum size of a family of subsets of $[n]$ which does not contain a given poset $P$ among its containment relations.  In this talk\, I will discuss what is known about the behavior of $La(n\,P)$ and its natural extension to the lattice of subspaces of a vector space over a finite field.  In particular\, I will highlight some recent joint work with Jimeng Xiao.  Many open problems will also be discussed.
URL:https://dimag.ibs.re.kr/event/2020-11-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201111T163000
DTEND;TZID=Asia/Seoul:20201111T173000
DTSTAMP:20260424T013056
CREATED:20200927T024800Z
LAST-MODIFIED:20240707T082419Z
UID:3059-1605112200-1605115800@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, Constant congestion bramble
DESCRIPTION:In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk\, Paweł Komosa and Manuel Sorge. \nA bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. \nBrambles are objects dual to treewidth: As shown by Seymour and Thomas\, the maximum order of a bramble in an undirected graph $G$ equals one plus the treewidth of $G$. However\, as shown by Grohe and Marx\, brambles of high order may necessarily be of exponential size: In a constant-degree $n$-vertex expander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponential in $\Omega(n^{2\delta})$ for any fixed $\delta \in (0\,\frac{1}{2}]$. On the other hand\, the combination of results of Grohe and Marx\, and Chekuri and Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order $\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{O}(k^{3/2})$. ($\widetilde{\Omega}$ and $\widetilde{O}$ hide polylogarithmic factors and divisors\, respectively.) \nWe first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2})$ and congestion $2$\, i.e.\, every vertex of $G$ is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second\, we provide a tight upper bound for the lower bound of Grohe and Marx: For every $\delta \in (0\,\frac{1}{2}]$\, every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2+\delta})$ and size $2^{\widetilde{O}(k^{2\delta})}$.
URL:https://dimag.ibs.re.kr/event/2020-11-11/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201119T163000
DTEND;TZID=Asia/Seoul:20201119T173000
DTSTAMP:20260424T013056
CREATED:20200927T025647Z
LAST-MODIFIED:20240705T194022Z
UID:3062-1605803400-1605807000@dimag.ibs.re.kr
SUMMARY:Yijia Chen (陈翌佳)\, Graphs of bounded shrub-depth\, through a logic lens
DESCRIPTION:Shrub-depth is a graph invariant often considered as an extension\nof tree-depth to dense graphs. In this talk I will explain our recent\nproofs of two results about graphs of bounded shrub-depth. \n\nEvery graph property definable in monadic-second order logic\,\ne.g.\, 3-colorability\, can be evaluated by Boolean circuits of constant\ndepth and polynomial size\, whose depth only depends on the\nshrub-depth of input graphs.\nGraphs of bounded shrub-depth can be characterized by\na finite set of forbidden induced subgraphs [Ganian et al. 2015].\n\nCentral to the first result is the definability in first-order logic of\ntree-models for graphs of bounded shrub-depth. For the second\nresult\, we observe that shrub-depth can be easily generalized\nto infinite graphs\, and thus some classical tools\, i.e.\, Craig’s\nInterpolation and Łoś-Tarski Theorem\, in model theory are\napplicable to graphs of bounded shrub-depth. \nThis is joint work with Jörg Flum.
URL:https://dimag.ibs.re.kr/event/2020-11-19/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201124T163000
DTEND;TZID=Asia/Seoul:20201124T173000
DTSTAMP:20260424T013056
CREATED:20201111T070608Z
LAST-MODIFIED:20240705T193020Z
UID:3264-1606235400-1606239000@dimag.ibs.re.kr
SUMMARY:Duksang Lee (이덕상)\, Characterizing matroids whose bases form graphic delta-matroids
DESCRIPTION:We introduce delta-graphic matroids\, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for the class of delta-graphic matroids has at most 48 elements. This is joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2020-11-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201126T100000
DTEND;TZID=Asia/Seoul:20201126T110000
DTSTAMP:20260424T013056
CREATED:20201027T002159Z
LAST-MODIFIED:20240705T193041Z
UID:3195-1606384800-1606388400@dimag.ibs.re.kr
SUMMARY:Da Qi Chen\, Bipartite Saturation
DESCRIPTION:In extremal graph theory\, a graph G is H-saturated if G does not contain a copy of H but adding any missing edge to G creates a copy of H. The saturation number\, sat(n\, H)\, is the minimum number of edges in an n-vertex H-saturated graph. This class of problems was first studied by Zykov and Erdős\, Hajnal\, and Moon. They also determined the saturation number when H is a clique and classified the extremal structures. \nIn this talk\, we will focus mainly on the bipartite saturation problem (which was also first introduced by Erdős\, Hajnal\, and Moon). Here\, we always assume that both G and H are bipartite graphs. Then\, G is H-saturated if G does not contain H but adding any missing edge across the bipartition creates a copy of H. We can then similarly define sat(n\, H) as the minimum number of edges of an n-by-n bipartite graph that is also H-saturated. One of the most interesting and natural questions here is to determine the saturation number for the complete bipartite graph $K_{s\, t}$. When s=t\, the saturation number and its extremal structures were determined long ago but nothing else is known for the general case. Half a decade ago\, Gan\, Korandi\, and Sudakov gave an asymptotically tight bound that was only off by an additive constant.  We will highlight the main ideas behind that proof and show\, with some additional techniques\, how the bound can be improved to achieve tightness for the case when s=t-1. \nThis talk is based on collaborative work with Debsoumya Chakraborti and Mihir Hasabnis. See arXiv: https://arxiv.org/abs/2009.07651 for the full paper.
URL:https://dimag.ibs.re.kr/event/2020-11-26/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201130T170000
DTEND;TZID=Asia/Seoul:20201130T180000
DTSTAMP:20260424T013056
CREATED:20201126T022202Z
LAST-MODIFIED:20240707T082346Z
UID:3307-1606755600-1606759200@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, On Ramsey multiplicity
DESCRIPTION:Ramsey’s theorem states that\, for a fixed graph $H$\, every 2-edge-colouring of $K_n$ contains a monochromatic copy of $H$ whenever $n$ is large enough. Perhaps one of the most natural questions after Ramsey’s theorem is then how many copies of monochromatic $H$ can be guaranteed to exist. To formalise this question\, let the Ramsey multiplicity $M(H;n)$ be the minimum number of labelled copies of monochromatic $H$ over all 2-edge-colouring of $K_n$. We define the Ramsey multiplicity constant $C(H)$ is defined by $C(H):=\lim_{n\rightarrow\infty}\frac{M(H\,n)}{n(n-1)\cdots(n-v+1)}$. I will discuss various bounds for C(H) that are known so far.
URL:https://dimag.ibs.re.kr/event/2020-11-30/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR