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:20170101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20190813
DTEND;VALUE=DATE:20190816
DTSTAMP:20260419T164220
CREATED:20190410T011602Z
LAST-MODIFIED:20240707T090140Z
UID:748-1565654400-1565913599@dimag.ibs.re.kr
SUMMARY:2019 Combinatorics Workshop
DESCRIPTION:The annual conference on Combinatorics Workshop (조합론 학술대회) began in 2004 by the Yonsei University BK21 Research Group. This year it will take place in Songdo\, Incheon\, August 13-15\, 2019. \n\n\n\n\n\n\n\n\n\nDue to the capacity (50 persons) of the place\, we are able to limit your registration. In principle\, registration is on a first-come\, first-served basis. \n\n\n\n\n\n\n\n\n\n\nTitle 2019 Combinatorics Workshop (2019 조합론 학술대회)\nDate August 13-15 (Tue-Thu)\, 2019\nVenue Hotel Skypark\, Songdo\, Incheon\nWeb https://cw2019.combinatorics.kr\n\nWe are going to \n\ngive six 50-minute talks and ten 25-minute talks in Korean.\ndistribute the program and abstracts of CW2019.\nprovide for the accommodations for all participants.\nprovide for six meals (two breakfasts\, two luncheons\, one dinner\, and one banquet) for all participants.\n\nPlenary Speaker\n\nMihyun Kang\, Graz University of Technology\n\nKeynote Speakers\n\nJaehoon Kim\, KAIST\nSeung Jin Lee\, Seoul National University\nMeesue Yoo\, Dankook University\n\nInvited Speakers\n\nEun-Kyung Cho\, Hankuk University of Foreign Studies\nSoogang Eoh\, Seoul National University\nJiSun Huh\, Sungkyunkwan University\nJihyeug Jang\, Sungkyunkwan University\nDong Yeap Kang\, KAIST and IBS Discrete Mathematics Group\nMin Jeong Kang\, Incheon National University\nDabeen Lee\, IBS Discrete Mathematics Group\nKang-Ju Lee\, Seoul National University\nMyeonghwan Lee\, Incheon National University\nJihye Park\, Yeungnam University\nSun-mi Yun\, Sungkyunkwan University\n\nOrganizing Committee\n\nO-joung Kwon\, Incheon National University and IBS Discrete Mathematics Group\nSuil O\, SUNY Korea\nSang-il Oum\, IBS Discrete Mathematics Group and KAIST\nHeesung Shin\, Inha University\n\nAdvisory Committee\n\nCommittee of Discrete Mathematics\, The Korean Mathematical Society (Chair: Seog-Jin Kim\, Konkuk University)\n\nSponsors\n\nIBS Discrete Mathematics Group\nNRF (National Research Foundation of Korea)
URL:https://dimag.ibs.re.kr/event/2019-combinatorics-workshop/
LOCATION:Hotel Skypark\, Songdo\, Incheon\, Korea (송도 스카이파크호텔)
CATEGORIES:Workshops and Conferences
ATTACH;FMTTYPE=image/png:https://dimag.ibs.re.kr/cms/wp-content/uploads/2019/06/unnamed.png
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190812T110000
DTEND;TZID=Asia/Seoul:20190812T200000
DTSTAMP:20260419T164220
CREATED:20190730T073856Z
LAST-MODIFIED:20240707T090147Z
UID:1201-1565607600-1565640000@dimag.ibs.re.kr
SUMMARY:2019-2 IBS One-Day Conference on Extremal Graph Theory
DESCRIPTION:Invited Speakers\n\nJaehoon Kim (김재훈)\, KAIST\nHong Liu (刘鸿)\, University of Warwick\nAbhishek Methuku\, IBS Discrete Mathematics Group\nPéter Pál Pach\, Budapest University of Technology and Economics\n\nSchedule\nAugust 12\, Monday\n11:00am-12:00pm Jaehoon Kim (김재훈): Tree decompositions of graphs without large bipartite holes \n12:00pm-1:30pm Lunch \n1:30pm-2:30pm Abhishek Methuku: Bipartite Turán problems for ordered graphs \n3:00pm-4:00pm Péter Pál Pach: On some applications of graph theory to number theoretic problems \n4:30pm-5:30pm Hong Liu: Recent advance in Ramsey-Turán theory \n6:00pm-8:00pm Banquet \nAbstract\nJaehoon Kim (김재훈)\, Tree decompositions of graphs without large bipartite holes\nA recent result of Condon\, Kim\, Kühn and Osthus implies that for any $r\geq (\frac{1}{2}+o(1))n$\, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this talk\, we prove that a similar result holds for an almost $\alpha n$-regular graph $G$ with any $\alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. This is joint work with Younjin Kim and Hong Liu. \nAbhishek Methuku\,  Bipartite Turán problems for ordered graphs\nA zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete rows and columns of $M$\, and turn 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$\, denoted by $ex(n\,A)$\, is the maximum number of $1$-entries in an $n\times n$ sized matrix $M$ that does not contain $A$. \nA matrix $A$ is column-$t$-partite (or row-$t$-partite)\, if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite\, then $\operatorname{ex}(n\,A)<n^{2-\frac{1}{t}+\frac{1}{2t^{2}}+o(1)}$\, and if $A$ is both column- and row-$t$-partite\, then $\operatorname{ex}(n\,A)<n^{2-\frac{1}{t}+o(1)}$\, and this bound is close to being optimal. Our proof introduces a new density-increment-type argument which is combined with the celebrated dependent random choice method. \nResults about the extremal numbers of zero-one matrices translate into results about the Turán numbers of bipartite ordered graphs. In particular\, a zero-one matrix with at most $t$ 1-entries in each row corresponds to an ordered graph with maximum degree $t$ in one of its vertex classes. The aim of this talk is to establish general results about the extremal numbers of ordered graphs. Our results are partially motivated by a well known result of Füredi (1991) and Alon\, Krivelevich\, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes\, then $\operatorname{ex}(n\,H)=O(n^{2-\frac{1}{t}})$. This is joint work with Tomon. \nPéter Pál Pach\, On some applications of graph theory to number theoretic problems\nHow large can a set of integers be\, if the equation $a_1a_2\dots a_h=b_1b_2\dots b_h$ has no solution consisting of distinct elements of this set? How large can a set of integers be\, if none of them divides the product of $h$ others? How small can a multiplicative basis for $\{1\, 2\, \dots\, n\}$ be? The first question is about a generalization of the multiplicative Sidon sets\, the second one is of the primitive sets\, while the third one is the multiplicative version of the well-studied analogue problem for additive bases. \nIn answering the above mentioned questions graph theory plays an important role and in most of our results not only the asymptotics are found\, but very tight bounds are obtained for the error terms\, as well. We will also discuss the counting version of these questions. \nHong Liu\, Recent advance in Ramsey-Turán theory\nWe will talk about Ramsey-Turán theory and some recent development. More specifically\, we will talk about graphs with $\alpha_r(G)=o(n)$\, where $\alpha_r(G)$ is the largest size subset with no $K_r$. Two major open problems in this area from the 80s ask: (1) whether Bollobas-Erdos graph can be generalised to densities other than $1/2$; (2) whether the asymptotic extremal structure for $\alpha_r(G)$ resembles that of $\alpha_2(G)$. We settle the first conjecture by constructing Bollobas-Erdos type graph with density $a$ for arbitrary rational number $a\le 1/2$; and refute the second conjecture by witnessing asymptotic extremal structures that are drastically different from the $\alpha_2(G)$ problem via a ”Mobius product” construction. \nJoint work with Christian Reiher\, Maryam Sharifzadeh\, and Katherine Staden.
URL:https://dimag.ibs.re.kr/event/2019-08-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20190721
DTEND;VALUE=DATE:20190811
DTSTAMP:20260419T164220
CREATED:20190312T042509Z
LAST-MODIFIED:20240707T090155Z
UID:680-1563667200-1565481599@dimag.ibs.re.kr
SUMMARY:2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures
DESCRIPTION:Schedule\nJuly 22 Monday\n10:00-11:00 Introduction\, 11:00-12:00 Open Problems \nJuly 23 Tuesday\n10:00-10:30 Stefan Kratsch\, Humboldt-Universität zu Berlin\, Germany\nElimination Distances\, Blocking Sets\, and Kernels for Vertex Cover \n10:45-11:15 Benjamin Bergougnoux\, University Clermont Auvergne\, France\nMore applications of the d-neighbor equivalence \n11:30-12:00 Yixin Cao\, Hong Kong Polytechnic University\, China\nEnumerating Maximal Induced Subgraphs \n13:30-14:30 Open Problems \nJuly 24 Wednesday\nWe will go to KAIST for June Huh‘s two talks 15:00-16:00\, 16:30-17:30. A IBS shuttle bus @14:30 from the lobby. \nJuly 25 Thursday\n10:00-11:00 Nick Brettell\, Durham University\, UK\nRecent work on characterising matroids representable over finite fields \n11:30-12:00 Mamadou M. Kanté\, University Clermont Auvergne\, France\nOn recognising k-letter graphs \nJuly 26 Friday\n10:00-11:00 O-joung Kwon (권오정)\, Incheon National University\, Korea\nThe grid theorem for vertex-minors \n11:00-12:00 Progress Report \nJuly 27 Saturday\n8:30 Excursion to Damyang (departure from the accommodation) \nJuly 29 Monday\n10:00-11:00 Archontia Giannopoulou\, National and Kapodistrian University of Athens\, Greece\nThe directed flat wall theorem \n11:30-12:00 Eunjung Kim (김은정)\, LAMSADE-CNRS\, France\nSubcubic even-hole-free graphs have a constant treewidth \nJuly 30 Tuesday\n10:00-11:00 Pierre Aboulker\, ENS Ulm\, France\nGeneralizations of the geometric de Bruijn Erdős Theorem \n11:30-12:00 Michael Dobbins\, Binghamton University\, USA\nBarycenters of points in polytope skeleta \nJuly 31 Wednesday\n10:00-11:00 Magnus Wahlström\, Royal Holloway\, University of London\, UK\nFPT-algorithms via LP-relaxations \n11:30-12:00 Édouard Bonnet\, ENS Lyon\, France\nThe FPT/W[1]-hard dichotomy of Max Independent Set in H-free graphs \nAugust 1 Thursday\n10:00-11:00 Euiwoong Lee (이의웅)\, NYU\, USA\n Losing treewidth by separating subsets \n11:30-12:00 Sang-il Oum (엄상일)\, IBS Discrete Mathematics Group and KAIST\, Korea\nBranch-depth: Generalizing tree-depth of graphs \nAugust 2 Friday\n10:00-11:00 Dabeen Lee (이다빈)\, IBS Discrete Mathematics Group\, Korea\nt-perfect graphs and the stable set problem \n11:00-12:00 Progress Report \nAugust 5-9: Free Discussions / Research Collaborations / Progress Report\nTea time: Every weekday 3:30pm \nAbstracts\nJuly 23 Tuesday\nStefan Kratsch\, Elimination Distances\, Blocking Sets\, and Kernels for Vertex Cover\nThe Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity\, i.e.\, the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes\, we seek to unify and generalize them using so-called blocking sets\, which have played implicit and explicit roles in many results. We show that in the most-studied setting\, parameterized by the size of a deletion set to a specified graph class ${\cal C}$\, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions\, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class ${\cal C}$\, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes ${\cal C}$\, including the class ${\cal C}_{LP}$ of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to\, e.g.\, forest\, bipartite\, or ${\cal C}_{LP}$ graphs. \nBenjamin Bergougnoux\, More applications of the d-neighbor equivalence\nIn this talk\, I will present a framework which gives efficient algorithms for several connectivity problems such as Connected Dominating Set\, Node Weighted Steiner Tree\, Maximum Induced Tree\, Longest Induced Path\, and Feedback Vertex Set. For all these problems\, we obtain efficient algorithms parameterized respectively by tree-width\, clique-width\, Q-rank-width\, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the running time of the best algorithms for Vertex Cover and Dominating Set. Our framework is based on the d-neighbor equivalence defined in [Bui-Xuan\, Telle and Vatshelle\, TCS 2013]. The results we obtain highlight the importance and the generalizing power of this equivalence relation on width measures. We also prove that this equivalence relation could be useful for Max Cut: a W[1]-hard problem parameterized by clique-width. \nPaper available on HAL : https://hal.archives-ouvertes.fr/hal-01799573 \nYixin Cao\, Enumerating Maximal Induced Subgraphs\nWe study efficient algorithms for the maximal induced subgraphs problem: Given a graph on $n$ vertices\, enumerate all its maximal induced subgraphs that belong to a particular hereditary graph class. While its optimization version\, known as the vertex deletion problem in literature\, has been intensively studied\, algorithms for the enumeration version exist only for few simple graph classes\, e.g.\, independent sets and cliques. Enumeration algorithms are mainly categorized in three complexity classes\, polynomial total time (polynomial on $n$ and the total number of solutions)\, incremental polynomial time (for all $s$\, the time to output the first $s$ solutions is polynomial on $n$ and $s$)\, and polynomial delay (for all $s$\, the time to output the first $s$ solutions is polynomial on $n$ and linear on $s$). We first show that the maximal induced subgraphs problem can be solved in polynomial total time if and only if it can be solved in incremental polynomial time. We then propose general approaches to develop polynomial-delay algorithms and incremental-polynomial-time algorithms for the problem. They enable us to develop simple algorithms to solve the problem with polynomial delay for a large number of graph classes\, and in incremental polynomial time for interval graphs\, chordal graphs as well as two of its well-studied subclasses\, and all graph classes with finite forbidden induced subgraphs. \nJuly 25 Thursday\nNick Brettell\, Recent work on characterising matroids representable over finite fields\nCharacterising when a matroid is representable over a certain field or set of fields is one of the oldest problems in matroid theory\, dating back to Whitney’s 1935 paper. In this talk\, I will discuss some of the more recent work in this area\, with a focus on work I have been involved with towards characterising matroids representable over all fields of size at least four. \nMamadou M. Kanté\, On recognising k-letter graphs\n$k$-letter graphs are a subclass of graphs of linear clique-width $k$\, but are well-quasi-ordered by the induced subgraph ordering. I present a simple FPT algorithm for recognising $k$-letter graphs and also an upper bound on the size of minimal obstructions. The characterisation is based on a simple observation allowing an MSOL-definability. (joint work with V. Lozin) \nJuly 26 Friday\nO-joung Kwon (권오정)\, The grid theorem for vertex-minors\nWe prove that\, for a circle graph $H$\, every graph with sufficiently large rank-width contains a vertex-minor isomorphic to $H$. This is joint work with Jim Geelen\, Rose McCarty\, and Paul Wollan. \nJuly 29 Monday\nArchontia Giannopoulou\, The directed flat wall theorem\nAt the core of the Robertson-Seymour theory of Graph Minors lies a powerful structure theorem which captures\, for any fixed graph $H$\, the common structural features of all the graphs not containing $H$ as a minor [Neil Robertson\, Paul D. Seymour: Graph Minors. XVI. Excluding a non-planar graph. J. Comb. Theory\, Ser. B 89(1): 43-76 (2003)]. An important step towards this structure theorem is the Flat Wall Theorem [Neil Robertson\, Paul D. Seymour: Graph Minors .XIII. The Disjoint Paths Problem. J. Comb. Theory\, Ser. B 63(1): 65-110 (1995)]\, which has a lot of algorithmic applications (for example\, the minor-testing and the disjoint paths problem with fixed number terminals).\nIn this paper\, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer)\, and we hope that this is an important and significant step toward the directed structure theorem\, as with the case for the undirected graph for the graph minor project.\nJoint work with Ken-ichi Kawarabayashi\, Stephan Kreutzer\, and O-joung Kwon. \nEunjung Kim (김은정)\, Subcubic even-hole-free graphs have a constant treewidth\nIt is known that even-hole-free graphs can have arbitrarily large rankwidth\, but all known constructions have many high-degree vertices. It has been believed in the structural graph theory community that the rankwidth shall be bounded if the maximum degree is bounded. We prove that there exists a universal constant $c$ such that every even-hole-free graph of degree at most three has treewidth at most $c$. As a by-product of the proof\, we also show that there exists a function $f$ such that for any $r$\, $K_r$-minor-free and even-hole-free graph has treewidth at most $f(r)$; this extends the result of Silva et. al. (Discrete Applied Mathematics 2010) addressing the case of planar graphs.\nThis is a joint work with Pierre Aboulker and Isolde Adler. \nJuly 30 Tuesday\nPierre Aboulker\, Generalizations of the geometric de Bruijn Erdős Theorem\nA classic Theorem of de Bruijn and Erdős states that every noncollinear set of n points in the plane determines at least n distinct lines. The line $L(u\,v)$ determined by two points $u$\, $v$ in the plane consists of all points $p$ such that \n\n$\operatorname{dist}(p\, u)+\operatorname{dist}(u\, v)=\operatorname{dist}(p\, v)$ (i.e. $u$ is between $p$ and $v$) or\n$\operatorname{dist}(u\, p)+\operatorname{dist}(p\, v)=\operatorname{dist}(u\, v)$ (i.e. $p$ is between $u$ and $v$) or\n$\operatorname{dist}(u\, v)+\operatorname{dist}(v\, p)=\operatorname{dist}(u\, p)$ (i.e. $v$ is between $u$ and $p$).\n\nWith this definition of line $L(uv)$ in an arbitrary metric space $(V\, \operatorname{dist})$\, Chen and Chvátal conjectured that every metric space on n points\, where n is at least 2\, has at least n distinct lines or a line that consists of all n points. The talk will survey results on and around this conjecture. \nMichael Dobbins\, Barycenters of points in polytope skeleta\nIn this talk I will classify the n-tuples of dimensions such that any target point in any d-polytope is the barycenter of points in faces of the prescribed dimensions. Specifically\, for a $(nk+r)$-polytope and target point\, we can always find $r$ points in faces of dimension $k+1$\, and $n-r$ points in faces of dimension $k$\, that have their barycenter at the given target. This is tight in the sense that we cannot require even one of the points to be in a face of dimension less than $k$\, and we cannot require more than $n-r$ of the points to be in faces of dimension $k$. This is joint work with Florian Frick. \nJuly 31 Wednesday\nMagnus Wahlström\, FPT-algorithms via LP-relaxations\nLP-relaxations are traditionally (within theoretical computer science) used for computing approximate solutions to NP-hard problems\, but across the last few years there have been several examples where LP-relaxations have been used to guide FPT-algorithms — that is\, exact (non-approximate) algorithms whose running time is bounded in terms of a “parameter” of the input instance.  This approach has given algorithms that are simultaneously simpler and faster for a range of central problems in parameterized complexity.  At the same time\, this is applicable only to specific problems and relaxations; an arbitrary LP-relaxation\, even one that has good properties in an approximation sense\, will in general give no useful guidance with respect to exact solutions. \nIn this talk\, we give an overview of these FPT applications\, and the conditions they impose on the LP-relaxation. Our main focus is on an approach of “discrete relaxation” referred to as Valued CSPs\, but we also briefly survey more immediately combinatorial conditions\, as well as related algorithms that solve these problems more efficiently (e.g.\, so-called linear-time FPT algorithms) by bypassing the LP-solver. \nÉdouard Bonnet\, The FPT/W[1]-hard dichotomy of Max Independent Set in H-free graphs\nMaximum Independent Set (MIS) is in general graphs the paradigmatic W[1]-hard problem. In stark contrast\, polynomial-time algorithms are known when the inputs are restricted to structured graph classes such as\, for instance\, perfect graphs (which includes bipartite graphs\, chordal graphs\, co-graphs\, etc.) or claw-free graphs. In this talk\, we introduce some variants of co-graphs with “parameterized noise”\, that is\, graphs that can be turned into disjoint unions or complete sums by the removal of a certain number of vertices and the edition of a certain number of edges per incident vertex\, both controlled by the parameter. We give a series of FPT Turing-reductions on these classes and use them to make some progress on the parameterized complexity of MIS in $H$-free graphs. We present the current state of the (randomized) FPT vs W[1]-hard dichotomy of MIS in $H$-free graphs. We then show that for every fixed $t \geq 1$\, MIS is FPT in $P(1\,t\,t\,t)$-free graphs\, where $P(1\,t\,t\,t)$ is the graph obtained by substituting all the vertices of a four-vertex path but one end of the path by cliques of size t. In particular\, this helped finishing the classification when H has at most five vertices.\nThis follows joint works with Nicolas Bousquet\, Pierre Charbit\, Stéphan Thomassé\, and Rémi Watrigant. \nAugust 1 Thursday\nEuiwoong Lee (이의웅)\, Losing treewidth by separating subsets\nWe study the problem of deleting the smallest set S of vertices (resp. edges) from a given graph $G$ such that the induced subgraph (resp. subgraph) $G \setminus S$ belongs to some class of graphs $H$. When graphs in H have treewidth bounded by $t$\, we construct a framework for both vertex and edge deletion versions where approximation algorithms for these problems can be obtained from approximation algorithms for natural graph partitioning problems called $k$-Subset Vertex Separator and $k$-Subset Edge Separator.\nFor the vertex deletion\, our framework\, combined with the previous best result for $k$-Subset Vertex Separator\, yields improved approximation ratios for fundamental problems such as $k$-Treewidth Vertex Deletion and Planar-$F$ Vertex Deletion. For the edge deletion\, we give improved approximation algorithms for $k$-Subset Edge Separator and their applications to various problems in bounded-degree graphs.\nJoint work with Anupam Gupta\, Jason Li\, Pasin Manurangsi\, and Michal Wlodarczyk. \nSang-il Oum (엄상일)\, Branch-depth: Generalizing tree-depth of graphs\nWe present a concept called the branch-depth of a connectivity function\, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph $G = (V\,E)$ and a subset $A $ of $E$ we let $\lambda_G (A)$ be the number of vertices incident with an edge in $A$ and an edge in $E \setminus A$. For a subset $X$ of $V$\, let $\rho_G(X)$ be the rank of the adjacency matrix between $X$ and $V \setminus X$ over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions $\lambda_G$ has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions $\rho_G$ has bounded branch-depth\, which we call the rank-depth of graphs.\nFurthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi-ordered by the restriction.\nThis is a joint work with Matt DeVos and O-joung Kwon. \nAugust 2 Friday\nDabeen Lee (이다빈)\, t-perfect graphs and the stable set problem\nA graph $G$ is called $t$-perfect if the stable set polytope of $G$ can be obtained after adding the odd cycle inequalities to the standard edge formulation for the problem. A motivation for studying $t$-perfect graphs is algorithmic: as the odd cycle inequalities can be separated in polynomial time\, one can compute a maximum weight stable set in a $t$-perfect graph by an LP algorithm in polynomial time. There are rich classes of $t$-perfect graphs\, but a complete characterization of $t$-perfect graphs is still open. Due to this\, no graph-theoretic / combinatorial algorithm is known\, although there is an algorithm for the unweighted case based on a combinatorial approximate LP algorithm. In this survey talk\, I will (i) review classes of known $t$-perfect graphs\, (ii) briefly explain the algorithm for the unweighted case and a possibility of extending it to the weighted case\, and (iii) discuss some research directions towards finding a graph-theoretic algorithm for computing a maximum weight stable set in a $t$-perfect graph. \nParticipants (not including IBS researchers)\n\n\n\nPierre Aboulker\, ENS Ulm\, France\nRémy Belmonte\, University of Electro-Communications\, Japan\nBenjamin Bergougnoux\, University of Paris Diderot\, France\nÉdouard Bonnet\, ENS Lyon\, France\nNick Brettell\, Durham University\, UK\nYixin Cao\, Hong Kong Polytechnic University\, China\nMichael Dobbins\, Binghamton University\, USA\nChris Eppolito\, Binghamton University\, USA\nArchontia Giannopoulou\, National and Kapodistrian University of Athens\, Greece\nMamadou M. Kante\, University Clermont Auvergne\, France\nEunjung Kim (김은정)\, LAMSADE-CNRS\, France\nStefan Kratsch\, Humboldt-Universität zu Berlin\, Germany\nO-joung Kwon (권오정)\, Incheon National University\, Korea\nMichael Lampis\, Université Paris-Dauphine\, France\nEuiwoong Lee (이의웅)\, NYU\, USA\nValia Mitsou\, Université Paris-Diderot\, France\nFlorian Sikora\, University Paris Dauphine\, France\nMagnus Wahlström\, Royal Holloway\, University of London\, UK\n\n\n\nAn invitation-only summer research program will be held in the summer of 2019. There will be 10-20 participants to work together at DIMAG. Talks are open. \nAccommodation\nEveryone will stay at the Daedeok Innopolis Guest House (대덕특구게스트하우스). \n\nAddress: 27-5\, Expo-ro 123beon-gil\, Yuseong-gu\, Daejeon\, 34125\, Republic of Korea (대전광역시 유성구 엑스포로 123번길 27-5)\nTel: (+82)-042-865-2500\n\nOrganizers\n\nEunjung Kim (김은정)\, LAMSADE-CNRS\, France\nSang-il Oum (엄상일)\, IBS Discrete Mathematics Group and KAIST\, Korea
URL:https://dimag.ibs.re.kr/event/2019-ibs-summer-research-program/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Research Program
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190716T163000
DTEND;TZID=Asia/Seoul:20190716T173000
DTSTAMP:20260419T164220
CREATED:20190627T074550Z
LAST-MODIFIED:20240707T090234Z
UID:1060-1563294600-1563298200@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, Integrality of set covering polyhedra and clutter minors
DESCRIPTION:Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$\, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem\, also known as the hitting set problem\, admits a simple integer linear programming formulation. The constraint system of the integer linear programming formulation defines a polyhedron\, and we call it the set covering polyhedron of $\mathcal{C}$. We say that a set covering polyhedron is integral if every extreme point is an integer lattice point. Although the set covering problem is NP-hard in general\, conditions under which the problem becomes polynomially solvable have been studied. If the set covering polyhedron is integral\, then it is straightforward that the problem can be solved using a polynomial-time algorithm for linear programming. \nIn this talk\, we will focus on the question of when the set covering polyhedron is integral. We say that the family $\mathcal{C}$ is a clutter if every subset in $\mathcal{C}$ is inclusion-wise minimal. As taking out non-minimal subsets preserves integrality\, we may assume that $\mathcal{C}$ is a clutter. We call $\mathcal{C}$ ideal if the set covering polyhedron of it is integral. To understand when a clutter is ideal\, the notion of clutter minors is important in that $\mathcal{C}$ is ideal if and only if so is every minor of it. We will study two fundamental classes of non-ideal clutters\, namely\, deltas and the blockers of extended odd holes. We will characterize when a clutter contains either a delta or the blocker of an extended odd hole as a minor. \nThis talk is based on joint works with Ahmad Abdi and Gérard Cornuéjols.
URL:https://dimag.ibs.re.kr/event/2019-07-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190625T163000
DTEND;TZID=Asia/Seoul:20190625T173000
DTSTAMP:20260419T164220
CREATED:20190520T133325Z
LAST-MODIFIED:20240707T090302Z
UID:913-1561480200-1561483800@dimag.ibs.re.kr
SUMMARY:Patrice Ossona de Mendez\, A model theoretical approach to sparsity
DESCRIPTION:We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity\, and give some example of applications\, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes\, characterization of transductions of classes with bounded pathwidth\, decompositions of graphs with bounded rank-width into cographs.
URL:https://dimag.ibs.re.kr/event/2019-06-25/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190619T163000
DTEND;TZID=Asia/Seoul:20190619T173000
DTSTAMP:20260419T164220
CREATED:20190418T080534Z
LAST-MODIFIED:20240707T090333Z
UID:789-1560961800-1560965400@dimag.ibs.re.kr
SUMMARY:Suil O (오수일)\, An odd [1\,b]-factor in regular graphs from eigenvalues
DESCRIPTION:An odd $[1\,b]$-factor of a graph is a spanning subgraph $H$ such that for every vertex $v \in V(G)$\, $1 \le d_H(v) \le b$\, and $d_H(v)$ is odd. For positive integers $r \ge 3$ and $b \le r$\, Lu\, Wu\, and Yang gave an upper bound for the third largest eigenvalue in an $r$-regular graph with even number of vertices to guarantee the existence of an odd [1\,b]-factor.\nIn this talk\, we improve their bound.
URL:https://dimag.ibs.re.kr/event/2019-06-19/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190603T163000
DTEND;TZID=Asia/Seoul:20190603T173000
DTSTAMP:20260419T164220
CREATED:20190411T160640Z
LAST-MODIFIED:20240707T090357Z
UID:770-1559579400-1559583000@dimag.ibs.re.kr
SUMMARY:Jinyoung Park (박진영)\, The number of maximal independent sets in the Hamming cube
DESCRIPTION:Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$\, as was conjectured by Ilinca and Kahn in connection with a question of Duffus\, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools\, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$. This is joint work with Jeff Kahn.
URL:https://dimag.ibs.re.kr/event/2019-06-03/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190520T163000
DTEND;TZID=Asia/Seoul:20190520T173000
DTSTAMP:20260419T164220
CREATED:20190304T123855Z
LAST-MODIFIED:20240707T090406Z
UID:642-1558369800-1558373400@dimag.ibs.re.kr
SUMMARY:Lars Jaffke\, A complexity dichotomy for critical values of the b-chromatic number of graphs
DESCRIPTION:A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors.\nThe $b$-chromatic number of a graph $G$\, denoted by $\chi_b(G)$\, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the $b$-Coloring problem\, whenever the value of $k$ is close to one of two upper bounds on $\chi_b(G)$: The maximum degree $\Delta(G)$ plus one\, and the $m$-degree\, denoted by $m(G)$\, which is defined as the maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k \in\{\Delta(G) + 1 − p\, m(G) − p\}$\, the problem is polynomial-time solvable whenever $p\in\{0\, 1\}$ and\, even when $k = 3$\, it is NP-complete whenever $p \ge 2$.\nWe furthermore consider parameterizations of the $b$-Coloring problem that involve the maximum degree $\Delta(G)$ of the input graph $G$ and give two FPT-algorithms. First\, we show that deciding whether a graph G has a $b$-coloring with $m(G)$ colors is FPT parameterized by $\Delta(G)$. Second\, we show that $b$-Coloring is FPT parameterized by $\Delta(G) + \ell_k(G)$\, where $\ell_k(G)$ denotes the number of vertices of degree at least $k$.\nThis is joint work with Paloma T. Lima.
URL:https://dimag.ibs.re.kr/event/2019-05-20/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190516T163000
DTEND;TZID=Asia/Seoul:20190516T173000
DTSTAMP:20260419T164220
CREATED:20190118T041528Z
LAST-MODIFIED:20240707T090507Z
UID:423-1558024200-1558027800@dimag.ibs.re.kr
SUMMARY:Xin Zhang (张欣)\, On equitable tree-colorings of graphs
DESCRIPTION:An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class (i.e\, the set of vertices in a common color) induces a forest and the sizes of any two color classes differ by at most one. The minimum integer $k$ such that a graph $G$ is equitably tree-$k$-colorable is the equitable vertex arboricity of $G$\, denoted by $va_{eq}(G)$. A graph that is equitably tree-$k$-colorable may admits no equitable tree-$k’$-coloring for some $k’>k$. For example\, the complete bipartite graph $K_{9\,9}$ has an equitable tree-$2$-coloring but is not equitably tree-3-colorable. In view of this a new chromatic parameter so-called the equitable vertex arborable threshold is introduced. Precisely\, it is the minimum integer $k$ such that $G$ has an equitable tree-$k’$-coloring for any integer $k’\geq k$\, and is denoted by $va_{eq}^*(G)$. The concepts of the equitable vertex arboricity and the equitable vertex arborable threshold were introduced by J.-L. Wu\, X. Zhang and H. Li in 2013. In 2016\, X. Zhang also introduced the list analogue of the equitable tree-$k$-coloring. There are many interesting conjectures on the equitable (list) tree-colorings\, one of which\, for example\, conjectures that every graph with maximum degree at most $\Delta$ is equitably tree-$k$-colorable for any integer $k\geq (\Delta+1)/2$\, i.e\, $va_{eq}^*(G)\leq \lceil(\Delta+1)/2\rceil$. In this talk\, I review the recent progresses on the studies of the equitable tree-colorings from theoretical results to practical algorithms\, and also share some interesting problems for further research.
URL:https://dimag.ibs.re.kr/event/2019-05-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190508T163000
DTEND;TZID=Asia/Seoul:20190508T173000
DTSTAMP:20260419T164220
CREATED:20190310T074230Z
LAST-MODIFIED:20240707T090513Z
UID:673-1557333000-1557336600@dimag.ibs.re.kr
SUMMARY:Sang June Lee (이상준)\, On strong Sidon sets of integers
DESCRIPTION:Let $\mathbb N$ be the set of natural numbers. A set $A\subset \mathbb N$ is called a Sidon set if the sums $a_1+a_2$\, with $a_1\,a_2\in S$ and $a_1\leq a_2$\, are distinct\, or equivalently\, if \[|(x+w)-(y+z)|\geq 1\] for every $x\,y\,z\,w\in S$ with $x<y\leq z<w$. We define strong Sidon sets as follows: \nFor a constant $\alpha$ with $0\leq \alpha<1$\, a set $S\subset \mathbb N$ is called an $\alpha$-strong Sidon set if \[|(x+w)-(y+z)|\geq w^\alpha\] for every $x\,y\,z\,w\in S$ with $x<y\leq z<w$. \nThe motivation of strong Sidon sets is that a strong Sidon set generates many Sidon sets by altering each element a bit. This infers that a dense strong Sidon set will guarantee a dense Sidon set contained in a sparse random subset of $\mathbb N$. \nIn this talk\, we are interested in how dense a strong Sidon set can be. This is joint work with Yoshiharu Kohayakawa\, Carlos Gustavo Moreira and Vojtěch Rödl.
URL:https://dimag.ibs.re.kr/event/2019-05-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190426T160000
DTEND;TZID=Asia/Seoul:20190426T170000
DTSTAMP:20260419T164220
CREATED:20190309T122202Z
LAST-MODIFIED:20240705T211023Z
UID:666-1556294400-1556298000@dimag.ibs.re.kr
SUMMARY:Rose McCarty\, Circle graphs are polynomially chi-bounded
DESCRIPTION:Circle graphs are the intersection graphs of chords on a circle; vertices correspond to chords\, and two vertices are adjacent if their chords intersect. We prove that every circle graph with clique number k has chromatic number at most $4k^2$. Joint with James Davies.
URL:https://dimag.ibs.re.kr/event/2019-04-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190418T110000
DTEND;TZID=Asia/Seoul:20190418T120000
DTSTAMP:20260419T164220
CREATED:20190403T013055Z
LAST-MODIFIED:20240707T090539Z
UID:733-1555585200-1555588800@dimag.ibs.re.kr
SUMMARY:Jon-Lark Kim (김종락)\, Introduction to Boolean functions with Artificial Neural Network
DESCRIPTION:A Boolean function is a function from the set Q of binary vectors of length n (i.e.\, the binary n-dimensional hypercube) to $F_2=\{0\,1\}$. It has several applications to complexity theory\, digital circuits\, coding theory\, and cryptography.\nIn this talk we give a connection between Boolean functions and Artificial Neural Network. We describe how to represent Boolean functions by Artificial Neural Network including linear and polynomial threshold units and sigmoid units. For example\, even though a linear threshold function cannot realize XOR\, a polynomial threshold function can do it. We also give currently open problems related to the number of (Boolean) linear threshold functions and polynomial threshold functions.
URL:https://dimag.ibs.re.kr/event/2019-04-18/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190312T163000
DTEND;TZID=Asia/Seoul:20190312T173000
DTSTAMP:20260419T164220
CREATED:20190226T113020Z
LAST-MODIFIED:20240707T090549Z
UID:635-1552408200-1552411800@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Large cliques in hypergraphs with forbidden substructures
DESCRIPTION:A result due to Gyárfás\, Hubenko\, and Solymosi\, answering a question of Erdős\, asserts that if a graph $G$ does not contain $K_{2\,2}$ as an induced subgraph yet has at least $c\binom{n}{2}$ edges\, then $G$ has a complete subgraph on at least $\frac{c^2}{10}n$ vertices. In this paper we suggest a “higher-dimensional” analogue of the notion of an induced $K_{2\,2}$\, which allows us to extend their result to $k$-uniform hypergraphs. Our result also has interesting consequences in topological combinatorics and abstract convexity\, where it can be used to answer questions by Bukh\, Kalai\, and several others.
URL:https://dimag.ibs.re.kr/event/2019-03-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20190211
DTEND;VALUE=DATE:20190213
DTSTAMP:20260419T164221
CREATED:20190118T003152Z
LAST-MODIFIED:20240707T090601Z
UID:396-1549843200-1550015999@dimag.ibs.re.kr
SUMMARY:2019-1 IBS Workshop on Graph Theory
DESCRIPTION:Invited Speakers\n\nJeong Han Kim (김정한)\, KIAS\, Seoul\nMartin Balko\, Charles University\, Prague\nDániel Gerbner\, Alfréd Rényi Institute of Mathematics\, Budapest\nCory T. Palmer\, University of Montana\, Missoula\nBoram Park (박보람)\, Ajou University\nDong Yeap Kang (강동엽)\, KAIST\n\nSchedule\nFeb. 11\, 2019\, Monday\n1:30pm-2:20pm Jeong Han Kim: Entropy and sorting\n2:20pm-3:10pm Cory T. Palmer: Generalized Turán problems – Berge hypergraphs\nCoffee Break\n4:00pm-4:50pm Martin Balko: Ramsey numbers of edge-ordered graphs\n4:50pm-5:40pm Dong Yeap Kang: On the rational Turán exponents conjecture\nBanquet \nFeb. 12\, 2019\, Tuesday\n9:30am-10:20am Boram Park: Sum-free set problem on integers\nCoffee Break\n11:00am-11:50am Dániel Gerbner: Generalized Turán problems – counting subgraphs\nLunch \nWe plan to provide meals to all participants and provide a room at a near-by hotel for invited speakers and selected participants. Please register in the following form below by January 28\, Monday; please register early if you want to receive the support for the accommodation. \nAbstracts\nJeong Han Kim (김정한)\, Entropy and Sorting \nWe reconsider the old problem of sorting under partial information\, and give polynomial time algorithms for the following tasks: (1) Given a partial order P\, find (adaptively) a sequence of comparisons (questions of the form\, “is x < y?”) which sorts ( i.e.\, finds an unknown linear extension of) P using O(log(e(P))) comparisons in worst case (where e(P) is the number of linear extensions of P). (2) Compute (on line) answers to any comparison algorithm for sorting a partial order P which force the algorithm to use Ω(log(e(P))) comparisons. (3) Given a partial order P of size n\, estimate e(P) to within a factor exponential in n. (We give upper and lower bounds which differ by the factor $n^n /n!$.) Our approach\, based on entropy of the comparability graph of P and convex minimization via the ellipsoid method\, is completely different from earlier attempts to deal with these questions. \nJoint work with J. Kahn. \nCory T. Palmer\, Generalized Turán problems – Berge hypergraphs\nLet $F$ be a graph. We say that a hypergraph $H$ is a Berge-$F$ if there is a bijection $f : E(F) \rightarrow E(H )$ such that $e \subseteq f(e)$ for every $e \in E(F)$. Note that Berge-$F$ actually denotes a class of hypergraphs. The maximum number of edges in an $n$-vertex $r$-graph with no subhypergraph isomorphic to any Berge-$F$ is denoted $\operatorname{ex}_r(n\,\textrm{Berge-}F)$. Observe that when $r=2$\, then a Berge-$F$ is simply the graph $F$ and thus again we! are investigating the Tur\’an function $\operatorname{ex}(n\,F)$. \nIn this talk we will survey results on the function $\operatorname{ex}_r(n\,\textrm{Berge-}F)$ for various graphs $F$. We will also describe several interesting open problems. \nMartin Balko\, Ramsey numbers of edge-ordered graphs\nAn edge-ordered graph is a graph with linearly ordered set of edges. We introduce and study Ramsey numbers of edge-ordered graphs\, called edge-ordered Ramsey numbers. We prove some basic properties of these numbers for general edge! -ordered graphs and we provide some stronger estimates for special classes of edge-ordered graphs. We also pose some new open problems and compare edge-ordered Ramsey numbers with the standard Ramsey numbers of graphs and with ordered Ramsey numbers\, which are Ramsey numbers for graphs with linearly ordered vertex sets. \nJoint work with Mate Vizer. \nDong Yeap Kang (강동엽)\, On the rational Turán exponents conjecture\nThe extremal number ${\rm ex}(n\,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1\,2]$ is realisable if there exists a graph $F$ with ${\rm ex}(n \, F) = \Theta(n^r)$. Several decades ago\, Erdős and Simonovits conjectured that every rational number in $[1\,2]$ is realisable. Despite decades of effort\, the only known realisable numbers are $1\,\frac{7}{5}\,2$\, and the numbers of the form $1+\frac{1}{m}$\, $2-\frac{1}{m}$\, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular\, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2. \nWe discuss some recent progress on the conjecture of Erdős and Simonovits. First\, we show that $2 – \frac{a}{b}$ is realisable for any integers $a\,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones\, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence. \nSecondly\, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own\, we show that\, somewhat surprisingly\, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable. \nThis is joint work with Jaehoon Kim and Hong Liu. \nBoram Park (박보람)\, Sum-free set problem on integers\nFor an abelian  group $G$\, a set $A \subset G$ is sum-free if there are no $x\, y\, z \in A$ such that $x + y = z$. Sum-free sets was initiated by Schur (1916) by an attempt to prove the famous Fermat’s Last Theorem. Since then\, there have been intensive and fruitful research in the field of additive combinatorics. One of great interest in the study of sum-free sets is to consider sum-free subsets of a set of integers\, which has attracted a significant attention in the literature over the years. \nIn this talk\, some recent results on sum-free sets of integers are discussed. Then we present a result on $k$-sum $\bf{n}$-free set\, where $\bf{n}$ is an $n$-dimensional integer vector. The work is based on joint work with Ilkyoo Choi and Ringi Kim. \nDániel Gerbner\, Generalized Turán problems – counting subgraphs\nGiven two graphs $H$ and $F$\, our goal is to determine the maximum number of copies of $H$ in an $F$-free graph on $n$ vertices. The systematic research of these problems was initiated (after several sporadic results) by Alon and Shikhelman. I describe several results of mine in this area\, with different sets of co-authors. \nJoint work with Ervin Győri\, Abhishek Methuku\, Cory Palmer and Mate Vizer.
URL:https://dimag.ibs.re.kr/event/2019-1-graph-theory/
LOCATION:Room B234\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190128T160000
DTEND;TZID=Asia/Seoul:20190128T170000
DTSTAMP:20260419T164221
CREATED:20190102T015548Z
LAST-MODIFIED:20240705T211438Z
UID:348-1548691200-1548694800@dimag.ibs.re.kr
SUMMARY:Seog-Jin Kim (김석진)\, Signed colouring and list colouring of  k-chromatic graphs
DESCRIPTION:A signed graph is a pair (G\, σ)\, where G is a graph and σ: E(G) → {1\,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G\,σ) is a mapping f:V(G) → Nk such that for each edge e=uv\, f(x)≠σ(e) f(y)\, where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G\, (G\, σ) has a k-colouring. \nLet f(n\,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n\,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G\, for any signature σ on G\, there is a proper L-colouring of (G\, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand\, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result\, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.
URL:https://dimag.ibs.re.kr/event/2019-01-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190104T160000
DTEND;TZID=Asia/Seoul:20190104T170000
DTSTAMP:20260419T164221
CREATED:20181217T143613Z
LAST-MODIFIED:20240705T211439Z
UID:279-1546617600-1546621200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, New algorithm for multiway cut guided by strong min-max duality
DESCRIPTION:Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then\, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design. \nIn this talk\, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds\, namely μ(I)=2LP(I)-IP(dual-I). Here\, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result\, we obtain an algorithm running in time 4k-μ(I) for multiway cut and its generalizations\, where k is the budget for a solution. \nThis talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.
URL:https://dimag.ibs.re.kr/event/2019-01-04/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190103T160000
DTEND;TZID=Asia/Seoul:20190103T170000
DTSTAMP:20260419T164221
CREATED:20181224T085518Z
LAST-MODIFIED:20240707T090650Z
UID:305-1546531200-1546534800@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, Sidorenko’s conjecture for blow-ups
DESCRIPTION:A celebrated conjecture of Sidorenko and Erdős–Simonovits states that\, for all bipartite graphs H\, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs\, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion. \nOur contribution here\, which goes beyond this paradigm\, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary\, we have that for every bipartite graph H with bipartition A∪B\, there is a positive integer p such that the blow-up HAp formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Joint work with David Conlon.
URL:https://dimag.ibs.re.kr/event/2019-01-03/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20181213T170000
DTEND;TZID=Asia/Seoul:20181213T180000
DTSTAMP:20260419T164221
CREATED:20181120T125609Z
LAST-MODIFIED:20240707T090704Z
UID:250-1544720400-1544724000@dimag.ibs.re.kr
SUMMARY:Hong Liu\, Polynomial Schur’s Theorem
DESCRIPTION:I will discuss the Ramsey problem for {x\,y\,z:x+y=p(z)} for polynomials p over ℤ. This is joint work with Peter Pach and Csaba Sandor.
URL:https://dimag.ibs.re.kr/event/2018-12-13/
LOCATION:Room B109\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20181210T170000
DTEND;TZID=Asia/Seoul:20181210T180000
DTSTAMP:20260419T164221
CREATED:20181031T151146Z
LAST-MODIFIED:20240707T090718Z
UID:180-1544461200-1544464800@dimag.ibs.re.kr
SUMMARY:Tony Huynh\, A tight Erdős-Pósa function for planar minors
DESCRIPTION:Let H be a planar graph. By a classical result of Robertson and Seymour\, there is a function f(k) such that for all k and all graphs G\, either G contains k vertex-disjoint subgraphs each containing H as a minor\, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible\, up to the value of c\, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log 𝖮𝖯𝖳)-approximation algorithm for packing subgraphs containing an H-minor. \nThis is joint work with Wouter Cames van Batenburg\, Gwenaël Joret\, and Jean-Florent Raymond.
URL:https://dimag.ibs.re.kr/event/2018-12-10/
LOCATION:Room B109\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR