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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221108T163000
DTEND;TZID=Asia/Seoul:20221108T173000
DTSTAMP:20260419T190556
CREATED:20221018T044028Z
LAST-MODIFIED:20240707T074529Z
UID:6364-1667925000-1667928600@dimag.ibs.re.kr
SUMMARY:Jungho Ahn (안정호)\, Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
DESCRIPTION:Let $\mathcal{F}$ be a family of graphs\, and let $p$ and $r$ be nonnegative integers.\nThe $(p\,r\,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$\, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^p\setminus N_G^r[D]$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$\, where $G^p$ is the $p$-th power of $G$ and $N^r_G[D]$ is the set of all vertices in $G$ at distance at most $r$ from $D$ in $G$. The $(p\,r\,\mathcal{F})$-Packing problem asks whether for a graph $G$ and an integer $k$\, $G^p$ has $k$ induced subgraphs $H_1\,\ldots\,H_k$ such that each $H_i$ is isomorphic to a graph in $\mathcal{F}$\, and for distinct $i\,j\in \{1\, \ldots\, k\}$\, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. The $(p\,r\,\mathcal{F})$-Covering problem generalizes Distance-$r$ Dominating Set and Distance-$r$ Vertex Cover\, and the $(p\,r\,\mathcal{F})$-Packing problem generalizes Distance-$r$ Independent Set and Distance-$r$ Matching. By taking $(p’\,r’\,\mathcal{F}’)=(pt\, rt\, \mathcal{F})$\, we may formulate the $(p\,r\,\mathcal{F})$-Covering and $(p\, r\, \mathcal{F})$-Packing problems on the $t$-th power of a graph. Moreover\, $(1\,0\,\mathcal{F})$-Covering is the $\mathcal{F}$-Free Vertex Deletion problem\, and $(1\,0\,\mathcal{F})$-Packing is the Induced-$\mathcal{F}$-Packing problem. \nWe show that for every fixed nonnegative integers $p\,r$ and every fixed nonempty finite family $\mathcal{F}$ of connected graphs\, the $(p\,r\,\mathcal{F})$-Covering problem with $p\leq2r+1$ and the $(p\,r\,\mathcal{F})$-Packing problem with $p\leq2\lfloor r/2\rfloor+1$ admit almost linear kernels on every nowhere dense class of graphs\, and admit linear kernels on every class of graphs with bounded expansion\, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries\, we prove that Distance-$r$ Vertex Cover\, Distance-$r$ Matching\, $\mathcal{F}$-Free Vertex Deletion\, and Induced-$\mathcal{F}$-Packing for any fixed finite family $\mathcal{F}$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for Distance-$r$ Dominating Set by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017)\, and the result for Distance-$r$ Independent Set by Pilipczuk and Siebertz (EJC 2021). \nThis is joint work with Jinha Kim and O-joung Kwon.
URL:https://dimag.ibs.re.kr/event/2022-11-08/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221109T163000
DTEND;TZID=Asia/Seoul:20221109T173000
DTSTAMP:20260419T190556
CREATED:20221015T061909Z
LAST-MODIFIED:20240705T171133Z
UID:6342-1668011400-1668015000@dimag.ibs.re.kr
SUMMARY:Hugo Jacob\, On the parameterized complexity of computing tree-partitions
DESCRIPTION:Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender\, Cornelissen\, and van der Wegen\, we consider the parameterized problem of computing a decomposition. We prove that computing an optimal tree-partition is XALP-complete\, which is likely to exclude FPT algorithms. However\, we prove that computing a tree-partition of approximate width is tractable using a relatively simple sketch. This is sufficient to remove the requirement of having a given tree-partition for FPT algorithms. Our simple sketch can be adapted for several regimes within polynomial time and FPT time. Furthermore\, we adapt some simple structural results about the tree-partition-width of subdivisions\, and use them to compare tree-cut width and tree-partition-width. \nBased on joint work with Hans Bodlaender and Carla Groenland.
URL:https://dimag.ibs.re.kr/event/2022-11-09/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221115T163000
DTEND;TZID=Asia/Seoul:20221115T173000
DTSTAMP:20260419T190556
CREATED:20221011T041240Z
LAST-MODIFIED:20240705T171137Z
UID:6283-1668529800-1668533400@dimag.ibs.re.kr
SUMMARY:Sebastian Wiederrecht\, Excluding single-crossing matching minors in bipartite graphs
DESCRIPTION:By a seminal result of Valiant\, computing the permanent of (0\, 1)-matrices is\, in general\, #P-hard. In 1913 Pólya asked for which (0\, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975\, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding $K_{3\,3}$ as a matching minor. This was turned into a polynomial time algorithm by McCuaig\, Robertson\, Seymour\, and Thomas in 1999. However\, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K3\,3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0\, 1)-matrices can be computed efficiently. \nIn this paper we unify the two results above into a single\, more general result in the style of the celebrated structure theorem for single-crossing minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and $K_{3\,3}$ which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover\, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude $K_{5\,5}$ as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem\, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth. \nThis is joint work with Archontia Giannopoulou and Dimitrios Thilikos.
URL:https://dimag.ibs.re.kr/event/2022-11-15/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221117T100000
DTEND;TZID=Asia/Seoul:20221117T110000
DTSTAMP:20260419T190556
CREATED:20221109T131844Z
LAST-MODIFIED:20240707T074503Z
UID:6462-1668679200-1668682800@dimag.ibs.re.kr
SUMMARY:Chong Shangguan (上官冲)\, On the sparse hypergraph problem of Brown\, Erdős and Sós
DESCRIPTION:For fixed integers $r\ge 3\, e\ge 3$\, and $v\ge r+1$\, let $f_r(n\,v\,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ distinct edges contains at least $v+1$ vertices. In 1973\, Brown\, Erdős and Sós initiated the study of the function $f_r(n\,v\,e)$ and they proved that $\Omega(n^{\frac{er-v}{e-1}})=f_r(n\,v\,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil})$. We will survey the state-of-art results about the study of $f_r(n\,er-(e-1)k+1\,e)$ and $f_r(n\,er-(e-1)k\,e)$\, where $r>k\ge 2$ and $e\ge 3$. Although these two functions have been extensively studied\, many interesting questions remain open.
URL:https://dimag.ibs.re.kr/event/2022-11-17/
LOCATION:Zoom ID: 224 221 2686 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221122T163000
DTEND;TZID=Asia/Seoul:20221122T173000
DTSTAMP:20260419T190556
CREATED:20221018T043943Z
LAST-MODIFIED:20240707T074455Z
UID:6362-1669134600-1669138200@dimag.ibs.re.kr
SUMMARY:Seonghyuk Im (임성혁)\, A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
DESCRIPTION:A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices.  A linear $3$-graph is called a Steiner triple system if each pair of two distinct vertices belong to a unique edge. \nA simple greedy algorithm shows that every $n$-vertex Steiner triple system $G$ contains all hypertrees $T$ of order at most $\frac{n+3}{2}$. On the other hand\, it is not immediately clear whether one can always find larger hypertrees in $G$. In 2011\, Goodall and de Mier proved that a Steiner triple system $G$ contains at least one spanning tree. However\, one cannot expect the Steiner triple system to contain all possible spanning trees\, as there are many Steiner triple systems that avoid numerous spanning trees as subgraphs. Hence it is natural to wonder how much one can improve the bound from the greedy algorithm. \nIndeed\, Elliott and Rödl conjectured that an $n$-vertex Steiner triple system $G$ contains all hypertrees of order at most $(1-o(1))n$. We prove the conjecture by Elliott and Rödl. \nThis is joint work with Jaehoon Kim\, Joonkyung Lee\, and Abhishek Methuku.
URL:https://dimag.ibs.re.kr/event/2022-11-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20221128
DTEND;VALUE=DATE:20221130
DTSTAMP:20260419T190556
CREATED:20221118T114614Z
LAST-MODIFIED:20240705T171025Z
UID:6495-1669593600-1669766399@dimag.ibs.re.kr
SUMMARY:The 2nd Workshop on Developments in Combinatorics
DESCRIPTION:Official website (with the abstract)\nOnline workshop “Developments in Combinatorics” \n \n\nInvited Speakers\nNov. 28 Monday\nJie Han\, Beijing Institute of Technology\n15:30 Seoul\, 14:30 Beijing\, 06:30 UK\, 07:30 EU \nJoonkyung Lee (이준경)\, Hanyang University\n16:10 Seoul\, 15:10 Beijing\, 07:10 UK\, 08:10 EU \nLior Gishboliner\, ETH Zürich\n16:50 Seoul\, 15:50 Beijing\, 07:50 UK\, 08:50 EU \nAlex Scott\, University of Oxford\n17:40 Seoul\, 16:40 Beijing\, 08:40 UK\, 09:40 EU \nDongyeap Kang (강동엽)\, University of Birmingham\n18:20 Seoul\, 17:20 Beijing\, 09:20 UK\, 10:20 EU \nNov. 29 Tuesday\nChong Shangguan\, Shandong University\n15:30 Seoul\, 14:30 Beijing\, 06:30 UK\, 07:30 EU \nZdeněk Dvořák\, Charles University\n16:10 Seoul\, 15:10 Beijing\, 07:10 UK\, 08:10 EU \nAndrzej Grzesik\, Jagiellonian University\n16:50 Seoul\, 15:50 Beijing\, 07:50 UK\, 08:50 EU \nImre Leader\, University of Cambridge\n17:40 Seoul\, 16:40 Beijing\, 08:40 UK\, 09:40 EU \nJozef Skokan\, The London School of Ecnomics and Political Science\n18:20 Seoul\, 17:20 Beijing\, 09:20 UK\, 10:20 EU \nOrganizers\n\nHong Liu\nGuanghui Wang\nBingyu Luan\n\nSponsors\n\nIBS Extremal Combinatorics and Probability Group\nShandong University\n\n 
URL:https://dimag.ibs.re.kr/event/2022-11-28/
LOCATION:Zoom ID: 346 934 4087 (202209)
CATEGORIES:Workshops and Conferences
ATTACH;FMTTYPE=image/jpeg:https://dimag.ibs.re.kr/cms/wp-content/uploads/2022/11/ecopro-sdu-workshop2022-scaled-1.jpeg
END:VEVENT
END:VCALENDAR