BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20210105T163000
DTEND;TZID=Asia/Seoul:20210105T173000
DTSTAMP:20260507T051148
CREATED:20201126T024545Z
LAST-MODIFIED:20240707T082022Z
UID:3313-1609864200-1609867800@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Directed tangles and applications
DESCRIPTION:The canonical tree-decomposition theorem\, proved by Robertson and Seymour in their seminal graph minors series\, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper\, we prove the analogous result for digraphs\, the directed tangle tree-decomposition theorem. More precisely\, we introduce directed tangles and provide a directed tree-decomposition of digraphs $G$ that distinguishes all maximal directed tangles in $G$. Furthermore\, for any integer $k$\, we construct a directed tree-decomposition that distinguishes all directed tangles of order $k$\, for any integer $k$. \nBy relaxing the bound slightly\, we can make the previous result algorithmic: for fixed $k$\, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order $3k$ separated by some separation of order less than $k$. \nWe provide two direct applications of this tangle tree-decomposition theorem. First\, we show that the family of directed odd cycles has the half-integral Erdős-Pósa property\, that is\, there is a function $f:\mathbb{N}\rightarrow \mathbb{R}$ such that for every digraph $G$ and every integer $k$\, either $G$ contains a family of $k$ directed odd cycles where every vertex of $G$ is contained at most two cycles\, or a vertex subset of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral Erdős-Pósa property for undirected odd cycles\, shown by Reed [Mangoes and blueberries. Combinatorica 1999]. \nSecond\, for every fixed $k$ we show that there is a polynomial-time algorithm which\, on input $G$\, and source and sink vertices $(s_1\, t_1)\, \dots\, (s_k\, t_k)$\, either finds a family of paths $P_1\, \dots\, P_k$ such that each $P_i$ links $s_i$ to $t_i$ and every vertex of $G$ is contained in at most two paths\, or determines that there is no set of pairwise vertex-disjoint paths each connecting $s_i$  to $t_i$. This result improves previous results (with “two” replaced by “three”)\, and given known hardness results\, our result is best possible in a sense that we cannot hope for fixed parameter tractability or fully vertex-disjoint directed paths. \nThis is joint work with Archontia C. Giannopoulou\, Ken-ichi Kawarabayashi\, Stephan Kreutzer\, and Qiqin Xie.
URL:https://dimag.ibs.re.kr/event/2021-01-05/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201222T163000
DTEND;TZID=Asia/Seoul:20201222T173000
DTSTAMP:20260507T051148
CREATED:20201208T060000Z
LAST-MODIFIED:20240705T192115Z
UID:3349-1608654600-1608658200@dimag.ibs.re.kr
SUMMARY:Jinha Kim (김진하)\, On a conjecture by Kalai and Meshulam - the Betti number of the independence complex of ternary graphs
DESCRIPTION:Given a graph G=(V\,E)\, the independence complex of G is the abstract simplicial complex I(G) on V whose faces are the independent sets of G. A graph is ternary if it does not contain an induced cycle of length divisible by three. Kalai and Meshulam conjectured that if G is ternary then the sum of the Betti numbers of I(G) is either 0 or 1. In this talk\, I will introduce a result by Zhang and Wu\, which proves the Kalai-Meshulam conjecture.
URL:https://dimag.ibs.re.kr/event/2020-12-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201208T163000
DTEND;TZID=Asia/Seoul:20201208T173000
DTSTAMP:20260507T051148
CREATED:20201120T042705Z
LAST-MODIFIED:20240705T193010Z
UID:3287-1607445000-1607448600@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, A solution to Erdős and Hajnal's odd cycle problem
DESCRIPTION:I will go over the history on the study of the set of cycle lengths of graphs with large average degree or chromatic number\, and discuss recent work with Richard Montgomery on this topic. In particular\, we will see the divergence of harmonic sum of odd cycle lengths in graphs with large chromatic number and the appearance of cycle lengths in very sparse sequences (such as powers of 2). The methods developed in this work allows also us to embed equally divided clique subdivisions\, which was conjectured by Thomassen.
URL:https://dimag.ibs.re.kr/event/2020-12-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201202T170000
DTEND;TZID=Asia/Seoul:20201202T180000
DTSTAMP:20260507T051148
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:20260507T051148
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:20260507T051148
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:20201124T163000
DTEND;TZID=Asia/Seoul:20201124T173000
DTSTAMP:20260507T051148
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:20201110T163000
DTEND;TZID=Asia/Seoul:20201110T173000
DTSTAMP:20260507T051148
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:20201103T163000
DTEND;TZID=Asia/Seoul:20201103T173000
DTSTAMP:20260507T051148
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:20260507T051148
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:20201021T163000
DTEND;TZID=Asia/Seoul:20201021T173000
DTSTAMP:20260507T051148
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:20200929T163000
DTEND;TZID=Asia/Seoul:20200929T173000
DTSTAMP:20260507T051148
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:20200922T163000
DTEND;TZID=Asia/Seoul:20200922T173000
DTSTAMP:20260507T051148
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:20200915T163000
DTEND;TZID=Asia/Seoul:20200915T173000
DTSTAMP:20260507T051148
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:20200908T163000
DTEND;TZID=Asia/Seoul:20200908T173000
DTSTAMP:20260507T051148
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:20260507T051148
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:20260507T051148
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:20260507T051148
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:20200825T163000
DTEND;TZID=Asia/Seoul:20200825T173000
DTSTAMP:20260507T051148
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;TZID=Asia/Seoul:20200818T163000
DTEND;TZID=Asia/Seoul:20200818T173000
DTSTAMP:20260507T051148
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:20260507T051148
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;TZID=Asia/Seoul:20200804T163000
DTEND;TZID=Asia/Seoul:20200804T173000
DTSTAMP:20260507T051148
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:20200728T163000
DTEND;TZID=Asia/Seoul:20200728T173000
DTSTAMP:20260507T051148
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:20200721T163000
DTEND;TZID=Asia/Seoul:20200721T173000
DTSTAMP:20260507T051148
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:20260507T051148
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:20260507T051148
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:20260507T051148
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:20260507T051148
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:20260507T051148
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:20260507T051148
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
END:VCALENDAR