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:20180101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200609T163000 DTEND;TZID=Asia/Seoul:20200609T173000 DTSTAMP:20260418T193000 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:20260418T193000 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:20260418T193000 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 BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200519T163000 DTEND;TZID=Asia/Seoul:20200519T173000 DTSTAMP:20260418T193000 CREATED:20200422T003736Z LAST-MODIFIED:20240705T201022Z UID:2383-1589905800-1589909400@dimag.ibs.re.kr SUMMARY:O-joung Kwon (권오정)\, Mim-width: a width parameter beyond rank-width DESCRIPTION:Vatshelle (2012) introduced a width parameter called mim-width. It is based on the following cut function : for a vertex partition (A\,B) of a graph\, the complexity of this partition is computed by the size of a maximum induced matching of the bipartite subgraph induced by edges between A and B. This parameter naturally extends the expressibility power of the graph parameters clique-width and rank-width\, which have been well-developed in recent years. In a series of papers\, we explored the computational complexity of several problems\, parameterized by mim-width. We summarize known structural properties and algorithmic applications of mim-width\, and give some open problems at the end. This is joint work with Lars Jaffke\, Torstein Strømme\, and Jan Arne Telle. URL:https://dimag.ibs.re.kr/event/2020-05-19/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200512T163000 DTEND;TZID=Asia/Seoul:20200512T173000 DTSTAMP:20260418T193000 CREATED:20200417T054420Z LAST-MODIFIED:20240707T084008Z UID:2354-1589301000-1589304600@dimag.ibs.re.kr SUMMARY:Eun Jung Kim (김은정)\, Twin-width: tractable FO model checking DESCRIPTION:Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA ’14]\, we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes\, bounded rank-width graphs\, map graphs\, $K_t$-free unit $d$-dimensional ball graphs\, posets with antichains of bounded size\, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions\, witness that the twin-width is at most $d$. We show that FO model checking\, that is deciding if a given first-order formula $\phi$ evaluates to true for a given binary structure $G$ on a domain $D$\, is FPT in $|\phi|$ on classes of bounded twin-width\, provided the witness is given. More precisely\, being given a $d$-contraction sequence for $G$\, our algorithm runs in time $f(d\,|\phi|) \cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes\, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS ’15]. \nIn order to explore the limits of twin-width\, we generalize to bounded twin-width classes a result by Norine et al. [JCTB ’06] stating that proper minor-free classes are small (i.e.\, they contain at most $n! c^n$ graphs on $n$ vertices\, for some constant $c$). This implies by a counting argument that bounded-degree graphs\, interval graphs\, and unit disk graphs have unbounded twin-width. \nJoint work with Stéphan Thomassé\, Édouard Bonnet\, and Rémi Watrigant. URL:https://dimag.ibs.re.kr/event/2020-05-12/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;VALUE=DATE:20200508 DTEND;VALUE=DATE:20200510 DTSTAMP:20260418T193000 CREATED:20200221T012551Z LAST-MODIFIED:20240705T201209Z UID:2142-1588896000-1589068799@dimag.ibs.re.kr SUMMARY:KSIAM 2020 Spring Conference (cancelled) DESCRIPTION:KSIAM 2020 Spring Conference will be held at IBS from May 8\, 2020 to May 9\, 2020. \nOrganized by Korean Society for Industrial and Applied Mathematics. \nOrganizing Committee\n\nMyungjoo Kang (Seoul National University) (chair)\nAhn\, Jaemyung (KAIST)\nKwon\, Hee-Dae (Inha University)\nLee\, Eun Jung (Yonsei University)\nJang\, Bongsoo (UNIST)\nJung\, Miyoun (Hankuk University of Foreign Studies)\nKim\, Junseok (Korea University)\nOum\, Sang-il (IBS\, KAIST) URL:https://dimag.ibs.re.kr/event/ksiam-2020-spring-conference/ LOCATION:IBS Science Culture Center CATEGORIES:Workshops and Conferences END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200428T163000 DTEND;TZID=Asia/Seoul:20200428T173000 DTSTAMP:20260418T193000 CREATED:20200417T080351Z LAST-MODIFIED:20240707T084026Z UID:2361-1588091400-1588095000@dimag.ibs.re.kr SUMMARY:Seunghun Lee (이승훈)\, Leray numbers of complexes of graphs with bounded matching number DESCRIPTION:Given a graph $G$ on the vertex set $V$\, the non-matching complex of $G$\, $\mathsf{NM}_k(G)$\, is the family of subgraphs $G’ \subset G$ whose matching number $\nu(G’)$ is strictly less than $k$. As an attempt to generalize the result by Linusson\, Shareshian and Welker on the homotopy types of $\mathsf{NM}_k(K_n)$ and $\mathsf{NM}_k(K_{r\,s})$ to arbitrary graphs $G$\, we show that (i) $\mathsf{NM}_k(G)$ is $(3k-3)$-Leray\, and (ii) if $G$ is bipartite\, then $\mathsf{NM}_k(G)$ is $(2k-2)$-Leray. This result is obtained by analyzing the homology of the links of non-empty faces of the complex $\mathsf{NM}_k(G)$\, which vanishes in all dimensions $d\geq 3k-4$\, and all dimensions $d \geq 2k-3$ when $G$ is bipartite. As a corollary\, we have the following rainbow matching theorem which generalizes the result by Aharoni et. al. and Drisko’s theorem: Let $E_1\, \dots\, E_{3k-2}$ be non-empty edge subsets of a graph and suppose that $\nu(E_i\cup E_j)\geq k$ for every $i\ne j$. Then $E=\bigcup E_i$ has a rainbow matching of size $k$. Furthermore\, the number of edge sets $E_i$ can be reduced to $2k-1$ when $E$ is the edge set of a bipartite graph. \nThis is a joint work with Andreas Holmsen. URL:https://dimag.ibs.re.kr/event/2020-04-28/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200421T163000 DTEND;TZID=Asia/Seoul:20200421T173000 DTSTAMP:20260418T193000 CREATED:20200417T000545Z LAST-MODIFIED:20240705T201135Z UID:2349-1587486600-1587490200@dimag.ibs.re.kr SUMMARY:Sang-il Oum (엄상일)\, Survey on vertex-minors DESCRIPTION:For a vertex v of a graph G\, the local complementation at v is an operation to obtain a new graph denoted by G*v from G such that two distinct vertices x\, y are adjacent in G*v if and only if both x\, y are neighbors of v and x\, y are non-adjacent\, or at least one of x\, y is not a neighbor of v and x\, y are adjacent. A graph H is a vertex-minor of a graph G if H is obtained from G by a sequence of local complementation and vertex deletions. Interestingly vertex-minors have been used in the study of measurement-based quantum computing on graph states. \nMotivated by the big success of the graph minor structure theory developed deeply by Robertson and Seymour since 1980s\, we propose a similar theory for vertex-minors. This talk will illustrate similarities between graph minors and graph vertex-minors and give a survey of known theorems and open problems on vertex-minors of graphs. URL:https://dimag.ibs.re.kr/event/2020-04-21/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200414T163000 DTEND;TZID=Asia/Seoul:20200414T173000 DTSTAMP:20260418T193000 CREATED:20200409T030201Z LAST-MODIFIED:20240705T201139Z UID:2322-1586881800-1586885400@dimag.ibs.re.kr SUMMARY:Casey Tompkins\, Saturation problems in the Ramsey theory of graphs\, posets and point sets DESCRIPTION:In 1964\, Erdős\, Hajnal and Moon introduced a saturation version of Turán’s classical theorem in extremal graph theory. In particular\, they determined the minimum number of edges in a $K_r$-free\, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the Erdős-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets. \nWe also consider semisaturation problems\, wherein we allow the family to have the forbidden configuration\, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting\, we prove a semisaturation version of the Erdős-Szekeres theorem on convex $k$-gons\, as well as multiple semisaturation theorems for sequences and posets. \nThis project was joint work with Gábor Damásdi\, Balázs Keszegh\, David Malec\, Zhiyu Wang and Oscar Zamora. URL:https://dimag.ibs.re.kr/event/2020-04-14/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200407T163000 DTEND;TZID=Asia/Seoul:20200407T173000 DTSTAMP:20260418T193000 CREATED:20200403T043936Z LAST-MODIFIED:20240707T084138Z UID:2269-1586277000-1586280600@dimag.ibs.re.kr SUMMARY:Pascal Gollin\, Disjoint dijoins for classes of dibonds in finite and infinite digraphs DESCRIPTION:A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dibonds in that digraph. We call such sets dijoins. \nWoodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a digraph equals the minimum size of a dibond.\nWe study a modification of this question where we restrict our attention to certain classes of dibonds\, i.e. whether for a class $\mathfrak{B}$ of dibonds of a digraph the maximum number of disjoint edge sets meeting every dibond in $\mathfrak{B}$ equal the size a minimum dibond in $\mathfrak{B}$. \nIn particular\, we verify this questions for nested classes of dibonds\, for the class of dibonds of minimum size\, and for classes of infinite dibonds. URL:https://dimag.ibs.re.kr/event/2020-04-07/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200331T163000 DTEND;TZID=Asia/Seoul:20200331T173000 DTSTAMP:20260418T193000 CREATED:20200324T132402Z LAST-MODIFIED:20240707T084146Z UID:2222-1585672200-1585675800@dimag.ibs.re.kr SUMMARY:Ringi Kim (김린기)\, The strong clique number of graphs with forbidden cycles DESCRIPTION:The strong clique number of a graph $G$ is the maximum size of a set of edges of which every pair has distance at most two. \nIn this talk\, we prove that every  $\{C_5\,C_{2k}\}$-free graph has strong clique number at most $k\Delta(G)-(k-1)$\, which resolves a conjecture by  Cames van Batenburg et al. We also prove that every $C_{2k}$-free graph has strong clique number at most $(2k−1)\Delta(G) + (2k−1)^2$\, improving the previous known upper bound $10k^2 (\Delta(G)-1)$ due to  Cames van Batenburg et al. This is joint work with Eun-Kyung Cho\, Ilkyoo Choi\, and Boram Park. URL:https://dimag.ibs.re.kr/event/2020-03-31/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200324T163000 DTEND;TZID=Asia/Seoul:20200324T173000 DTSTAMP:20260418T193000 CREATED:20200311T074415Z LAST-MODIFIED:20240707T084154Z UID:2186-1585067400-1585071000@dimag.ibs.re.kr SUMMARY:Kevin Hendrey\, Covering radius in the Hamming permutation space DESCRIPTION:Our problem can be described in terms of a two player game\, played with the set $\mathcal{S}_n$ of permutations on $\{1\,2\,\dots\,n\}$. First\, Player 1 selects a subset $S$ of $\mathcal{S}_n$ and shows it to Player 2. Next\, Player 2 selects a permutation $p$ from $\mathcal{S}_n$ as different as possible from the permutations in $S$\, and shows it to Player 1. Finally\, Player 1 selects a permutation $q$ from $S$\, and they compare $p$ and $q$. The aim of Player 1 is to ensure that $p$ and $q$ differ in few positions\, while keeping the size of $S$ small. The function $f(n\,s)$ can be defined as the minimum size of a set $S\subseteq \mathcal{S}_n$ that Player 1 can select in order to gaurantee that $p$ and $q$ will differ in at most $s$ positions. \nI will present some recent results on the function $f(n\,s)$. We are particularly interested in determining the value $f(n\,2)$\, which would resolve a conjecture of Kézdy and Snevily that implies several famous conjectures for Latin squares. Here we improve the best known lower bound\, showing that $f(n\,2)\geqslant 3n/4$. This talk is based on joint work with Ian M. Wanless. URL:https://dimag.ibs.re.kr/event/2020-03-24/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200317T163000 DTEND;TZID=Asia/Seoul:20200317T173000 DTSTAMP:20260418T193000 CREATED:20200307T133007Z LAST-MODIFIED:20240705T201209Z UID:2180-1584462600-1584466200@dimag.ibs.re.kr SUMMARY:Dabeen Lee (이다빈)\, On a generalization of the Chvátal-Gomory closure DESCRIPTION:Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called “cutting-plane” algorithm in combination with branch-and-bound enumeration. Cutting-planes for an integer linear program are linear inequalities that are valid for all integer feasible solutions but cut off intermediate fractional solutions. \nThe Chvátal-Gomory cuts\, introduced by Gomory in 1958 and further studied by Chvátal in 1973 in relation to their applications in combinatorial optimization\, are the first class of general-purpose cutting-planes in the literature. The split cuts\, whose name was coined by Cook\, Kannan\, and Schrijver in 1980\, are another class of important cutting-planes in modern integer programming. Although there are infinitely many cuts in each class\, it is known that only finitely many of them are nonredundant\, which is related to designing a finite-convergent cutting-plane algorithm. In this talk\, we introduce a new class of cutting-planes that generalizes the Chvátal-Gomory cuts and generalizes a special case of the split cuts. As the two classic classes of cutting-planes\, we show that only a finite number of cuts can be redundant. \nThis talk is based on a joint work with Sanjeeb Dash and Oktay Günlük. URL:https://dimag.ibs.re.kr/event/2020-03-17/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200303T163000 DTEND;TZID=Asia/Seoul:20200303T173000 DTSTAMP:20260418T193000 CREATED:20200207T093644Z LAST-MODIFIED:20240707T091837Z UID:2099-1583253000-1583256600@dimag.ibs.re.kr SUMMARY:Eun-Kyung Cho (조은경)\, Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$ DESCRIPTION:Given a graph $G$\, a decomposition of $G$ is a collection of spanning subgraphs $H_1\, \ldots\, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i \in \{1\, \ldots\, t\}$. Given a positive integer $d$\, a graph is said to be $d$-degenerate if every subgraph of it has a vertex of degree at most $d$. Given a non-negative integer $h$\, we say that a graph $G$ is $(d\,h)$-decomposable if there is a decomposition of $G$ into two spanning subgraphs\, where one is a $d$-degenerate graph\, and the other is a graph with maximum degree at most $h$. \nIt is known that a planar graph is $5$-degenerate\, but not always $4$-degenerate. This implies that a planar graph is $(5\,0)$-decomposable\, but not always $(4\,0)$-decomposable. Moreover\, by related previous results\, it is known that a planar graph is $(3\,4)$- and $(2\,8)$-decomposable. \nIn this talk\, we improve these results by showing that every planar graph is $(4\,1)$-\, $(3\,2)$-\, and $(2\,6)$-decomposable. The $(4\,1)$- and $(3\,2)$-decomposabilities are sharp in the sense that the maximum degree condition cannot be reduced more. \nThis is joint work with Ilkyoo Choi\, Ringi Kim\, Boram Park\, Tingting Shan\, and Xuding Zhu. URL:https://dimag.ibs.re.kr/event/2020-03-03/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200225T163000 DTEND;TZID=Asia/Seoul:20200225T173000 DTSTAMP:20260418T193000 CREATED:20200217T133320Z LAST-MODIFIED:20240707T084212Z UID:2129-1582648200-1582651800@dimag.ibs.re.kr SUMMARY:Xin Zhang (张欣)\, On the equitable tree-coloring of graphs with low degeneracy DESCRIPTION:A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest\, and is equitable if the sizes of any two color classes differ by at most 1. The first relative result concerning the equitable tree-coloring of graphs is due to H. Fan\, H. A. Kierstead\, G. Liu\, T. Molla\, J.-L. Wu\, and X. Zhang (2011)\, who proved that any graph with maximum degree at most $\Delta$ has a $\Delta$-coloring so that each color class induces a graph with maximum degree at most 1. After that\, many results on this topic were published in the literature. For example\, L. Esperet\, L. Lemoine\, and F. Maffray (2015) showed that any planar graph admits an equitable tree-$k$-coloring for every integer $k\ge 4$，and G. Chen\, Y. Gao\, S. Shan\, G. Wang\, and J.-L. Wu (2017) proved that any 5-degenerate graph with maximum degree at most $\Delta$ admits an equitable tree-$k$-coloring for every $k\geq \lceil\frac{\Delta+1}{2}\rceil$. \nIn this talk\, we review part of the known results and the conjectures on the equitable tree-coloring of graphs\, and then show the sketch proofs of our three new results as follows: \n(a) the vertex set of any graph $G$ can be equitably partitioned into $k$ subsets for any integer $k\geq\max\{\lceil\frac{\Delta(G)+1}{2}\rceil\,\lceil\frac{|G|}{4}\rceil\}$ so that each of them induces a linear forest; \n(b) any plane graph with independent crossings admits an equitable tree-$k$-coloring for every integer $k\ge 8$; \n(c) any $d$-degenerate graph with maximum degree at most $\Delta$ admits an equitable tree-$k$-coloring for every integer $k\geq (\Delta+1)/2$ provided that $\Delta\geq 10d$. \nThis is a joint work with Yuping Gao\, Bi Li\, Yan Li\, and Bei Niu. URL:https://dimag.ibs.re.kr/event/2020-02-25/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200218T163000 DTEND;TZID=Asia/Seoul:20200218T173000 DTSTAMP:20260418T193000 CREATED:20200114T112946Z LAST-MODIFIED:20240705T202042Z UID:2039-1582043400-1582047000@dimag.ibs.re.kr SUMMARY:Dong Yeap Kang (강동엽)\, Fragile minor-monotone parameters under random edge perturbation DESCRIPTION:We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly\, after adding a few random edges\, its treewidth\, treedepth\, genus\, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases. We also discuss analogous results for randomly perturbed bipartite graphs as well as the size of a largest complete odd minor in randomly perturbed graphs. URL:https://dimag.ibs.re.kr/event/2020-02-18/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200128T163000 DTEND;TZID=Asia/Seoul:20200128T173000 DTSTAMP:20260418T193000 CREATED:20191216T045747Z LAST-MODIFIED:20240705T203007Z UID:1940-1580229000-1580232600@dimag.ibs.re.kr SUMMARY:Dillon Mayhew\, Courcelle's Theorem for hypergraphs DESCRIPTION:Courcelle’s Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time\, as long as the property can expressed in the monadic second-order logic of graphs\, and as long as the input is restricted to a class of graphs with bounded tree-width. There are several properties that are NP-complete in general\, but which can be expressed in monadic logic (3-colourability\, Hamiltonicity…)\, so Courcelle’s Theorem implies that these difficult properties can be tested in polynomial time when the structural complexity of the input is limited. \nMatroids can be considered as a special class of hypergraphs. Any finite set of vectors over a field leads to a matroid\, and such a matroid is said to be representable over that field. Hlineny produced a matroid analogue of Courcelle’s Theorem for input classes with bounded branch-width that are representable over a finite field. \nWe have now identified the structural properties of hypergraph classes that allow a proof of Hliněný’s Theorem to go through. This means that we are able to extend his theorem to several other natural classes of matroids. \nThis talk will contain an introduction to matroids\, monadic logic\, and tree-automata. \nThis is joint work with Daryl Funk\, Mike Newman\, and Geoff Whittle. URL:https://dimag.ibs.re.kr/event/2020-01-28/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200120T163000 DTEND;TZID=Asia/Seoul:20200120T173000 DTSTAMP:20260418T193000 CREATED:20200108T022511Z LAST-MODIFIED:20240705T202052Z UID:1997-1579537800-1579541400@dimag.ibs.re.kr SUMMARY:Adam Zsolt Wagner\, The largest projective cube-free subsets of $Z_{2^n}$ DESCRIPTION:What is the largest subset of $Z_{2^n}$ that doesn’t contain a projective d-cube? In the Boolean lattice\, Sperner’s\, Erdos’s\, Kleitman’s and Samotij’s theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $Z_2^n$ we work in $Z_{2^n}$\, analogous statements hold if one replaces the word k-chain by projective cube of dimension $2^{k-1}$. The largest d-cube-free subset of $Z_{2^n}$\, if d is not a power of two\, exhibits a much more interesting behaviour. \nThis is joint work with Jason Long. URL:https://dimag.ibs.re.kr/event/2020-01-20/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200115T163000 DTEND;TZID=Asia/Seoul:20200115T173000 DTSTAMP:20260418T193000 CREATED:20200107T040041Z LAST-MODIFIED:20240707T084237Z UID:1990-1579105800-1579109400@dimag.ibs.re.kr SUMMARY:Ben Lund\, Furstenberg sets over finite fields DESCRIPTION:An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture\, proved by Dvir in 2008. Dvir’s proof introduced the polynomial method to incidence geometry\, which led to the solution to many long-standing problems in the area.\nI will talk about a generalization of the Kakeya conjecture posed by Ellenberg\, Oberlin\, and Tao. A $(k\,m)$-Furstenberg set S in $\mathbb F_q^n$ has the property that\, parallel to every affine $k$-plane V\, there is a k-plane W such that $|W \cap S| > m$. Using sophisticated ideas from algebraic geometry\, Ellenberg and Erman showed that if S is a $(k\,m)$-Furstenberg set\, then $|S| > c m^{n/k}$\, for a constant c depending on n and k. In recent joint work with Manik Dhar and Zeev Dvir\, we give simpler proofs of stronger bounds. For example\, if $m>2^{n+7}q$\, then $|S|=(1-o(1))mq^{n-k}$\, which is tight up to the $o(1)$ term. URL:https://dimag.ibs.re.kr/event/2020-01-15/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20200114T163000 DTEND;TZID=Asia/Seoul:20200114T173000 DTSTAMP:20260418T193000 CREATED:20191225T230320Z LAST-MODIFIED:20240705T202054Z UID:1961-1579019400-1579023000@dimag.ibs.re.kr SUMMARY:Sanjeeb Dash\, Boolean decision rules via column generation DESCRIPTION:In many applications of machine learning\, interpretable or explainable models for binary classification\, such as decision trees or decision lists\, are preferred over potentially more accurate but less interpretable models such as random forests or support vector machines. In this talk\, we consider boolean decision rule sets (equivalent to boolean functions in disjunctive normal form) as interpretable models for binary classification. We define the complexity of a rule set to be the number of rules (clauses) plus the number of conditions (literals) across all clauses\, and assume that simpler or less complex models are more interpretable. We discuss an integer programming formulation for such models that trades off classification accuracy against rule simplicity\, and obtain high-quality classifiers of this type using column generation techniques. Compared to some recent alternatives\, our algorithm dominates the accuracy-simplicity trade-off in 8 out of 16 datasets\, and also produced the winning entry in the 2018 FICO explainable machine learning challenge. When compared to rule learning methods designed for accuracy\, our algorithm sometimes finds significantly simpler solutions that are no less accurate. URL:https://dimag.ibs.re.kr/event/2020-01-14/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191226T163000 DTEND;TZID=Asia/Seoul:20191226T173000 DTSTAMP:20260418T193000 CREATED:20191122T072031Z LAST-MODIFIED:20240705T203023Z UID:1875-1577377800-1577381400@dimag.ibs.re.kr SUMMARY:Jaiung Jun (전재웅)\, The Hall algebra of the category of matroids DESCRIPTION:To an abelian category A satisfying certain finiteness conditions\, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a non-additive setting\, Dyckerhoff and Kapranov introduced the notion of proto-exact categories\, as a non-additive generalization of an exact category\, which is shown to suffice for the construction of an associative Hall algebra. In this talk\, I will discuss the category of matroids in this perspective. URL:https://dimag.ibs.re.kr/event/2019-12-26/ LOCATION:Room 1401\, Bldg. E6-1\, KAIST CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191219T163000 DTEND;TZID=Asia/Seoul:20191219T173000 DTSTAMP:20260418T193000 CREATED:20191119T013103Z LAST-MODIFIED:20240707T084251Z UID:1801-1576773000-1576776600@dimag.ibs.re.kr SUMMARY:Attila Joó\, Base partition for finitary-cofinitary matroid families DESCRIPTION:Let ${\mathcal{M} = (M_i \colon i\in K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$. \nWe prove the following Cantor-Bernstein-type result: if $E$ can be covered by sets ${(B_i \colon i\in K)}$ which are bases in the corresponding matroids and there are also pairwise disjoint bases of the matroids $M_i$ then $E$ can be partitioned into bases with respect to $\mathcal{M}$. URL:https://dimag.ibs.re.kr/event/2019-12-19/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191212T163000 DTEND;TZID=Asia/Seoul:20191212T173000 DTSTAMP:20260418T193000 CREATED:20191122T071803Z LAST-MODIFIED:20240707T084259Z UID:1872-1576168200-1576171800@dimag.ibs.re.kr SUMMARY:Hong Liu\, A proof of Mader's conjecture on large clique subdivisions in $C_4$-free graphs DESCRIPTION:Given any integers $s\,t\geq 2$\, we show there exists some $c=c(s\,t)>0$ such that any $K_{s\,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ vertices. In particular\, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general\, the widely conjectured asymptotic behaviour of the extremal density of $K_{s\,t}$-free graphs suggests our result is tight up to the constant $c(s\,t)$. This is joint work with Richard Montgomery. URL:https://dimag.ibs.re.kr/event/2019-12-12/ LOCATION:Room 1401\, Bldg. E6-1\, KAIST CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191210T163000 DTEND;TZID=Asia/Seoul:20191210T173000 DTSTAMP:20260418T193000 CREATED:20191004T104834Z LAST-MODIFIED:20240707T084332Z UID:1488-1575995400-1575999000@dimag.ibs.re.kr SUMMARY:Jakub Gajarský\, First-order interpretations of bounded expansion classes DESCRIPTION:The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular\, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs\, we introduce classes of graphs with structurally bounded expansion\, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment\, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions\, replacing treedepth by its dense analogue called shrubdepth. URL:https://dimag.ibs.re.kr/event/2019-12-10/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191121T163000 DTEND;TZID=Asia/Seoul:20191121T173000 DTSTAMP:20260418T193000 CREATED:20191028T154322Z LAST-MODIFIED:20240707T084339Z UID:1641-1574353800-1574357400@dimag.ibs.re.kr SUMMARY:Frédéric Meunier\, Topological bounds for graph representations over any field DESCRIPTION:Haviv (European Journal of Combinatorics\, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb {R}$. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for the minrank parameter over $\mathbb {R}$ – an important graph invariant from coding theory – and show that this bound is actually valid for all fields as well. The notion of independent representation over a matroid is introduced and used in a general theorem having these results as corollaries. Related complexity results are also discussed.\nThis is joint work with Meysam Alishahi. URL:https://dimag.ibs.re.kr/event/2019-11-21/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191119T163000 DTEND;TZID=Asia/Seoul:20191119T173000 DTSTAMP:20260418T193000 CREATED:20190924T042207Z LAST-MODIFIED:20240707T084346Z UID:1430-1574181000-1574184600@dimag.ibs.re.kr SUMMARY:Ruth Luo\, Induced Turán problems for hypergraphs DESCRIPTION:Let $F$ be a graph. We say that a hypergraph $\mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $\mathcal H$ such that for all $xy \in E(F)$\, $f(xy) \cap V(F) = \{x\,y\}$. In this talk\, we show asymptotics for the maximum number of edges in $r$-uniform hypergraphs with no induced Berge $F$. In particular\, this function is strongly related to the generalized Turán function $ex(n\,K_r\, F)$\, i.e.\, the maximum number of cliques of size $r$ in $n$-vertex\, $F$-free graphs.  Joint work with Zoltan Füredi. URL:https://dimag.ibs.re.kr/event/2019-11-19/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191112T163000 DTEND;TZID=Asia/Seoul:20191112T173000 DTSTAMP:20260418T193000 CREATED:20190920T115103Z LAST-MODIFIED:20240705T204218Z UID:1402-1573576200-1573579800@dimag.ibs.re.kr SUMMARY:Tony Huynh\, Stable sets in graphs with bounded odd cycle packing number DESCRIPTION:It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann\, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$.  We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus\, there is a polynomial-time algorithm for each fixed $k$.  Moreover\, we obtain polynomial-size extended formulations for the respective stable set polytopes. \nTo this end\, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface. \nEventually\, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class\, which we prove to be efficiently solvable in our case. \nThis is joint work with Michele Conforti\, Samuel Fiorini\, Gwenaël Joret\, and Stefan Weltge. URL:https://dimag.ibs.re.kr/event/2019-11-12/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191108T120000 DTEND;TZID=Asia/Seoul:20191109T190000 DTSTAMP:20260418T193000 CREATED:20191004T060008Z LAST-MODIFIED:20240707T084357Z UID:1475-1573214400-1573326000@dimag.ibs.re.kr SUMMARY:Combinatorial and Discrete Optimization (2019 KSIAM Annual Meeting) DESCRIPTION:Special Session @ 2019 KSIAM Annual Meeting\nA special session on “Combinatorial and Discrete Optimization” at the 2019 KSIAM Annual Meeting is organized by Dabeen Lee. URL: https://www.ksiam.org/conference/84840fb6-87b0-4566-acc1-4802bde58fbd/welcome \nDate\nNov 8\, 2019 – Nov 9\, 2019 Address: 61-13 Odongdo-ro\, Sujeong-dong\, Yeosu-si\, Jeollanam-do (전남 여수시 오동도로 61-13) \nVenue\nVenezia Hotel & Resort Yeosu\, Yeosu\, Korea (여수 베네치아 호텔)  Address: 61-13 Odongdo-ro\, Sujeong-dong\, Yeosu-si\, Jeollanam-do (전남 여수시 오동도로 61-13) \nSpeakers\n\nHyung-Chan An (안형찬)\, Yonsei University\nTony Huynh\, Monash University\nDong Yeap Kang (강동엽)\, KAIST / IBS Discrete Mathematics Group\nDabeen Lee (이다빈)\, IBS Discrete Mathematics Group\nKangbok Lee (이강복)\, POSTECH\nSang-il Oum (엄상일)\, IBS Discrete Mathematics Group / KAIST\nKedong Yan\, Nanjing University of Science and Technology\nSe-Young Yun (윤세영)\, KAIST\n\nSchedules\n\nCombinatorial and Discrete Optimization I: November 8\, 2019 Friday\, 14:20 – 15:40.\n\nKangbok Lee\nKedong Yan\nDabeen Lee\nSe-young Yun\n\n\nCombinatorial and Discrete Optimization II: November 9\, 2019 Saturday\, 10:00 – 11:20.\n\nHyung Chan An\nDong Yeap Kang\nTony Huynh\nSang-il Oum\n\n\n\nAbstracts\nKangbok Lee (이강복)\, Bi-criteria scheduling\n\n\nThe bi-criteria scheduling problems that minimize the two most popular scheduling objectives\, namely the makespan and the total completion time\, are considered. Given a schedule\, makespan\, denoted as $C_\max$\, is the latest completion time of the jobs and the total completion time\, denoted as $\sum C_j$\, is the sum of the completion times of the jobs. These two objectives have received a lot of attention in the literature because of their practical implications. Scheduling problems are somehow difficult to solve even for single criterion. On the other hand\, when it comes to a bi-criteria problem\, a balanced solution coordinating both objectives is indeed essential. In this paper\, we consider bi-criteria scheduling problems on $m$ identical parallel machines where $m$ is 2\, 3 and an arbitrary number\, denoted as $P2 || (C_\max\,\sum􏰂 C_j)$\, $P3 || (C_\max\,􏰂\sum C_j)$ and $P || (C_\max\,􏰂C_j)$\, respectively. For each problem\, we explore its inapproximability and develop an approximation algorithm with analysis of its worst performance.\n\n\nKedong Yan\, Cliques for multi-term linearization of 0-1 multilinear program for boolean logical pattern generation\n\n\nLogical Analysis of Data (LAD) is a combinatorial optimization-based machine learning method. A key stage of LAD is pattern generation\, where useful knowledge in a training dataset of two types of\, say\, + and − data under analysis is discovered. LAD pattern generation can be cast as a 0-1 multilinear program (MP) with a single 0-1 multilinear constraint: $$(PG): \max\limits_{x\in\{0\,1\}^{2n}}f(x):=\sum_{i\in S^+}\Pi_{j\in J_i}(1-x_j)~~\text{subject to}~~g(x):=\sum_{i\in S^-}\Pi_{j\in J_i}(1-x_j)=0$$\n\n\nThe unconstrained maximization of $f$ (without $g$) is straightforward\, thus the main difficulty of globally maximizing $(PG)$ arises primarily from the presence of g and the interaction between $f$ and $g$. We dealt with the task of linearizing $g$. Namely\, we employed a graph theoretic analysis of data to discover sufficient conditions among neighboring data and also neighboring groups of data for ‘compactly linearizing’ $g$ in terms of a small number of stronger valid inequalities\, as compared to those that can be obtained via 0-1 linearization techniques from the literature. In an earlier work\, we analyzed + and − data (that is\, terms of $f$ and $g$ together) on a graph to develop a polyhedral overestimation scheme for $f$. Extending this line of research\, this paper proposes a new graph representation of monomials in f in conjunction with terms in $g$ to more aggressively aggregate a set of terms/data through each maximal clique in the graph into yielding a stronger valid inequality. This is achieved by means of a new notion of ‘neighbors’ that allows us to join two data that are more than 1-Hamming distance away from each other by an edge in the graph. We show that new inequalities generalize and subsume those from the earlier paper. Furthermore\, with using six benchmark data mining datasets\, we demonstrate that new inequalities are superior to their predecessors in terms of a more efficient global maximization of $(PG)$; that is\, for a more efficient analysis and classification of real-life datasets.\n\n\nDabeen Lee (이다빈)\, Joint Chance-constrained programs and the intersection of mixing sets through a submodularity lens\nThe intersection of mixing sets with common binary variables arise when modeling joint linear chance-constrained programs with random right-hand sides and finite sample space. In this talk\, we first establish a strong and previously unrecognized connection of mixing sets to submodularity. This viewpoint enables us to unify and extend existing results on polyhedral structures of mixing sets. Then we study the intersection of mixing sets with common binary variables and also linking constraint lower bounding a linear function of the continuous variables. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull. \nSe-Young Yun (윤세영)\, Optimal sampling and clustering algorithms in the stochastic block model\n\n\nThis paper investigates the design of joint adaptive sampling and clustering algorithms in the Stochastic Block Model (SBM). To extract hidden clusters from the data\, such algorithms sample edges sequentially in an adaptive manner\, and after gathering edge samples\, return cluster estimates. We derive information-theoretical upper bounds on the cluster recovery rate. These bounds reveal the optimal sequential edge sampling strategy\, and interestingly\, the latter does not depend on the sampling budget\, but only the parameters of the SBM. We devise a joint sampling and clustering algorithm matching the recovery rate upper bounds. The algorithm initially uses a fraction of the sampling budget to estimate the SBM parameters\, and to learn the optimal sampling strategy. This strategy then guides the remaining sampling process\, which confers the optimality of the algorithm.\n\n\nHyung-Chan An (안형찬)\, Constant-factor approximation algorithms for parity-constrained facility location problems\n\n\nFacility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest\, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather disturbing when we consider the central role of parity in the field of combinatorics. In this paper\, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients\, the opening cost of each facility\, and the parity requirement—$\mathsf{odd}$\, $\mathsf{even}$\, or $\mathsf{unconstrained}$—of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances\, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap\, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a $T$-join on an auxiliary graph constructed by the algorithm. This graph does not satisfy the triangle inequality\, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse $T$-join. Finally\, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. At the end of this paper\, we also present the first constant-factor approximation algorithm for the parity-constrained $k$-center problem\, the bottleneck optimization variant.\n\n\nDong Yeap Kang (강동엽)\, On minimal highly connected spanning subgraphs in dense digraphs\nIn 1985\, Mader showed that every $n(\geq4k+3)$-vertex strongly $k$-connected digraph contains a spanning strongly $k$-connected subgraph with at most $2kn-2k^2$ edges\, and the only extremal digraph is a complete bipartite digraph $DK_{k\,n−k}$. Nevertheless\, since the extremal graph is sparse\, Bang-Jensen asked whether there exists g(k) such that every strongly $k$-connected $n$-vertex tournament contains a spanning strongly $k$-connected subgraph with $kn + g(k)$ edges\, which is an “almost $k$-regular” subgraph. \n\n\nRecently\, the question of Bang-Jensen was answered in the affirmative with $g(k) = O(k^2\log k)$\, which is best possible up to logarithmic factor. In this talk\, we discuss how to find minimal highly connected spanning subgraphs in dense digraphs as well as tournaments. In particular\, we show that every highly connected dense digraph contains a spanning highly connected subgraph that is almost $k$-regular\, which yields $g(k) = O(k^2)$ that is best possible for tournaments.\n\n\nTony Huynh\, Stable sets in graphs with bounded odd cycle packing number\n\n\nIt is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann\, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$. We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus\, there is a polynomial-time algorithm for each fixed $k$. Moreover\, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end\, we show that 2-sided odd cycles satisfy the Erdos-Posa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdos-Posa property in graphs embedded in a fixed orientable surface Eventually\, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class\, which we prove to be efficiently solvable in our case.\n\n\nSang-il Oum\, Rank-width: Algorithmic and structural results\n\n\nRank-width is a width parameter of graphs describing whether it is possible to decompose a graph into a tree-like structure by ‘simple’ cuts. This talk aims to survey known algorithmic and structural results on rank-width of graphs. This talk is based on a survey paper with further remarks on the recent developments. URL:https://dimag.ibs.re.kr/event/2019-11-08/ LOCATION:Venezia Hotel & Resort Yeosu\, Yeosu\, Korea (여수 베네치아 호텔)  CATEGORIES:Workshops and Conferences END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191105T163000 DTEND;TZID=Asia/Seoul:20191105T173000 DTSTAMP:20260418T193000 CREATED:20191027T113022Z LAST-MODIFIED:20240707T085941Z UID:1636-1572971400-1572975000@dimag.ibs.re.kr SUMMARY:Sun Kim (김선)\, Two identities in Ramanujan’s Lost Notebook with Bessel function series DESCRIPTION:On page 335 in his lost notebook\, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities under three different interpretations for the double series\, and showed that they are intimately connected with the classical circle and divisor problems in number theory. Furthermore\, we established many analogues and generalizations of them. This is joint work with Bruce C. Berndt and Alexandru Zaharescu. URL:https://dimag.ibs.re.kr/event/2019-11-05/ LOCATION:Room 1401\, Bldg. E6-1\, KAIST CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;VALUE=DATE:20191031 DTEND;VALUE=DATE:20191105 DTSTAMP:20260418T193000 CREATED:20190514T145906Z LAST-MODIFIED:20240707T090002Z UID:863-1572480000-1572911999@dimag.ibs.re.kr SUMMARY:The 2nd East Asia Workshop on Extremal and Structural Graph Theory DESCRIPTION:The 2nd East Asia Workshop on Extremal and Structural Graph Theory is a workshop to bring active researchers in the field of extremal and structural graph theory\, especially in the East Asia such as China\, Japan\, and Korea. \nDate\nOct 31\, 2019 (Arrival Day) – Nov 4\, 2019 (Departure Day) \nVenue and Date\n1st floor  Diamond Hall \nUTOP UBLESS Hotel\, Jeju\, Korea (유탑유블레스호텔제주) Address: 502 Johamhaean-ro\, Jocheon-eup\, Jeju\, Korea (제주특별자치도 제주시 조천읍 조함해안로 502) We plan to support the accommodation for invited participants. \nThe UTOP UBLESS Hotel is located at the beautiful Hamdeok Beach of the Jeju Island.\nInvited Speakers\n\nPing Hu\, Sun Yat-Sen University\, China\nJaehoon Kim\, KAIST\, Korea\nO-joung Kwon\, Incheon National University and IBS Discrete Mathematics Group\, Korea\nJoonkyung Lee\, University of Hamburg\, Germany\nBinlong Li\, Northwestern Polytechnical University\, China\nHongliang Lu\, Xi’an Jiaotong University\, China\nAbhishek Methuku\, IBS Discrete Mathematics Group\, Korea\nAtsuhiro Nakamoto\, Yokohama National University\, Japan\nKenta Noguchi\, Tokyo University of Science\, Japan\nKenta Ozeki\, Yokohama National University\, Japan\nBoram Park\, Ajou University\, Korea\nYuejian Peng\, Hunan University\, China\nZi-Xia Song\, University of Central Florida\, U.S.A.\nTomáš Kaiser\, University of West Bohemia\, Czech Republic.\nMaho Yokota\, Tokyo University of Science\, Japan.\nXuding Zhu\, Zhejiang Normal University\, China\n\nMore speakers to be announced as soon as confirmed. Last update: September 10. \nProgram\nDay 0 (Oct. 31 Thursday)\n\n4:00PM-6:00Pm Registration and Discussions\n\nDay 1 (Nov. 1 Friday)\n\n9:00AM-9:20AM Opening address\n9:20AM-9:50AM Jaehoon Kim\, A quantitative result on the polynomial Schur’s theorem\n10:00AM-10:30AM Yuejian Peng\, Lagrangian densities of hypergraphs\n10:30AM-10:50AM Coffee Break\n10:50AM-11:20AM Atsuhiro Nakamoto\, Geometric quadrangulations on the plane\n11:30AM-12:00PM Ping Hu\, The inducibility of oriented stars\n2:00PM-2:30PM Boram Park\, 5-star coloring of some sparse graphs\n2:40PM-3:10PM Kenta Ozeki\, An orientation of graphs with out-degree constraint\n3:10PM-3:30PM Coffee Break\n3:30PM-5:30PM Problem session\n\nDay 2 (Nov. 2 Saturday)\n\n9:20AM-9:50AM Xuding Zhu\, List colouring and Alon-Tarsi number of planar graphs\n10:00AM-10:30AM O-joung Kwon\, A survey of recent progress on Erdős-Pósa type problems\n10:30AM-10:50AM Coffee Break\n10:50AM-11:20AM Kenta Noguchi\, Extension of a quadrangulation to triangulations\, and spanning quadrangulations of a triangulation\n11:30AM-12:00PM Zi-Xia Song\, Ramsey numbers of cycles under Gallai colorings\n2:00PM-2:30PM Binlong Li\, Cycles through all finite vertex sets in infinite graphs\n2:40PM-3:10PM Tomáš Kaiser\, Hamilton cycles in tough chordal graphs\n3:20PM-3:50PM Abhishek Methuku\, On a hypergraph bipartite Turán problem\n3:50PM-4:10PM Coffee Break\n4:10PM-6:00PM Problem session and discussion\n\nDay 3 (Nov. 3 Sunday)\n\n9:20AM-9:50AM Joonkyung Lee\, Odd cycles in subgraphs of sparse pseudorandom graphs\n10:00AM-10:30AM Maho Yokota\, Connectivity\, toughness and forbidden subgraph conditions\n10:30AM-10:50AM Coffee Break\n10:50AM-11:20AM Hongliang Lu\, On minimum degree thresholds for fractional perfect matchings and near perfect matchings in hypergraphs\n11:30AM-12:00PM Contributed Talks\n2:00PM-6:00PM Problem session / Discussions / Hike\n\nDay 4 (Nov. 4 Monday)\n\n9:00AM-10:30AM Discussions\n\nHistory\n\n1st East Asia Workshop on Extremal and Structural Graph Theory\n\nNov. 30-Dec. 2\, 2018.\nHeld at and sponsored by Shanghai Center for Mathematical Sciences in China\, under the name “2018 SCMS Workshop on Extremal and Structural Graph Theory”.\nOrganizers: Ping Hu\, Seog-Jin Kim\, Kenta Ozeki\, Hehui Wu.\n\n\n\nOrganizers\n\nSeog-Jin Kim\, Konkuk University\, Korea.\nSang-il Oum\, IBS Discrete Mathematics Group\, Korea and KAIST\, Korea.\nKenta Ozeki\, Yokohama National University\, Japan.\nHehui Wu\, Shanghai Center for Mathematical Sciences\, China.\n\nSponsor\nIBS Discrete Mathematics Group\, Korea. \nAbstracts\nPing Hu\, The inducibility of oriented stars\nLet $S_{k\,\ell}$ denote the oriented star with $k+\ell$ edges\, where the center has out-degree $k$ and in-degree $\ell$. For all $k\,\ell$ with $k+\ell$ large\, we determine n-vertex digraphs $G$ which maximize the number of induced $S_{k\,\ell}$. This extends a result of Huang (2014) for all $S_{k\,0}$\, and a result of Hladký\, Král’ and Norin for $S_{1\,1}$. Joint work with Jie Ma\, Sergey Norin\, and Hehui Wu. \nJaehoon Kim\, A quantitative result on the polynomial Schur’s theorem\nRecently\, Liu\, Pach\, and Sándor [arXiv:1811.05200] proved that for a polynomial $p(z)\in \mathbb{Z}[z]$\, any $2$-coloring of $\mathbb{N}$ has infinitely many monochromatic solutions of the equatoin $x+y=p(z)$ if and only if $2\mid p(0)p(1)$. We improve their result in a quantitative way. We prove that if $p(z)$ has degree $d \neq 3$ and $2\mid p(0)p(1)$\, then any $2$-coloring of $[n]=\{1\,\dots\, n\}$ contains at least $n^{2/d^2 -o(1)}$ monochromatic solutions. This is sharp as there exists a coloring of $[n]$ with $O(n^{2/d^2})$ monochromatic solutions. Our method also gives some bound for the case when $d=3$\, but it is not sharp. We also prove that if $2\mid p(0)p(1)$\, then the interval $[n\, p(\lceil \frac{p(n)}{2} \rceil)]$ contains at least one monochromatic solution of $x+y=p(z)$. This is sharp up to multiplicative constant at most two as one can color $[n\, \frac{1}{2}p(\lceil \frac{p(n)}{2} \rceil)-1]$ with no monochromatic solutions. Joint work with Hong Liu and Péter Pál Pach. \nO-joung Kwon\, A survey of recent progress on Erdős-Pósa type problems\nA graph family $\mathcal{F}$ is said to have the Erdős-Pósa property if there is a function $f$ such that for every graph $G$ and an integer $k$\, either $G$ contains $k$ disjoint copies of graphs in $\mathcal{F}$\, or it has a vertex set of size at most $f(k)$ that hits all copies of graphs in $\mathcal{F}$. This name is motivated from the Erdős-Pósa theorem (1965) which says that the set of cycles has the Erdős-Pósa property. In this talk\, we survey on progress of finding various graph families that have the Erdős-Pósa property\, and would like to pose interesting open problems. \nJoonkyung Lee\, Odd cycles in subgraphs of sparse pseudorandom graphs\n  We answer two extremal questions about odd cycles that naturally arise in the study of sparse pseudorandom graphs. Let $\Gamma$ be an $(n\,d\,\lambda)$-graph\, i.e.\, $n$-vertex\, $d$-regular graphs with all nontrivial eigenvalues in the interval $[-\lambda\,\lambda]$. Krivelevich\, Lee\, and Sudakov conjectured that\, whenever $\lambda^{2k-1}\ll d^{2k}/n$\, every subgraph $G$ of $\Gamma$ with $(1/2+o(1))e(\Gamma)$ edges contains an odd cycle $C_{2k+1}$. Aigner-Horev\, Hàn\, and the third author proved a weaker statment by allowing an extra polylogarithmic factor in the assumption $\lambda^{2k-1}\ll d^{2k}/n$\, but we completely remove it and hence settle the conjecture. This also generalises Sudakov\, Szabo\, and Vu’s Turán-type theorem for triangles. Secondly\, we obtain a Ramsey multiplicity result for odd cycles. Namely\, in the same range of parameters\, we prove that every 2-edge-colouring of $\Gamma$ contains at least $(1-o(1))2^{-2k}d^{2k+1}$ monochromatic copies of $C_{2k+1}$. Both results are asymptotically best possible by Alon and Kahale’s construction of $C_{2k+1}$-free pseudorandom graphs. Joint work with Sören Berger\, Mathias Schacht. \nBinlong Li\, Cycles through all finite vertex sets in infinite graphs\nA closed curve in the Freudenthal compactification $|G|$ of an infinite locally finite graph $G$ is called a Hamiltonian curve if it meets every vertex of $G$ exactly once (and hence it meets every end at least once). We prove that $|G|$ has a Hamiltonian curve if and only if every finite vertex set of $G$ is contained in a cycle of $G$. We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example\, Barnette’s conjecture (that every finite planar cubic 3-connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3-connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3-connected bipartite graph with a nowhere-zero 3-flow (with no restriction on the number of ends) has a Hamiltonian curve. However\, there are 7-ended planar cubic 3-connected bipartite graphs that do not have a Hamiltonian curve. Joint work  with André Kündgen and Carsten Thomassen. \nHongliang Lu\, On minimum degree thresholds for fractional perfect matchings and near perfect matchings in hypergraphs\nWe study degree conditions for the existence of large matchings and fractional perfect matching in uniform hypergraphs. Firstly\, we give some sufficient conditions for $k$-graphs to have fractional perfect matching in terms of minimum degree. Secondly\, we prove that for integers $k\,l\,n$ with $k\ge 3$\, $k/2{n-l\choose k-l}-{(n-l)-(\lceil n/k \rceil-2)\choose 2}$\, then $H$ has a matching covering all but a constant number of vertices.  When $l=k-2$ and $k\ge 5$\, such a matching is near perfect and our bound on $\delta_l(H)$ is best possible. When $k=3$\, with the help of an absorbing lemma of Hàn\, Person\, and Schacht\, our proof also implies that $H$ has a perfect matching\, a result proved by Kühn\, Osthus\, and Treglown and\, independently\, of Kahn. Joint work with Xingxing Yu and Xiaofan Yuan. \nAbhishek Methuku\, On a hypergraph bipartite Turán problem\nLet $t$ be an integer such that $t\geq 2$. Let $K_{2\,t}^{(3)}$ denote the triple system consisting of the $2t$ triples $\{a\,x_i\,y_i\}$\, $\{b\,x_i\,y_i\}$ for $ 1 \le i \le t$\, where the elements $a\, b\, x_1\, x_2\, \ldots\, x_t\,$ $y_1\, y_2\, \ldots\, y_t$ are all distinct. Let $ex(n\,K_{2\,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2\,t}^{(3)}$. This function was studied by Mubayi and Verstraëte\, where the special case $t=2$ was a problem of Erdős that was studied by various authors. Mubayi and Verstraëte proved that $ex(n\,K_{2\,t}^{(3)})1$. If $G$ is $k$-connected and $K_{1\,\lfloor r \rfloor +1}$-free\, then $\textrm{tough}(G)\geq k/r$. It means high connectivity implies high toughness under the star-free condition. Our purpose is to prove assertions which can be regarded as a converse of this statement; that is say\, we ask what we can say about $\mathcal H$ if high connectivity implies high toughness in the family of $\mathcal H$-free graphs. About this question\, Ota and Sueiro (2013) proved the following theorem. Theorem 1 (Ota and Sueiro). Let $H$ be a connected graph and $\tau$ be a real number with $0<\tau\leq 1/2$. Almost all $H$-free connected graphs $G$ satisfy $\textrm{tough}(G)\geq \tau$ if and only if $K_{1\,\lfloor 1/\tau \rfloor +1}$ contains $H$ as an induced subgraph. Our main result is high connectivity versions of this theorem. We proved the following theorems. Theorem 2. Let $H$ be a connected graph\, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. Almost all $H$-free $k$-connected graphs $G$ satisfy $\textrm{tough}(G)\geq k/r$ if and only if $K_{1\,\lfloor 1/\tau \rfloor +1}$ contains $H$ as an induced subgraph. Theorem 3. Let $\mathcal H=\{H_1\,H_2\}$ be a family of connected graphs\,  $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. Almost all $\mathcal H$-free $k$-connected graphs $G$ satisfy $\textrm{tough}(G)\geq k/r$ if and only if $K_{1\,\lfloor 1/\tau \rfloor +1}$ contains one of $H$ as an induced subgraph. \nXuding Zhu\, List colouring and Alon-Tarsi number of planar graphs\nA $d$-defective colouring of a graph $G$ is a colouring of the vertices of $G$ such that each vertex $v$ has at most $d$ neighbours coloured the same colour as $v$. We say $G$ is $d$-defective $k$-choosable if for any $k$-assignment $L$ of $G$\, there exists a $d$-defective $L$-colouring\, i.e.\, a $d$-defective colouring $f$ with $f(v) \in L(v)$ for each vertex $v$. It was proved by Eaton and Hull (1999) and Škrekovski (1999) that every planar graph is $2$-defective $3$-choosable\, and proved by Cushing and Kierstead (2010) that every planar graph is $1$-defective $4$-choosable. In other words\, for a planar graph $G$\, for any $3$-assigment $L$ of $G$\, there is a subgraph $H$ with $\Delta(H) \le 2$ such that $G-E(H)$ is $L$-colourable; and for any $4$-list assignment $L$ of $G$\, there is a subgraph $H$ with $\Delta(H) \le 1$ such that $G-E(H)$ is $L$-colourable. An interesting problem is whether there is a subgraph $H$ with $\Delta(H) \le 2$ such that $G-E(H)$ is $3$-choosable\, and whether there is a subgraph $H$ with $\Delta(H) \le 1$ such that $G-E(H)$ is $4$-choosable. It turns out that the answer to the first question is negative and the answer to the second question is positive. Kim\, Kim and I proved that there is a planar graph $G$ such that for any subgraph $H$ with $\Delta(H)=3$\, $G-E(H)$ is not $3$-choosable. Grytczuk and I proved that every planar graph $G$ has a matching $M$ such that $G-M$ has Alon-Tarsi number at most $4$\, and hence is $4$-choosable. The late result also implies that every planar graph is $1$-defective $4$-paintable. For a subset $X$ of $V(G)$\, let $f_X$ be the function defined as $f_X(v)=4$ for $v \in X$ and $f_X(v)=5$ for $v \in V(G)-X$. Our proof also shows that every planar graph $G$ has a subset $X$ of size $|X| \ge |V(G)|/2$ such that $G$ is $f_X$-AT\, which implies that $G$ is $f_X$-choosable and also $f_X$-paintable. In this talk\, we shall present the proof and discuss possible strengthening of this result. URL:https://dimag.ibs.re.kr/event/2019-east-asia-graph-theory/ LOCATION:UTOP UBLESS Hotel\, Jeju\, Korea (유탑유블레스호텔제주) CATEGORIES:Workshops and Conferences ORGANIZER;CN="Seog-Jin Kim (%EA%B9%80%EC%84%9D%EC%A7%84)":MAILTO:skim12@konkuk.ac.kr END:VEVENT END:VCALENDAR