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:20210317T170000
DTEND;TZID=Asia/Seoul:20210317T180000
DTSTAMP:20260418T090828
CREATED:20210228T115822Z
LAST-MODIFIED:20240705T190042Z
UID:3692-1616000400-1616004000@dimag.ibs.re.kr
SUMMARY:Yixin Cao (操宜新)\, Recognizing (unit) interval graphs by zigzag graph searches
DESCRIPTION:Corneil\, Olariu\, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics & Theoretical Computer Science 2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for Li and Wu’s algorithm\, as well as a simpler implementation. We also give a self-contained presentation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs\, based on three sweeps of graph searches. Moreover\, we show that two sweeps are already sufficient. Toward the proofs of the main results\, we make several new structural observations that might be of independent interests.
URL:https://dimag.ibs.re.kr/event/2021-03-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210217T100000
DTEND;TZID=Asia/Seoul:20210217T110000
DTSTAMP:20260418T090828
CREATED:20201231T022333Z
LAST-MODIFIED:20240707T081843Z
UID:3423-1613556000-1613559600@dimag.ibs.re.kr
SUMMARY:David Wood\, Tree densities of sparse graph classes
DESCRIPTION:This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $\mathcal{G}$ as $n\to \infty$? I will answer this question for a variety of sparse graph classes $\mathcal{G}$. In particular\, we show that the answer is $\Theta(n^{\alpha_d(T)})$ where $\alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$\, for some integer $d$ that depends on $\mathcal{G}$. For example\, when $\mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $\mathcal{G}$ is the class of graphs containing no $K_{s\,t}$-minor ($t\geq s$) then $d=s-1$; and when $\mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs. This is joint work with Tony Huynh (arXiv:2009.12989).
URL:https://dimag.ibs.re.kr/event/2021-02-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210210T163000
DTEND;TZID=Asia/Seoul:20210210T173000
DTSTAMP:20260418T090828
CREATED:20201231T073729Z
LAST-MODIFIED:20240705T191150Z
UID:3428-1612974600-1612978200@dimag.ibs.re.kr
SUMMARY:Jie Ma (马杰)\, Non-repeated cycle lengths and Sidon sequences
DESCRIPTION:We prove a conjecture of Boros\, Caro\, Furedi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths\, which is a restricted version of a longstanding problem of Erdos. Our proof together with the matched lower bound construction of Boros\, Caro\, Furedi and Yuster show that this problem can be conceptually reduced to the seminal problem of finding the maximum Sidon sequences in number theory. Joint work with Tianchi Yang.
URL:https://dimag.ibs.re.kr/event/2021-02-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210203T163000
DTEND;TZID=Asia/Seoul:20210203T173000
DTSTAMP:20260418T090828
CREATED:20201106T054235Z
LAST-MODIFIED:20240705T193028Z
UID:3241-1612369800-1612373400@dimag.ibs.re.kr
SUMMARY:Ron Aharoni\, Colorful KKM and multiple cakes division
DESCRIPTION:In the “cake partition” problem n players have each a list of preferred parts for any partition of the [0\,1] interval (“cake”) into n sub-intervals. Woodall\, Stromquist and Gale proved independently that under mild conditions on the list of preferences (like continuity) there is always a partition and assignment of parts to the players\, in which every player gets a piece belonging to her list of preferred parts. In fact\, Gale proved a colorful version of the famous KKM theorem\, not realizing that this is the same problem\, but on the other hand\, proved the problem its proper setting. I will discuss the case of partitioning more than one cake – how many players can you make happy\, when there is a general number of cakes\, and general number of players. \nJoint work with Eli Berger\, Joseph Briggs\, Erel Segal-Halevi and Shira Zerbib.
URL:https://dimag.ibs.re.kr/event/2021-02-03/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210127T100000
DTEND;TZID=Asia/Seoul:20210127T110000
DTSTAMP:20260418T090828
CREATED:20210114T124234Z
LAST-MODIFIED:20240705T191135Z
UID:3500-1611741600-1611745200@dimag.ibs.re.kr
SUMMARY:Dong Yeap Kang (강동엽)\, A proof of the Erdős-Faber-Lovász conjecture
DESCRIPTION:A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős\, Faber\, and Lovász in 1972\, states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. \nIn this talk\, I will present the ideas to prove the conjecture for all large $n$. This is joint work with Tom Kelly\, Daniela Kühn\, Abhishek Methuku\, and Deryk Osthus.
URL:https://dimag.ibs.re.kr/event/2021-01-27/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210120T163000
DTEND;TZID=Asia/Seoul:20210120T173000
DTSTAMP:20260418T090828
CREATED:20201211T084524Z
LAST-MODIFIED:20240707T081951Z
UID:3358-1611160200-1611163800@dimag.ibs.re.kr
SUMMARY:Yusuke Kobayashi (小林 佑輔)\, An FPT Algorithm for Minimum Additive Spanner Problem
DESCRIPTION:For a positive integer t and a graph G\, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph\, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive t-spanners\, Minimum Additive t-Spanner Problem is hard to handle\, and hence only few results are known for it. In this talk\, we study Minimum Additive t-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter\, and give a fixed-parameter algorithm for it. We also extend our result to (α\,β)-spanners.
URL:https://dimag.ibs.re.kr/event/2021-01-20/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210113T100000
DTEND;TZID=Asia/Seoul:20210113T110000
DTSTAMP:20260418T090828
CREATED:20201126T045239Z
LAST-MODIFIED:20240705T192124Z
UID:3318-1610532000-1610535600@dimag.ibs.re.kr
SUMMARY:Rose McCarty\, Vertex-minors and flooding immersions
DESCRIPTION:An immersion of a graph H into a graph G sends edges of H into edge-disjoint trails of G. We say the immersion is flooding if every edge of G is in one of the trails. Flooding immersions are interesting for Eulerian group-labelled graphs; in this context they behave quite differently from regular immersions. Moreover\, understanding such flooding immersions is a vital step towards understanding the structure of graphs with a forbidden vertex-minor. \nI will focus on explaining the connection to vertex-minors\, and on recent progress in this direction from ongoing joint work with Jim Geelen and Paul Wollan.
URL:https://dimag.ibs.re.kr/event/2021-01-13/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201230T100000
DTEND;TZID=Asia/Seoul:20201230T110000
DTSTAMP:20260418T090828
CREATED:20201220T231608Z
LAST-MODIFIED:20240707T082035Z
UID:3389-1609322400-1609326000@dimag.ibs.re.kr
SUMMARY:Paul Seymour\, The Erdős-Hajnal conjecture is true for excluding a five-cycle
DESCRIPTION:In an n-vertex graph\, there must be a clique or stable set of size at least $C\log n$\, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph\, the largest clique or stable set is bigger. \nErdős and Hajnal conjectured in 1977 that for every graph H\, there exists c>0 such that every H-free graph has a clique or stable set of size at least $|G|^c$ (“H-free” means not containing H as an induced subgraph\, and |G| means the number of vertices of G). This is still open\, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five. \nIt is true in that case. We will give a sketch of the proof\, which is via applying a lemma about bipartite graphs\, a variant of a theorem of I. Tomon. \nThis lemma has several other applications to the Erdős-Hajnal conjecture. For instance\, it implies that for every cycle C and forest T\, there exists c>0 such that every graph that is both C-free and T’-free (where T’ is the complement of T) has a clique or stable set of size $|G|^c$. (Until now this was open when C has length five and T is a 5-vertex path.) \nJoint work with Maria Chudnovsky\, Alex Scott and Sophie Spirkl.
URL:https://dimag.ibs.re.kr/event/2020-12-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201217T100000
DTEND;TZID=Asia/Seoul:20201217T110000
DTSTAMP:20260418T090828
CREATED:20201028T010135Z
LAST-MODIFIED:20240707T082135Z
UID:3210-1608199200-1608202800@dimag.ibs.re.kr
SUMMARY:Jaiung Jun (전재웅)\, On the Hopf algebra of multi-complexes
DESCRIPTION:In combinatorics\, Hopf algebras appear naturally when studying various classes of combinatorial objects\, such as graphs\, matroids\, posets or symmetric functions. Given such a class of combinatorial objects\, basic information on these objects regarding assembly and disassembly operations are encoded in the algebraic structure of a Hopf algebra. One then hopes to use algebraic identities of a Hopf algebra to return to combinatorial identities of combinatorial objects of interest. \nIn this talk\, I introduce a general class of combinatorial objects\, which we call multi-complexes\, which simultaneously generalizes graphs\, hypergraphs and simplicial and delta complexes. I also introduce a combinatorial Hopf algebra obtained from multi-complexes. Then\, I describe the structure of the Hopf algebra of multi-complexes by finding an explicit basis of the space of primitives\, which is of combinatorial relevance. If time permits\, I will illustrate some potential applications. \nThis is joint work with Miodrag Iovanov.
URL:https://dimag.ibs.re.kr/event/2020-12-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201209T163000
DTEND;TZID=Asia/Seoul:20201209T173000
DTSTAMP:20260418T090828
CREATED:20201013T135938Z
LAST-MODIFIED:20240705T193042Z
UID:3125-1607531400-1607535000@dimag.ibs.re.kr
SUMMARY:Karl Heuer\, Even Circuits in Oriented Matroids
DESCRIPTION:In this talk I will state a generalisation of the even directed cycle problem\, which asks whether a given digraph contains a directed cycle of even length\, to orientations of regular matroids. Motivated by this problem\, I will define non-even oriented matroids generalising non-even digraphs\, which played a central role in resolving the computational complexity of the even dicycle problem. Then I will present and discuss our two results regarding these notions: \nFirst we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. \nSecond and with the main focus for this talk\, we shall characterise the class of non-even oriented bond matroids in terms of forbidden minors\, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen. The second result makes use of a new concept of minors for oriented matroids\, which generalises butterfly minors for digraphs to oriented matroids. \nThe part of this talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory. \nThis talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht. \n[1] K. Heuer\, R. Steiner and S. Wiederrecht\, Even Circuits in Oriented Matroids\, arxiv:2010.08988
URL:https://dimag.ibs.re.kr/event/2020-12-09/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201203T163000
DTEND;TZID=Asia/Seoul:20201203T173000
DTSTAMP:20260418T090828
CREATED:20201013T135812Z
LAST-MODIFIED:20240705T194003Z
UID:3122-1607013000-1607016600@dimag.ibs.re.kr
SUMMARY:Deniz Sarikaya\, What means Hamiltonicity for infinite graphs and how to force it via forbidden induced subgraphs
DESCRIPTION:The study of Hamiltonian graphs\, i.e. finite graphs having a cycle that contains all vertices of the graph\, is a central theme of finite graph theory. For infinite graphs such a definition cannot work\, since cycles are finite. We shall debate possible concepts of Hamiltonicity for infinite graphs and eventually follow the topological approach by Diestel and Kühn [2\,3]\, which allows to generalize several results about being a Hamiltonian graph to locally finite graphs\, i.e. graphs where each vertex has finite degree. An infinite cycle of a locally finite connected graph G is defined as a homeomorphic image of the unit circle $S^1$  in the Freudenthal compactification |G| of G. Now we call G Hamiltonian if there is an infinite cycle in |G| containing all vertices of G. For an introduction see [1]. \nWe examine how to force Hamiltonicity via forbidden induced subgraphs and present recent extensions of results for Hamiltonicity in finite claw-free graphs to locally finite ones. The first two results are about claw- and net-free graphs\, claw- and bull-free graphs\, the last also about further graph classes being structurally richer\, where we focus on paws as relevant subgraphs\, but relax the condition of forbidding them as induced subgraphs. \nThe goal of the talk is twofold: (1) We introduce the history of the topological viewpoint and argue that there are some merits to it (2) sketch the proofs for the results mentioned above in some details. \nThis is based on joint work [4\,5] with Karl Heuer. \nBibliography\n[1] R. Diestel (2017) Infinite Graphs. In: Graph Theory. Graduate Texts in Mathematics\, vol 173. Springer\, Berlin\, Heidelberg. https://doi.org/10.1007/978-3-662-53622-3_8 \n[2] R. Diestel and D. Kühn\, On infinite cycles I\, Combinatorica 24 (2004)\, pp. 69-89. \n[3] R. Diestel and D. Kühn\, On infinite cycles II\, Combinatorica 24 (2004)\, pp. 91-116. \n[4] K. Heuer and D. Sarikaya\, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs I: nets and bulls\, arXiv:2006.09160 \n[5] K. Heuer and D. Sarikaya\, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs II: paws\, arXiv:2006.09166
URL:https://dimag.ibs.re.kr/event/2020-12-03/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201126T100000
DTEND;TZID=Asia/Seoul:20201126T110000
DTSTAMP:20260418T090828
CREATED:20201027T002159Z
LAST-MODIFIED:20240705T193041Z
UID:3195-1606384800-1606388400@dimag.ibs.re.kr
SUMMARY:Da Qi Chen\, Bipartite Saturation
DESCRIPTION:In extremal graph theory\, a graph G is H-saturated if G does not contain a copy of H but adding any missing edge to G creates a copy of H. The saturation number\, sat(n\, H)\, is the minimum number of edges in an n-vertex H-saturated graph. This class of problems was first studied by Zykov and Erdős\, Hajnal\, and Moon. They also determined the saturation number when H is a clique and classified the extremal structures. \nIn this talk\, we will focus mainly on the bipartite saturation problem (which was also first introduced by Erdős\, Hajnal\, and Moon). Here\, we always assume that both G and H are bipartite graphs. Then\, G is H-saturated if G does not contain H but adding any missing edge across the bipartition creates a copy of H. We can then similarly define sat(n\, H) as the minimum number of edges of an n-by-n bipartite graph that is also H-saturated. One of the most interesting and natural questions here is to determine the saturation number for the complete bipartite graph $K_{s\, t}$. When s=t\, the saturation number and its extremal structures were determined long ago but nothing else is known for the general case. Half a decade ago\, Gan\, Korandi\, and Sudakov gave an asymptotically tight bound that was only off by an additive constant.  We will highlight the main ideas behind that proof and show\, with some additional techniques\, how the bound can be improved to achieve tightness for the case when s=t-1. \nThis talk is based on collaborative work with Debsoumya Chakraborti and Mihir Hasabnis. See arXiv: https://arxiv.org/abs/2009.07651 for the full paper.
URL:https://dimag.ibs.re.kr/event/2020-11-26/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201119T163000
DTEND;TZID=Asia/Seoul:20201119T173000
DTSTAMP:20260418T090828
CREATED:20200927T025647Z
LAST-MODIFIED:20240705T194022Z
UID:3062-1605803400-1605807000@dimag.ibs.re.kr
SUMMARY:Yijia Chen (陈翌佳)\, Graphs of bounded shrub-depth\, through a logic lens
DESCRIPTION:Shrub-depth is a graph invariant often considered as an extension\nof tree-depth to dense graphs. In this talk I will explain our recent\nproofs of two results about graphs of bounded shrub-depth. \n\nEvery graph property definable in monadic-second order logic\,\ne.g.\, 3-colorability\, can be evaluated by Boolean circuits of constant\ndepth and polynomial size\, whose depth only depends on the\nshrub-depth of input graphs.\nGraphs of bounded shrub-depth can be characterized by\na finite set of forbidden induced subgraphs [Ganian et al. 2015].\n\nCentral to the first result is the definability in first-order logic of\ntree-models for graphs of bounded shrub-depth. For the second\nresult\, we observe that shrub-depth can be easily generalized\nto infinite graphs\, and thus some classical tools\, i.e.\, Craig’s\nInterpolation and Łoś-Tarski Theorem\, in model theory are\napplicable to graphs of bounded shrub-depth. \nThis is joint work with Jörg Flum.
URL:https://dimag.ibs.re.kr/event/2020-11-19/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201111T163000
DTEND;TZID=Asia/Seoul:20201111T173000
DTSTAMP:20260418T090828
CREATED:20200927T024800Z
LAST-MODIFIED:20240707T082419Z
UID:3059-1605112200-1605115800@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, Constant congestion bramble
DESCRIPTION:In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk\, Paweł Komosa and Manuel Sorge. \nA bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. \nBrambles are objects dual to treewidth: As shown by Seymour and Thomas\, the maximum order of a bramble in an undirected graph $G$ equals one plus the treewidth of $G$. However\, as shown by Grohe and Marx\, brambles of high order may necessarily be of exponential size: In a constant-degree $n$-vertex expander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponential in $\Omega(n^{2\delta})$ for any fixed $\delta \in (0\,\frac{1}{2}]$. On the other hand\, the combination of results of Grohe and Marx\, and Chekuri and Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order $\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{O}(k^{3/2})$. ($\widetilde{\Omega}$ and $\widetilde{O}$ hide polylogarithmic factors and divisors\, respectively.) \nWe first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2})$ and congestion $2$\, i.e.\, every vertex of $G$ is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second\, we provide a tight upper bound for the lower bound of Grohe and Marx: For every $\delta \in (0\,\frac{1}{2}]$\, every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2+\delta})$ and size $2^{\widetilde{O}(k^{2\delta})}$.
URL:https://dimag.ibs.re.kr/event/2020-11-11/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201105T100000
DTEND;TZID=Asia/Seoul:20201105T110000
DTSTAMP:20260418T090828
CREATED:20200818T142112Z
LAST-MODIFIED:20240707T082448Z
UID:2820-1604570400-1604574000@dimag.ibs.re.kr
SUMMARY:Daniel Cranston\, Vertex Partitions into an Independent Set and a Forest with Each Component Small
DESCRIPTION:For each integer $k\ge 2$\, we determine a sharp bound on\n$\operatorname{mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$\, where $I$ is an independent set and $G[F_k]$ is a forest in which each component has at most k vertices. For each $k$ we construct an infinite family of examples showing our result is best possible. Hendrey\, Norin\, and Wood asked for the largest function $g(a\,b)$ such that if $\operatorname{mad}(G) < g(a\,b)$ then $V(G)$ has a partition into sets $A$ and $B$ such that $\operatorname{mad}(G[A]) < a$ and $\operatorname{mad}(G[B]) < b$. They specifically asked for the value of $g(1\,b)$\, which corresponds to the case that $A$ is an independent set. Previously\, the only values known were $g(1\,4/3)$ and $g(1\,2)$. We find the value of $g(1\,b)$ whenever $4/3 < b < 2$. This is joint work with Matthew Yancey.
URL:https://dimag.ibs.re.kr/event/2020-11-05/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201022T101000
DTEND;TZID=Asia/Seoul:20201022T111000
DTSTAMP:20260418T090828
CREATED:20200927T024614Z
LAST-MODIFIED:20240705T194022Z
UID:3056-1603361400-1603365000@dimag.ibs.re.kr
SUMMARY:Chun-Hung Liu (劉俊宏)\, Asymptotic dimension of minor-closed families and beyond
DESCRIPTION:The asymptotic dimension of metric spaces is an important notion in  geometric group theory. The metric spaces considered in this talk are  the ones whose underlying spaces are the vertex-sets of (edge-)weighted  graphs and whose metrics are the distance functions in weighted graphs.  A standard compactness argument shows that it suffices to consider the  asymptotic dimension of classes of finite weighted graphs. We prove that  the asymptotic dimension of any minor-closed family of weighted graphs\,  any class of weighted graphs of bounded tree-width\, and any class of  graphs of bounded layered tree-width are at most 2\, 1\, and 2\,  respectively. The first result solves a question of Fujiwara and  Papasoglu; the second and third results solve a number of questions of  Bonamy\, Bousquet\, Esperet\, Groenland\, Pirot and Scott. These bounds for  asymptotic dimension are optimal and generalize and improve some results  in the literature\, including results for Riemannian surfaces and Cayley  graphs of groups with a forbidden minor.
URL:https://dimag.ibs.re.kr/event/2020-10-22/
LOCATION:Zoom ID:95464969835 (356260)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200924T100000
DTEND;TZID=Asia/Seoul:20200924T110000
DTSTAMP:20260418T090828
CREATED:20200811T231744Z
LAST-MODIFIED:20240707T082720Z
UID:2781-1600941600-1600945200@dimag.ibs.re.kr
SUMMARY:Zihan Tan\, Towards Tight(er) Bounds for the Excluded Grid Theorem
DESCRIPTION:We study the Excluded Grid Theorem\, a fundamental structural result in graph theory\, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f$\, such that for every integer $g > 0$\, every graph of treewidth at least $f(g)$ contains the g×g-grid as a minor. For every integer $g > 0$\, let $f(g)$ be the smallest value for which the theorem holds. Establishing tight bounds on $f(g)$ is an important graph-theoretic question. Robertson and Seymour showed that f(g) is at least of order $g^2 \log g$. For a long time\, the best known upper bounds on $f(g)$ were super-exponential in $g$. The first polynomial upper bound of $f(g) = O(g^{98} \operatorname{poly log} g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36} \operatorname{poly log} g)$\, and then to $f(g) = O(g^{19} \operatorname{poly log} g)$. In this talk\, we present our recent work that further improves this bound to $f(g) = O(g^9 \operatorname{poly log} g)$ via a simpler proof. Moreover\, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem\, it seems conceivable that the techniques proposed in this talk can lead to even tighter bounds on $f(g)$. \nThis talk is based on joint work with Julia Chuzhoy.
URL:https://dimag.ibs.re.kr/event/2020-09-24/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200917T100000
DTEND;TZID=Asia/Seoul:20200917T110000
DTSTAMP:20260418T090828
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:20200910T171000
DTEND;TZID=Asia/Seoul:20200910T181000
DTSTAMP:20260418T090828
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:20200826T103000
DTEND;TZID=Asia/Seoul:20200826T113000
DTSTAMP:20260418T090828
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:20200819T163000
DTEND;TZID=Asia/Seoul:20200819T173000
DTSTAMP:20260418T090828
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:20200805T163000
DTEND;TZID=Asia/Seoul:20200805T173000
DTSTAMP:20260418T090828
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:20200729T163000
DTEND;TZID=Asia/Seoul:20200729T173000
DTSTAMP:20260418T090828
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:20200722T163000
DTEND;TZID=Asia/Seoul:20200722T173000
DTSTAMP:20260418T090828
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
END:VCALENDAR