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:20200922T163000
DTEND;TZID=Asia/Seoul:20200922T173000
DTSTAMP:20260418T232010
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:20260418T232010
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:20260418T232010
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:20260418T232010
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:20260418T232010
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:20260418T232010
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:20260418T232010
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
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200831T150000
DTEND;TZID=Asia/Seoul:20200831T160000
DTSTAMP:20260418T232010
CREATED:20200825T130214Z
LAST-MODIFIED:20240707T082829Z
UID:2848-1598886000-1598889600@dimag.ibs.re.kr
SUMMARY:Junguk Lee (이정욱)\, A quick introduction to stability and NIP: Part I. Basic first order logic
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/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200826T103000
DTEND;TZID=Asia/Seoul:20200826T113000
DTSTAMP:20260418T232010
CREATED:20200629T004929Z
LAST-MODIFIED:20240705T200027Z
UID:2576-1598437800-1598441400@dimag.ibs.re.kr
SUMMARY:Nick Brettell\, On the graph width parameter mim-width
DESCRIPTION:Maximum induced matching width\, also known as mim-width\, is a width parameter for graphs introduced by Vatshelle in 2012.  This parameter can be defined over branch decompositions of a graph G\, where the width of a vertex partition (X\,Y) in G is the size of a maximum induced matching in the bipartite graph induced by edges of G with one endpoint in X and one endpoint in Y.  In this talk\, I will present a quick overview of mim-width and some key results that highlight why this parameter is of interest from both a theoretical and algorithmic point of view.  I will discuss some recent work regarding the boundedness or unboundedness of mim-width for hereditary classes defined by forbidding one or two induced subgraphs\, and for generalisations of convex graphs.  I will also touch on some interesting applications of this work\, in particular for colouring and list-colouring.  This is joint work with Jake Horsfield\, Andrea Munaro\, Giacomo Paesani\, and Daniel Paulusma.
URL:https://dimag.ibs.re.kr/event/2020-08-26/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200825T163000
DTEND;TZID=Asia/Seoul:20200825T173000
DTSTAMP:20260418T232011
CREATED:20200816T234618Z
LAST-MODIFIED:20240707T082841Z
UID:2794-1598373000-1598376600@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Point-plane incidence bounds
DESCRIPTION:In the early 1980s\, Beck proved that\, if P is a set of n points in the real plane\, and no more than g points of P lie on any single line\, then there are $\Omega(n(n-g))$ lines that each contain at least 2 points of P. In 2016\, I found a generalization of this theorem\, giving a similar lower bound on the number of planes spanned by a set of points in real space. I will discuss this result\, along with a number of applications and related open problems.
URL:https://dimag.ibs.re.kr/event/2020-08-25/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20200824
DTEND;VALUE=DATE:20200829
DTSTAMP:20260418T232011
CREATED:20191122T084127Z
LAST-MODIFIED:20240705T203020Z
UID:1878-1598227200-1598659199@dimag.ibs.re.kr
SUMMARY:2020 IBS Workshop on Extremal and Probabilistic Combinatorics (postponed)
DESCRIPTION:Date\nAugust 24\, 2020 – August 28\, 2020 \nArrival: August 23 Sunday. Departure: August 29\, Saturday \nVenue\nInstitute for Basic Science\,  55 Expo-ro\, Yuseong-gu\, Daejeon\, South Korea \nInvited Speakers\n\nJulia Böttcher\, London School of Economics\nBoris Bukh\, Carnegie Mellon University\nAmin Coja-Oghlan\, Goethe University\nDavid Conlon\, Caltech\nPenny Haxell\, University of Waterloo\nHao Huang\, Emory University\nJeff Kahn\, Rutgers University\nAlexandr V. Kostochka\, University of Illinois at Urbana-Champaign\nMichael Krivelevich\, Tel-Aviv University\nMichał Karoński\, Adam Mickiewicz University in Poznań\nAnita Liebenau\, UNSW Sydney\nHong Liu\, University of Warwick\nTomasz Łuczak\, Adam Mickiewicz University in Poznań\nRichard Montgomery\, University of Birmingham\nTobias Müller\, Groningen University\nPéter Pál Pach\, Budapest University of Technology and Economics\nMathias Schacht\, University of Hamburg\nAsaf Shapira\, Tel-Aviv University\nJoel Spencer\, New York University\nVan Vu\, Yale University\nYufei Zhao\, MIT\nThis list is incomplete. It is subject to change.\n\nAccommodation\nLotte City Hotel and Hotel ICC are within 700m. Invited speakers will be provided an accommodation at the near-by hotels. \nOrganizers\n\nMihyun Kang\, Graz University of Technology\, Austria.\nJaehoon Kim\, KAIST\, Korea.\nSang-il Oum\, IBS Discrete Mathematics Group\, Korea and KAIST\, Korea.
URL:https://dimag.ibs.re.kr/event/2020-ibs-workshop/
LOCATION:Room B234\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20200824
DTEND;VALUE=DATE:20200825
DTSTAMP:20260418T232011
CREATED:20200804T150044Z
LAST-MODIFIED:20240705T195125Z
UID:2758-1598227200-1598313599@dimag.ibs.re.kr
SUMMARY:2020 Combinatorics Workshop
DESCRIPTION:Combinatorics Workshop (조합론 학술대회) is the biggest annual conference in combinatorics in Korea. It was firstly held in 2004 by the Yonsei University BK21 Research Group. It has been advised by the committee of discrete mathematics of the Korean Mathematical Society since 2013. The aim of this workshop is to bring active researchers with different backgrounds to discuss recent and prospective advances in combinatorics and related areas. \nOriginally\, we planned an offline workshop. However\, COVID 19 is more spreading and many participants are worried about attending an offline conference. So the schedule and venue are changed as an online workshop with Zoom. I hope that all participants generously understand this sudden change. \nInvited Speakers\n\nSejeong Bang (방세정)\, Yeungnam University\nRingi Kim (김린기)\, KAIST\nSangwook Kim (김상욱)\, Chonnam National University\nJinyoung Park (박진영)\, Institute for Advanced Study\nJongyook Park (박종육)\, Kyungpook N. University\n\nContributed speakers\n\nByung-Hak Hwang (황병학)\, Seoul National University\nJaeseong Oh (오재성)\, Seoul National University\nJun Seok Oh (오준석)\, Incheon National University\nTuan Tran\, Institute for Basic Science (IBS)\n\nMore information is available on the website https://cw2020.combinatorics.kr.
URL:https://dimag.ibs.re.kr/event/2020-combinatorics-workshop/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200819T163000
DTEND;TZID=Asia/Seoul:20200819T173000
DTSTAMP:20260418T232011
CREATED:20200629T004729Z
LAST-MODIFIED:20240705T200030Z
UID:2573-1597854600-1597858200@dimag.ibs.re.kr
SUMMARY:Gwenaël Joret\, Packing and covering balls in graphs excluding a minor
DESCRIPTION:In 2007\, Chepoi\, Estellon\, and Vaxès conjectured that there exists a universal constant $c>0$ such that the following holds for every positive integers $r$ and $k$\, and every planar graph $G$: Either $G$ contains $k$ vertex-disjoint balls of radius $r$\, or there is a subset of vertices of size at most $c k$ meeting all balls of radius $r$ in $G$. The key aspect of this conjecture is that the constant $c$ does not depend on the radius $r$ of the balls. If we were to allow this dependency\, then the statement is known to hold\, and in fact it is true in the more general setting of graph classes with bounded expansion (as proved by Dvořák). \nIn this talk I will present a proof of this conjecture. The result we prove is a bit more general: (1) The conjecture holds for every proper minor-closed class of graphs (with the constant $c$ depending on the class)\, and (2) we can even focus on any set of balls in the graph we like\, there is nothing special about taking all balls of a given radius. In other words\, we show that for every proper minor-closed class $C$ of graphs\, there exists a constant $c>0$ such that for every graph $G$ in $C$\, every set $S$ of balls in $G$\, and every positive integer $k$\, either there are $k$ vertex-disjoint balls in $S$\, or there is a subset of vertices of $G$ of size at most $c k$ meeting all balls in $S$. \nJoint work with Nicolas Bousquet\, Wouter Cames van Batenburg\, Louis\nEsperet\, William Lochet\, Carole Muller\, and François Pirot.
URL:https://dimag.ibs.re.kr/event/2020-08-19/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200818T163000
DTEND;TZID=Asia/Seoul:20200818T173000
DTSTAMP:20260418T232011
CREATED:20200804T124550Z
LAST-MODIFIED:20240707T082915Z
UID:2750-1597768200-1597771800@dimag.ibs.re.kr
SUMMARY:Tuan Tran\, Anti-concentration phenomena
DESCRIPTION:Let $X$ be a real random variable; a typical anti-concentration inequality asserts that (under certain assumptions) if an interval $I$ has small length\, then $\mathbb{P}(X\in I)$ is small\, regardless the location of $I$. Inequalities of this type have found powerful applications in many branches of mathematics. In this talk we will discuss several recent applications of anti-concentration inequalities in extremal combinatorics\, as well as random matrix theory. The talk is partially based on joint work with Matthew Kwan and Benny Sudakov.
URL:https://dimag.ibs.re.kr/event/2020-08-18/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200811T163000
DTEND;TZID=Asia/Seoul:20200811T173000
DTSTAMP:20260418T232011
CREATED:20200725T052636Z
LAST-MODIFIED:20240707T082925Z
UID:2708-1597163400-1597167000@dimag.ibs.re.kr
SUMMARY:Yunbum Kook (국윤범)\, Vertex Sparsification for Edge Connectivity
DESCRIPTION:Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal\, we initiate the study of a thresholded version of the problem: for a given parameter $c$\, find a smaller graph\, which we call connectivity-$c$ mimicking network\, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that contraction-based connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist by (1) introducing an extension of well-linkedness to a thresholded $c$-connectivity setting and (2) leveraging a kernelization result\, based on gammoid and the representative sets lemma\, to identify `essential edges’ in minimum edge cuts between a partition of terminals. We also develop an algorithm based on expander decomposition\, which can find a contraction-based $c$-mimicking network of the optimal size in $m(c\log n)^{O(c)}$. \nThese results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c \ge 4$ in polylogarithmic time per query\, as well as more efficient algorithms for survivable network design on bounded treewidth graphs. \nThis is a joint work with Parinya Chalermsook\, Syamantak Das\, Bundit Laekhanukit\, Yang P. Liu\, Richard Peng\, Mark Sellke\, and Daniel Vaz.
URL:https://dimag.ibs.re.kr/event/2020-08-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20200810
DTEND;VALUE=DATE:20200814
DTSTAMP:20260418T232011
CREATED:20200221T012853Z
LAST-MODIFIED:20240705T201209Z
UID:2145-1597017600-1597363199@dimag.ibs.re.kr
SUMMARY:Nonlinear Algebra in Daejeon (Postponed)
DESCRIPTION:Program\n\nSummer School @ KAIST (August 4-7\, 2020)\nDiscussion Weekend (August 8-9\, 2020)\nWorkshop @ IBS Science Culture Center (August 10-13\, 2020)\n\nWebsite: https://dimag.ibs.re.kr/home/nonlinear/ \nOrganizing Committee\n\nInsong Choe (Konkuk U.)\nKangjin Han (DGIST)\nDavid Hyeon (SNU)\nSijong Kwak (KAIST)\nYongnam Lee (KAIST)\nAnton Leykin (Georgia Tech)\nSang-il Oum (IBS & KAIST)\nFrank Sottile (TAMU)
URL:https://dimag.ibs.re.kr/event/nonlinear-algebra-in-daejeon/
LOCATION:IBS Science Culture Center
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200805T163000
DTEND;TZID=Asia/Seoul:20200805T173000
DTSTAMP:20260418T232011
CREATED:20200629T004613Z
LAST-MODIFIED:20240705T200032Z
UID:2570-1596645000-1596648600@dimag.ibs.re.kr
SUMMARY:Robert Ganian\, Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions
DESCRIPTION:Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete\, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this talk is to summarize these recent developments and put them into context. Special attention will be paid to the structural parameter treedepth\, and at the end of the talk we will also consider how treedepth can be used to design algorithms for problems beyond ILP.
URL:https://dimag.ibs.re.kr/event/2020-08-05/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200804T163000
DTEND;TZID=Asia/Seoul:20200804T173000
DTSTAMP:20260418T232011
CREATED:20200708T124259Z
LAST-MODIFIED:20240705T200010Z
UID:2626-1596558600-1596562200@dimag.ibs.re.kr
SUMMARY:June Huh (허준이)\, Kazhdan-Lusztig polynomials of graphs and matroids
DESCRIPTION:I will introduce Kazhdan-Lusztig polynomials of matroids and survey combinatorial and geometric theories built around them. The focus will be on the conjecture of Gedeon\, Proudfoot\, and Young that all zeros of the Kazhdan-Lusztig polynomial of a matroid lie on the negative real axis.
URL:https://dimag.ibs.re.kr/event/2020-08-04/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200729T163000
DTEND;TZID=Asia/Seoul:20200729T173000
DTSTAMP:20260418T232011
CREATED:20200629T004429Z
LAST-MODIFIED:20240705T200034Z
UID:2567-1596040200-1596043800@dimag.ibs.re.kr
SUMMARY:Akanksha Agrawal\, Polynomial Kernel for Interval Vertex Deletion
DESCRIPTION:Given a graph G and an integer k\, the Interval Vertex Deletion (IVD) problem asks whether there exists a vertex subset S of size at most k\, such that G-S is an interval graph. A polynomial kernel for a parameterized problem is a polynomial time preprocessing algorithm that outputs an equivalent instance of the problem whose size is bounded by a polynomial function of the parameter. The existence of a polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this talk we look at a sketch of a polynomial kernel for the problem (with the solution size as the parameter). To illustrate one of the key ingredients of our kernel\, we will look at a polynomial kernel for IVD\, when parameterized by the vertex cover number.
URL:https://dimag.ibs.re.kr/event/2020-07-29/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200728T163000
DTEND;TZID=Asia/Seoul:20200728T173000
DTSTAMP:20260418T232011
CREATED:20200708T123952Z
LAST-MODIFIED:20240707T083742Z
UID:2624-1595953800-1595957400@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, Solving hard cut problems via flow-augmentation
DESCRIPTION:We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs\, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s\, t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals s and t. \nMore precisely\, we consider problems where an (unknown) solution is a set $Z \subseteq E(G)$ of size at most $k$ such that \n\nin $G−Z$\, $s$ and $t$ are indistinct connected components\,\nevery edge of $Z$ connects two distinct connected components of $G − Z$\, and\nif we define the set $Z_{s\,t}\subseteq Z$ as these edges $e \in Z$ for which there exists an (s\, t)-path P_e with $E(P_e) ∩ Z = \{e\}$\, then $Z_{s\,t}$ separates s from t.\n\nWe prove that in the above scenario one can in randomized time $k^O(1)(|V (G)| + |E(G)|)$ add a number of edges to the graph so that with $2^{O(k \log k)}$ probability no added edge connects two components of $G − Z$ and $Z_{s\,t}$ becomes a minimum cut between $s$ and $t$. \nThis additional property becomes a handy lever in applications. For example\, consider the question of an $(s\, t)$-cut of cardinality at most k and of minimum possible weight (assuming edge weights in $G$). While the problem is NP-hard in general\, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality an $(s\, t)$-cut in G. Hence\, we immediately obtain that the aforementioned problem admits an $2^{O(k \log k)}n^O(1)$-time randomized fixed-parameter algorithm. \nWe apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below)\, and was unamenable to other techniques for parameterized algorithms in graph cut problems\, such as Randomized Contractions\, Treewidth Reduction or Shadow Removal. \nIn fact\, we go one step further. To demonstrate the power of the approach\, we consider more generally the Boolean Min CSP(Γ)-problems\, a.k.a. Min SAT(Γ)\, parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious l-Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT\, (2) W[1]-hard\, or (3) able to express the soft constraint (u → v)\, and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate\, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words\, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class\, except those that explicitly encompass directed graph cuts. \nThis is a joint work with Stefan Kratsch\, Marcin Pilipczuk and Magnus Wahlström.
URL:https://dimag.ibs.re.kr/event/2020-07-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200722T163000
DTEND;TZID=Asia/Seoul:20200722T173000
DTSTAMP:20260418T232011
CREATED:20200629T004204Z
LAST-MODIFIED:20240707T083748Z
UID:2563-1595435400-1595439000@dimag.ibs.re.kr
SUMMARY:Paloma T. Lima\, Graph Square Roots of Small Distance from Degree One Graphs
DESCRIPTION:Given a graph class $\mathcal{H}$\, the task of the $\mathcal{H}$-Square Root problem is to decide whether an input graph G has a square root H that belongs to $\mathcal{H}$. We are interested in the parameterized complexity of the problem for classes $\mathcal{H}$ that are composed by the graphs at vertex deletion distance at most $k$ from graphs of maximum degree at most one. That is\, we are looking for a square root H that has a modulator S of size k such that H-S is the disjoint union of isolated vertices and disjoint edges. We show that different variants of the problems with constraints on the number of isolated vertices and edges in H-S are FPT when parameterized by k\, by providing algorithms with running time $2^{2^{O(k)}}\cdot n^{O(1)}$. We further show that the running time of our algorithms is asymptotically optimal and it is unlikely that the double-exponential dependence on k could be avoided. In particular\, we prove that the VC-k Root problem\, that asks whether an input graph has a square root with vertex cover of size at most k\, cannot be solved in time $2^{2^{o(k)}}\cdot n^{O(1)}$ unless the Exponential Time Hypothesis fails. Moreover\, we point out that VC-k Root parameterized by k does not admit a subexponential kernel unless P=NP. \nThis is a joint work with Petr Golovach and Charis Papadopoulos.
URL:https://dimag.ibs.re.kr/event/2020-07-22/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200721T163000
DTEND;TZID=Asia/Seoul:20200721T173000
DTSTAMP:20260418T232011
CREATED:20200519T123058Z
LAST-MODIFIED:20240707T083754Z
UID:2456-1595349000-1595352600@dimag.ibs.re.kr
SUMMARY:Ilkyoo Choi (최일규)\, Flexibility of Planar Graphs
DESCRIPTION:Oftentimes in chromatic graph theory\, precoloring techniques are utilized in order to obtain the desired coloring result. For example\, Thomassen’s proof for 5-choosability of planar graphs actually shows that two adjacent vertices on the same face can be precolored. In this vein\, we investigate a precoloring extension problem formalized by Dvorak\, Norin\, and Postle named flexibility. Given a list assignment $L$ on a graph $G$\, an $L$-request is a function on a subset $S$ of the vertices that indicates a preferred color in $L(v)$ for each vertex $v\in S$. A graph $G$ is $\varepsilon$-flexible for list size $k$ if given a $k$-list assignment $L$ and an $L$-request\, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. We survey known results regarding this new concept\, and prove some new results regarding flexibility of planar graphs.
URL:https://dimag.ibs.re.kr/event/2020-07-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200714T163000
DTEND;TZID=Asia/Seoul:20200714T173000
DTSTAMP:20260418T232011
CREATED:20200708T123817Z
LAST-MODIFIED:20240707T083801Z
UID:2622-1594744200-1594747800@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Inverse Turán Problems
DESCRIPTION:For given graphs $G$ and $F$\, the Turán number $ex(G\,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Briggs and Cox introduced a dual version of this problem wherein for a given number $k$\, one maximizes the number of edges in a host graph $G$ for which $ex(G\,H) < k$.  We resolve a problem of Briggs and Cox in the negative by showing that the inverse Turán number of $C_4$ is $\Theta(k^{3/2})$. More generally\, we determine the order of magnitude of the inverse Turán number of $K_{s\,t}$ for all $s$ and $t$.  Addressing another problem of Briggs and Cox\, we determine the asymptotic value of the inverse Turán number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length.  We also obtain improved bounds on the inverse Turán number of even cycles \nJoint work with Ervin Győri\, Nika Salia and Oscar Zamora.
URL:https://dimag.ibs.re.kr/event/2020-07-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200707T163000
DTEND;TZID=Asia/Seoul:20200707T173000
DTSTAMP:20260418T232011
CREATED:20200526T020628Z
LAST-MODIFIED:20240707T083806Z
UID:2481-1594139400-1594143000@dimag.ibs.re.kr
SUMMARY:Seog-Jin Kim (김석진)\, Online DP-coloring of graphs
DESCRIPTION:Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number\, $\chi_P(G)$\, (the minimum number of colors needed for an online coloring of $G$) and the DP-chromatic number\, $\chi_{DP}(G)$\, (the minimum number of colors needed for a DP-coloring of $G$) is at least the list chromatic number\, $\chi_\ell(G)$\, of $G$ and can be much larger. On the other hand\, each of them has a number of useful properties.\nWe introduce a common generalization\, online DP-coloring\, of online list coloring and DP-coloring and to study its properties. This is joint work with Alexandr Kostochka\, Xuer Li\, and Xuding Zhu.
URL:https://dimag.ibs.re.kr/event/2020-07-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200630T163000
DTEND;TZID=Asia/Seoul:20200630T173000
DTSTAMP:20260418T232011
CREATED:20200617T222504Z
LAST-MODIFIED:20240705T200042Z
UID:2542-1593534600-1593538200@dimag.ibs.re.kr
SUMMARY:Dennis Wong\, Generating Gray codes and universal cycles for weak orders
DESCRIPTION:A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics\, designing combination locks\, and even in horse racing. In this talk\, we present new and simple algorithms to generate Gray codes and universal cycles for weak orders.
URL:https://dimag.ibs.re.kr/event/2020-06-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200623T163000
DTEND;TZID=Asia/Seoul:20200623T173000
DTSTAMP:20260418T232011
CREATED:20200611T051100Z
LAST-MODIFIED:20240707T083929Z
UID:2529-1592929800-1592933400@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, A resilience version of Pósa's theorem
DESCRIPTION:Pósa’s theorem states that any graph G whose degree sequence $d_1\leq \dots \leq d_n$ satisfies $d_i \geq i+1$ for all $i< n/2$ has a Hamilton cycle. This degree condition is best possible. We show that a similar result holds for suitable subgraphs $G$ of random graphs. This is joint work with Padraig Condon\, Alberto Espuny Diaz\, Daniela Kühn and Deryk Osthus.
URL:https://dimag.ibs.re.kr/event/2020-06-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200616T163000
DTEND;TZID=Asia/Seoul:20200616T173000
DTSTAMP:20260418T232011
CREATED:20200525T080845Z
LAST-MODIFIED:20240707T083941Z
UID:2478-1592325000-1592328600@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Fractional Helly and topological complexity
DESCRIPTION:The fractional Helly theorem is a simple yet remarkable generalization of Helly’s classical theorem on the intersection of convex sets\, and it is of considerable interest to extend the fractional Helly theorem beyond the setting of convexity. In this talk I will discuss a recent result which shows that the fractional Helly theorem holds for families of subsets of $\mathbb R^d$ which satisfy only very weak topological assumptions. The proofs combine a number of tools such as homological minors\, stair-convexity\, supersaturation in hypergraphs\, Radon dimension\, and Ramsey-type arguments. This is joint work with Xavier Goaoc and Zuzana Patáková.
URL:https://dimag.ibs.re.kr/event/2020-06-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200609T163000
DTEND;TZID=Asia/Seoul:20200609T173000
DTSTAMP:20260418T232011
CREATED:20200529T052601Z
LAST-MODIFIED:20240705T200042Z
UID:2498-1591720200-1591723800@dimag.ibs.re.kr
SUMMARY:Jiseung Kim (김지승)\, Hardness and concrete security in cryptography
DESCRIPTION:Computationally hard problems have been widely used to construct cryptographic primitives such as encryptions\, digital signatures. For example\, provably secure primitives are based on a reduction from the hardness problems. However\, the concrete instantiation of primitives does not follow the results of hardness problems due to its efficiency. In this talk\, we introduce cryptographic hardness problems widely used in cryptography and the gap between hardness results and concrete security of cryptographic primitives based on our recent works.
URL:https://dimag.ibs.re.kr/event/2020-06-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200602T163000
DTEND;TZID=Asia/Seoul:20200602T173000
DTSTAMP:20260418T232011
CREATED:20200528T061536Z
LAST-MODIFIED:20240705T200043Z
UID:2491-1591115400-1591119000@dimag.ibs.re.kr
SUMMARY:Huy-Tung Nguyen\, The average cut-rank of graphs
DESCRIPTION:The cut-rank of a set X of vertices in a graph G is defined as the rank of the X×(V(G)∖X) matrix over the binary field whose (i\,j)-entry is 1 if the vertex i in X is adjacent to the vertex j in V(G)∖X and 0 otherwise. We introduce the graph parameter called the average cut-rank of a graph\, defined as the expected value of the cut-rank of a random set of vertices. We show that this parameter does not increase when taking vertex-minors of graphs and a class of graphs has bounded average cut-rank if and only if it has bounded neighborhood diversity. This allows us to deduce that for each real α\, the list of induced-subgraph-minimal graphs having average cut-rank larger than (or at least) α is finite. We further refine this by providing an upper bound on the size of obstruction and a lower bound on the number of obstructions for average cut-rank at most (or smaller than) α for each real α≥0. Finally\, we describe explicitly all graphs of average cut-rank at most 3/2 and determine up to 3/2 all possible values that can be realized as the average cut-rank of some graph. This is joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2020-06-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200526T163000
DTEND;TZID=Asia/Seoul:20200526T173000
DTSTAMP:20260418T232011
CREATED:20200507T062724Z
LAST-MODIFIED:20240705T201016Z
UID:2430-1590510600-1590514200@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Asymptotic Structure for the Clique Density Theorem
DESCRIPTION:The famous Erdős-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts\, the asymptotic value of this extremal function for all r was determined only recently\, by Reiher [Annals of Mathematics\, 184 (2016) 683-707]. Here we describe the asymptotic structure of all almost extremal graphs. This task for r=3 was previously accomplished by Pikhurko and Razborov [Combinatorics\, Probability and Computing\, 26 (2017) 138–160].
URL:https://dimag.ibs.re.kr/event/2020-05-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR