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:20201202T170000
DTEND;TZID=Asia/Seoul:20201202T180000
DTSTAMP:20260418T081432
CREATED:20201126T022405Z
LAST-MODIFIED:20240705T192124Z
UID:3309-1606928400-1606932000@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, On common graphs
DESCRIPTION:A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is minimised by the random colouring. Burr and Rosta\, extending a famous conjecture by Erdős\, conjectured that every graph is common. The conjectures by Erdős and by Burr and Rosta were disproved by Thomason and by Sidorenko\, respectively\, in the late 1980s. \nDespite its importance\, the full classification of common graphs is still a wide open problem and has not seen much progress since the early 1990s. In this lecture\, I will present some old and new techniques to prove whether a graph is common or not.
URL:https://dimag.ibs.re.kr/event/2020-12-02/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201201T163000
DTEND;TZID=Asia/Seoul:20201201T173000
DTSTAMP:20260418T081432
CREATED:20201115T235924Z
LAST-MODIFIED:20240705T193016Z
UID:3273-1606840200-1606843800@dimag.ibs.re.kr
SUMMARY:Debsoumya Chakraborti\, Rainbow matchings in edge-colored simple graphs
DESCRIPTION:There has been much research on finding a large rainbow matching in a properly edge-colored graph\, where a proper edge coloring is a coloring of the edge set such that no same-colored edges are incident. Barát\, Gyárfás\, and Sárközy conjectured that in every proper edge coloring of a multigraph (with parallel edges allowed\, but not loops) with $2q$ colors where each color appears at least $q$ times\, there is always a rainbow matching of size $q$. We prove that $2q + o(q)$ colors are enough if the graph is simple\, confirming the conjecture asymptotically for simple graphs. We also make progress in the lower bound on the required number of colors for simple graphs\, which disproves a conjecture of Aharoni and Berger. We use a randomized algorithm to obtain a large rainbow matching\, and the analysis of the algorithm is based on differential equations method. We will also briefly comment on the limitations of using our probabilistic approach for the problem. This talk will be based on a joint work with Po-Shen Loh.
URL:https://dimag.ibs.re.kr/event/2020-12-01/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201130T170000
DTEND;TZID=Asia/Seoul:20201130T180000
DTSTAMP:20260418T081432
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
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201126T100000
DTEND;TZID=Asia/Seoul:20201126T110000
DTSTAMP:20260418T081432
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:20201124T163000
DTEND;TZID=Asia/Seoul:20201124T173000
DTSTAMP:20260418T081432
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:20201119T163000
DTEND;TZID=Asia/Seoul:20201119T173000
DTSTAMP:20260418T081432
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:20201111T163000
DTEND;TZID=Asia/Seoul:20201111T173000
DTSTAMP:20260418T081432
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:20201110T163000
DTEND;TZID=Asia/Seoul:20201110T173000
DTSTAMP:20260418T081432
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:20201105T100000
DTEND;TZID=Asia/Seoul:20201105T110000
DTSTAMP:20260418T081432
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:20201103T163000
DTEND;TZID=Asia/Seoul:20201103T173000
DTSTAMP:20260418T081432
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:20201027T163000
DTEND;TZID=Asia/Seoul:20201027T173000
DTSTAMP:20260418T081432
CREATED:20201009T013533Z
LAST-MODIFIED:20240707T082504Z
UID:3107-1603816200-1603819800@dimag.ibs.re.kr
SUMMARY:Jeong Ok Choi (최정옥)\, Various game-theoretic models on graphs
DESCRIPTION:We introduce some of well-known game-theoretic graph models and related problems. \nA contagion game model explains how an innovation diffuses over a given network structure and focuses on finding conditions on which structure an innovation becomes epidemic. Regular infinite graphs are interesting examples to explore. We show that regular infinite trees make an innovation least advantageous to be epidemic considering the whole class of infinite regular graphs. \nA network creation game model\, on the other hand\, tries to explain the dynamics on forming a network structure when each vertex plays independently and selfishly. An important question is how costly a formation can be made without any central coordination\, and the concept of Price of Anarchy (PoA) is introduced. In the model originally suggested by Fabrikant et al.\, PoA measures how bad the forming cost can be at Nash equilibria compared to absolute minimum\, and they conjectured that this inefficiency can happen only when some tree structures are formed (Tree Conjecture). We will introduce recent progress on this tree conjecture\, remaining open problems\, and possible variations. \nThis talk includes part of joint work with Unjong Yu.
URL:https://dimag.ibs.re.kr/event/2020-10-27/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201022T101000
DTEND;TZID=Asia/Seoul:20201022T111000
DTSTAMP:20260418T081432
CREATED:20200927T024614Z
LAST-MODIFIED:20240705T194022Z
UID:3056-1603361400-1603365000@dimag.ibs.re.kr
SUMMARY:Chun-Hung Liu (劉俊宏)\, Asymptotic dimension of minor-closed families and beyond
DESCRIPTION:The asymptotic dimension of metric spaces is an important notion in  geometric group theory. The metric spaces considered in this talk are  the ones whose underlying spaces are the vertex-sets of (edge-)weighted  graphs and whose metrics are the distance functions in weighted graphs.  A standard compactness argument shows that it suffices to consider the  asymptotic dimension of classes of finite weighted graphs. We prove that  the asymptotic dimension of any minor-closed family of weighted graphs\,  any class of weighted graphs of bounded tree-width\, and any class of  graphs of bounded layered tree-width are at most 2\, 1\, and 2\,  respectively. The first result solves a question of Fujiwara and  Papasoglu; the second and third results solve a number of questions of  Bonamy\, Bousquet\, Esperet\, Groenland\, Pirot and Scott. These bounds for  asymptotic dimension are optimal and generalize and improve some results  in the literature\, including results for Riemannian surfaces and Cayley  graphs of groups with a forbidden minor.
URL:https://dimag.ibs.re.kr/event/2020-10-22/
LOCATION:Zoom ID:95464969835 (356260)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201021T163000
DTEND;TZID=Asia/Seoul:20201021T173000
DTSTAMP:20260418T081432
CREATED:20200930T112510Z
LAST-MODIFIED:20240707T082519Z
UID:3085-1603297800-1603301400@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, On graph norms for complex-valued functions
DESCRIPTION:For any given graph $H$\, one may define a natural corresponding functional $\|.\|_H$ for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions\, once $H$ is paired with a $2$-edge-colouring $\alpha$ to assign conjugates. We say that $H$ is real-norming (resp. complex-norming) if $\|.\|_H$ (resp. there is $\alpha$ such that $\|.\|_{H\,\alpha}$) is a norm on the vector space of real-valued (resp. complex-valued) functions. This generalises Gowers norms\, a widely used tool in extremal combinatorics to quantify quasirandomness. \nWe unify these two seemingly different notions of graph norms in real- and complex-valued settings\, by proving that $H$ is complex-norming if and only if it is real-norming. Our proof does not explicitly construct a suitable $2$-edge-colouring $\alpha$ but obtain its existence and uniqueness\, which may be of independent interest. \nAs an application\, we give various example graphs that are not norming. In particular\, we show that hypercubes are not norming\, which answers the only question appeared in Hatami’s pioneering work in the area that remained untouched. This is joint work with Alexander Sidorenko.
URL:https://dimag.ibs.re.kr/event/2020-10-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201015T170000
DTEND;TZID=Asia/Seoul:20201015T180000
DTSTAMP:20260418T081432
CREATED:20200915T062234Z
LAST-MODIFIED:20240705T194121Z
UID:2982-1602781200-1602784800@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Cycles and trees in graphs (8/8)
DESCRIPTION:This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
URL:https://dimag.ibs.re.kr/event/2020-10-15/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Online Lecture Series
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201014T170000
DTEND;TZID=Asia/Seoul:20201014T180000
DTSTAMP:20260418T081432
CREATED:20200915T062130Z
LAST-MODIFIED:20240705T194123Z
UID:2980-1602694800-1602698400@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Cycles and trees in graphs (7/8)
DESCRIPTION:This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
URL:https://dimag.ibs.re.kr/event/2020-10-14/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Online Lecture Series
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201013T170000
DTEND;TZID=Asia/Seoul:20201013T180000
DTSTAMP:20260418T081432
CREATED:20200915T062032Z
LAST-MODIFIED:20240705T194124Z
UID:2978-1602608400-1602612000@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Cycles and trees in graphs (6/8)
DESCRIPTION:This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
URL:https://dimag.ibs.re.kr/event/2020-10-13/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Online Lecture Series
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201012T170000
DTEND;TZID=Asia/Seoul:20201012T180000
DTSTAMP:20260418T081432
CREATED:20200915T061926Z
LAST-MODIFIED:20240705T194125Z
UID:2976-1602522000-1602525600@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Cycles and trees in graphs (5/8)
DESCRIPTION:This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
URL:https://dimag.ibs.re.kr/event/2020-10-12/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Online Lecture Series
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201008T170000
DTEND;TZID=Asia/Seoul:20201008T180000
DTSTAMP:20260418T081432
CREATED:20200915T061756Z
LAST-MODIFIED:20240705T194127Z
UID:2974-1602176400-1602180000@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Cycles and trees in graphs (4/8)
DESCRIPTION:This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
URL:https://dimag.ibs.re.kr/event/2020-10-08/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Online Lecture Series
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201007T170000
DTEND;TZID=Asia/Seoul:20201007T180000
DTSTAMP:20260418T081432
CREATED:20200915T061653Z
LAST-MODIFIED:20240705T194128Z
UID:2971-1602090000-1602093600@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Cycles and trees in graphs (3/8)
DESCRIPTION:This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
URL:https://dimag.ibs.re.kr/event/2020-10-07/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Online Lecture Series
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201006T170000
DTEND;TZID=Asia/Seoul:20201006T180000
DTSTAMP:20260418T081432
CREATED:20200915T060857Z
LAST-MODIFIED:20240705T194130Z
UID:2969-1602003600-1602007200@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Cycles and trees in graphs (2/8)
DESCRIPTION:This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
URL:https://dimag.ibs.re.kr/event/2020-10-06/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Online Lecture Series
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201005T170000
DTEND;TZID=Asia/Seoul:20201005T180000
DTSTAMP:20260418T081432
CREATED:20200915T060706Z
LAST-MODIFIED:20240705T194131Z
UID:2967-1601917200-1601920800@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Cycles and trees in graphs (1/8)
DESCRIPTION:This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
URL:https://dimag.ibs.re.kr/event/2020-10-05/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Online Lecture Series
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200929T163000
DTEND;TZID=Asia/Seoul:20200929T173000
DTSTAMP:20260418T081432
CREATED:20200921T045326Z
LAST-MODIFIED:20240705T194112Z
UID:3014-1601397000-1601400600@dimag.ibs.re.kr
SUMMARY:Minki Kim (김민기)\, Complexes of graphs with bounded independence number
DESCRIPTION:Let $G$ be a graph on $V$ and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose faces are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of $I_n(G)$ for various classes of graphs\, focusing on the class of graphs with bounded maximum degree. This is joint work with Alan Lew.
URL:https://dimag.ibs.re.kr/event/2020-09-29/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200924T100000
DTEND;TZID=Asia/Seoul:20200924T110000
DTSTAMP:20260418T081432
CREATED:20200811T231744Z
LAST-MODIFIED:20240707T082720Z
UID:2781-1600941600-1600945200@dimag.ibs.re.kr
SUMMARY:Zihan Tan\, Towards Tight(er) Bounds for the Excluded Grid Theorem
DESCRIPTION:We study the Excluded Grid Theorem\, a fundamental structural result in graph theory\, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f$\, such that for every integer $g > 0$\, every graph of treewidth at least $f(g)$ contains the g×g-grid as a minor. For every integer $g > 0$\, let $f(g)$ be the smallest value for which the theorem holds. Establishing tight bounds on $f(g)$ is an important graph-theoretic question. Robertson and Seymour showed that f(g) is at least of order $g^2 \log g$. For a long time\, the best known upper bounds on $f(g)$ were super-exponential in $g$. The first polynomial upper bound of $f(g) = O(g^{98} \operatorname{poly log} g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36} \operatorname{poly log} g)$\, and then to $f(g) = O(g^{19} \operatorname{poly log} g)$. In this talk\, we present our recent work that further improves this bound to $f(g) = O(g^9 \operatorname{poly log} g)$ via a simpler proof. Moreover\, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem\, it seems conceivable that the techniques proposed in this talk can lead to even tighter bounds on $f(g)$. \nThis talk is based on joint work with Julia Chuzhoy.
URL:https://dimag.ibs.re.kr/event/2020-09-24/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200922T163000
DTEND;TZID=Asia/Seoul:20200922T173000
DTSTAMP:20260418T081432
CREATED:20200914T065243Z
LAST-MODIFIED:20240707T082727Z
UID:2960-1600792200-1600795800@dimag.ibs.re.kr
SUMMARY:Jinha Kim (김진하)\, Collapsibility of Non-Cover Complexes of Graphs
DESCRIPTION:Let $G$ be a graph on the vertex set $V$. A vertex subset $W \subset V$ is a cover of $G$ if $V \setminus W$ is an independent set of $G$\, and $W$ is a non-cover of $G$ if $W$ is not a cover of $G$. The non-cover complex of $G$ is a simplicial complex on $V$ whose faces are non-covers of $G$. Then the non-cover complex of $G$ is the combinatorial Alexander dual of the independence complex of $G$. In this talk\, I will show the $(|V(G)|-i\gamma(G)-1)$-collapsibility of the non-cover complex of a graph $G$ where $i\gamma(G)$ denotes the independence domination number of $G$ using the minimal exclusion sequence method. This is joint work with Ilkyoo Choi and Boram Park.
URL:https://dimag.ibs.re.kr/event/2020-09-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200917T100000
DTEND;TZID=Asia/Seoul:20200917T110000
DTSTAMP:20260418T081432
CREATED:20200811T231948Z
LAST-MODIFIED:20240707T082734Z
UID:2789-1600336800-1600340400@dimag.ibs.re.kr
SUMMARY:Luke Postle\, Further progress towards Hadwiger's conjecture
DESCRIPTION:In 1943\, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s\, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.  Recently\, Norin\, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$\, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^{\beta})$-colorable for every $\beta > 0$; more specifically\, they are $O(t (\log \log t)^{6})$-colorable.
URL:https://dimag.ibs.re.kr/event/2020-09-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200915T163000
DTEND;TZID=Asia/Seoul:20200915T173000
DTSTAMP:20260418T081432
CREATED:20200901T083403Z
LAST-MODIFIED:20240705T194142Z
UID:2919-1600187400-1600191000@dimag.ibs.re.kr
SUMMARY:Debsoumya Chakraborti\, Maximum number of cliques in a graph with bounded maximum degree
DESCRIPTION:Generalized extremal problems have been one of the central topics of study in extremal combinatorics throughout the last few decades. One such simple-looking problem\, maximizing the number of cliques of a fixed order in a graph with a fixed number of vertices and given maximum degree\, was recently resolved by Chase. Settling a conjecture of Kirsch and Radcliffe\, we resolve the edge variant of this problem\, where the number of edges is fixed instead of the number of vertices. This talk will be based on joint work with Da Qi Chen.
URL:https://dimag.ibs.re.kr/event/2020-09-15/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200910T171000
DTEND;TZID=Asia/Seoul:20200910T181000
DTSTAMP:20260418T081432
CREATED:20200708T123031Z
LAST-MODIFIED:20240705T200015Z
UID:2619-1599757800-1599761400@dimag.ibs.re.kr
SUMMARY:Sebastian Siebertz\, Rank-width meets stability
DESCRIPTION:Forbidden graph characterizations provide a convenient way of specifying graph classes\, which often exhibit a rich combinatorial and algorithmic theory. A prime example in graph theory are classes of bounded tree-width\, which are characterized as those classes that exclude some planar graph as a minor. Similarly\, in model theory\, classes of structures are characterized by configurations that are forbidden as logical interpretations or transductions. Two notions from classical model theory are (monadic) stability and (monadic) dependence\, which correspond to the impossibility of interpreting with first-order logic (after a vertex coloring step) arbitrary long linear orders and all graphs\, respectively.  Examples of monadically stable classes of graphs are nowhere dense graph classes\, and examples of monadically dependent classes are classes of bounded rank-width (or equivalently\, bounded clique-width)\, which can be seen as a dense analog of classes of bounded tree-width. \nI will give an overview over recent approaches to combine model theoretic and graph theoretic tools to derive structural and algorithmic results for classes of (finite) graphs. I assume no background from logic.
URL:https://dimag.ibs.re.kr/event/2020-09-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200908T163000
DTEND;TZID=Asia/Seoul:20200908T173000
DTSTAMP:20260418T081432
CREATED:20200820T123810Z
LAST-MODIFIED:20240705T194152Z
UID:2831-1599582600-1599586200@dimag.ibs.re.kr
SUMMARY:Rutger Campbell\, Disasters in abstracting combinatorial properties of linear dependence
DESCRIPTION:Let E be a finite set and I be a collection of subsets of E. When is there a set of real vectors indexed by E such that I correspond to its linearly independent subsets? In 1935\, Whitney introduced matroids using some necessary conditions for this. However\, complete characterizations with various techniques are intractable. This remains the case even if it is already known that there is a set of complex vectors indexed by E whose collection of linearly independent subsets corresponds to I.
URL:https://dimag.ibs.re.kr/event/2020-09-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200901T103000
DTEND;TZID=Asia/Seoul:20200901T113000
DTSTAMP:20260418T081432
CREATED:20200825T130632Z
LAST-MODIFIED:20240707T082809Z
UID:2855-1598956200-1598959800@dimag.ibs.re.kr
SUMMARY:Junguk Lee (이정욱)\, A quick introduction to stability and NIP: Part III. NIP
DESCRIPTION:I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. We review basic properties of stability and NIP. Finally\, we aim to give several characterizations of stability and NIP of a given formula in terms of counting types and definability types.
URL:https://dimag.ibs.re.kr/event/2020-09-01/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200831T161500
DTEND;TZID=Asia/Seoul:20200831T171500
DTSTAMP:20260418T081432
CREATED:20200825T130503Z
LAST-MODIFIED:20240707T082818Z
UID:2851-1598890500-1598894100@dimag.ibs.re.kr
SUMMARY:Junguk Lee (이정욱)\, A quick introduction to stability and NIP: Part II. Stability
DESCRIPTION:I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. We review basic properties of stability and NIP. Finally\, we aim to give several characterizations of stability and NIP of a given formula in terms of counting types and definability types.
URL:https://dimag.ibs.re.kr/event/2020-08-31-part2/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR