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:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211102T163000
DTEND;TZID=Asia/Seoul:20211102T173000
DTSTAMP:20260424T030109
CREATED:20211109T073000Z
LAST-MODIFIED:20240707T080853Z
UID:4780-1635870600-1635874200@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Maximal 3-wise intersecting families
DESCRIPTION:A family $\mathcal F$ of subsets of {1\,2\,…\,n} is called maximal k-wise intersecting if every collection of at most k members from $\mathcal F$ has a common element\, and moreover\, no set can be added to $\mathcal F$ while preserving this property. In 1974\, Erdős and Kleitman asked for the smallest possible size of a maximal k-wise intersecting family\, for k≥3. We resolve this problem for k=3 and n even and sufficiently large. \nThis is joint work with Kevin Hendrey\, Casey Tompkins\, and Tuan Tran.
URL:https://dimag.ibs.re.kr/event/2021-11-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211105T163000
DTEND;TZID=Asia/Seoul:20211105T173000
DTSTAMP:20260424T030109
CREATED:20211105T073000Z
LAST-MODIFIED:20240707T080839Z
UID:4555-1636129800-1636133400@dimag.ibs.re.kr
SUMMARY:Martin Milanič\, Tree Decompositions with Bounded Independence Number
DESCRIPTION:The independence number of a tree decomposition $\mathcal{T}$ of a graph is the smallest integer $k$ such that each bag of $\mathcal{T}$ induces a subgraph with independence number at most $k$. If a graph $G$ is given together with a tree decomposition with bounded independence number\, then the Maximum Weight Independent Set (MWIS) problem can be solved in polynomial time. Motivated by this observation\, we consider six graph containment relations—the subgraph\, topological minor\, and minor relations\, as well as their induced variants—and for each of them characterize the graphs $H$ for which any graph excluding $H$ with respect to the relation admits a tree decomposition with bounded independence number. Furthermore\, using a variety of tools including SPQR trees and potential maximal cliques\, we show how to obtain such tree decompositions efficiently. \nAs an immediate consequence\, we obtain that the MWIS problem can be solved in polynomial time in an infinite family of graph classes that properly contain the class of chordal graphs. In fact\, our approach shows that the Maximum Weight Independent $\mathcal{H}$-Packing problem\, a common generalization of the MWIS and the Maximum Weight Induced Matching problems\, can be solved in polynomial time in these graph classes. \nThis is joint work with Clément Dallard and Kenny Štorgel.
URL:https://dimag.ibs.re.kr/event/2021-11-05/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211109T163000
DTEND;TZID=Asia/Seoul:20211109T173000
DTSTAMP:20260424T030109
CREATED:20211109T073000Z
LAST-MODIFIED:20240705T181024Z
UID:4588-1636475400-1636479000@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, 2-complexes with unique embeddings in 3-space
DESCRIPTION:A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere\, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem. This is joint work with Agelos Georgakopoulos.
URL:https://dimag.ibs.re.kr/event/2021-11-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211111T163000
DTEND;TZID=Asia/Seoul:20211111T173000
DTSTAMP:20260424T030109
CREATED:20211111T073000Z
LAST-MODIFIED:20240705T181024Z
UID:4668-1636648200-1636651800@dimag.ibs.re.kr
SUMMARY:Sebastian Wiederrecht\, Matching Minors in Bipartite Graphs
DESCRIPTION:Matching minors are a specialisation of minors which preserves the existence and elementary structural properties of perfect matchings. They were first discovered as part of the study of the Pfaffian recognition problem on bipartite graphs (Polya’s Permanent Problem) and acted as a major inspiration for the definition of butterfly minors in digraphs. In this talk we consider the origin and motivation behind the study of matching minors\, the current state of the art\, and their relation to structural digraph theory. The main result is a generalisation of the structure theorem by Robertson et al. and McCuaig for $K_{3\,3}$-matching minor free bipartite graphs to bipartite graphs excluding $K_{t\,t}$ as a matching minor for general t. This generalisation can be seen as a matching theoretic version of the Flat Wall Theorem by Robertson and Seymour.
URL:https://dimag.ibs.re.kr/event/2021-11-11/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211123T163000
DTEND;TZID=Asia/Seoul:20211123T173000
DTSTAMP:20260424T030109
CREATED:20211123T073000Z
LAST-MODIFIED:20240707T080759Z
UID:4798-1637685000-1637688600@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Ramsey numbers of Boolean lattices
DESCRIPTION:The poset Ramsey number $R(Q_{m}\,Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of $Q_{m}$ or a red induced copy of $Q_{n}$. Axenovich and Walzer showed that $n+2\le R(Q_{2}\,Q_{n})\le2n+2$. Recently\, Lu and Thompson\nimproved the upper bound to $\frac{5}{3}n+2$. In this paper\, we solve this problem asymptotically by showing that $R(Q_{2}\,Q_{n})=n+O(n/\log n)$.\nJoint work with Dániel Grósz and Abhishek Methuku.
URL:https://dimag.ibs.re.kr/event/2021-11-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211125T163000
DTEND;TZID=Asia/Seoul:20211125T173000
DTSTAMP:20260424T030109
CREATED:20211125T073000Z
LAST-MODIFIED:20240705T181009Z
UID:4552-1637857800-1637861400@dimag.ibs.re.kr
SUMMARY:Tuukka Korhonen\, Fast FPT-Approximation of Branchwidth
DESCRIPTION:Branchwidth determines how graphs\, and more generally\, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. \n\nAn algorithm that for a given n-vertex graph G and integer k in time $2^{2^{O(k)}} n^2$ either constructs a rank decomposition of G of width at most 2k or concludes that the rankwidth of G is more than $k$. It also yields a $(2^{2k+1}−1)$-approximation algorithm for cliquewidth within the same time complexity\, which in turn\, improves to $f(k) n^2$ the running times of various algorithms on graphs of cliquewidth $k$. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area.\nAn algorithm that for a given n-vertex graph G and integer k in time $2^{O(k)} n$ either constructs a branch decomposition of G of width at most $2k$ or concludes that the branchwidth of G is more than $k$. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].\n\nThis is joint work with Fedor Fomin.
URL:https://dimag.ibs.re.kr/event/2021-11-25/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211130T163000
DTEND;TZID=Asia/Seoul:20211130T173000
DTSTAMP:20260424T030109
CREATED:20211130T073000Z
LAST-MODIFIED:20240707T080630Z
UID:4852-1638289800-1638293400@dimag.ibs.re.kr
SUMMARY:Seonghyuk Im (임성혁)\, Large clique subdivisions in graphs without small dense subgraphs
DESCRIPTION:What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = \Theta(\sqrt{d})$ was proved by Bollobás and Thomason and independently by Komlós and Szemerédi. This is best possible by considering a disjoint union of $K_{d\,d}$. However\, this example contains a much smaller subgraph with the almost same average degree\, for example\, one copy of $K_{d\,d}$. \nIn 2017\, Liu and Montgomery proposed the study on the parameter $c_{\varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\varepsilon d(G)$. In fact\, they conjectured that for small enough $\varepsilon>0$\, every graph $G$ of average degree $d$ contains a clique subdivision of size $\Omega(\min\{d\, \sqrt{\frac{c_{\varepsilon}(G)}{\log c_{\varepsilon}(G)}}\})$. We prove that this conjecture holds up to a multiplicative $\min\{(\log\log d)^6\,(\log \log c_{\varepsilon}(G))^6\}$-term. \nAs a corollary\, for every graph $F$\, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term. \nThis is joint work with Jaehoon Kim\, Youngjin Kim\, and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2021-11-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR