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:20191226T163000 DTEND;TZID=Asia/Seoul:20191226T173000 DTSTAMP:20260418T231854 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:20260418T231854 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:20260418T231854 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:20260418T231854 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:20260418T231854 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:20260418T231854 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:20260418T231854 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:20260418T231854 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:20260418T231854 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:20260418T231854 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 BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191029T163000 DTEND;TZID=Asia/Seoul:20191029T173000 DTSTAMP:20260418T231854 CREATED:20191027T110551Z LAST-MODIFIED:20240707T090010Z UID:1632-1572366600-1572370200@dimag.ibs.re.kr SUMMARY:Pascal Gollin\, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs DESCRIPTION:Given a cardinal $\lambda$\, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$\, and a $\lambda$-covering of $G$ is a family of spanning trees covering $E(G)$. \nWe show that if a graph admits a $\lambda$-packing and a $\lambda$-covering  then the graph also admits a decomposition into $\lambda$ many spanning trees. In this talk\, we concentrate on the case of $\lambda$ being an infinite cardinal. Moreover\, we will provide a new and simple proof for a theorem of Laviolette characterising the existence of a $\lambda$-packing\, as well as for a theorem of Erdős and Hajnal characterising the existence of a $\lambda$-covering. \nJoint work with Joshua Erde\, Attila Joó\, Paul Knappe and Max Pitz. URL:https://dimag.ibs.re.kr/event/2019-10-29/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;VALUE=DATE:20191026 DTEND;VALUE=DATE:20191028 DTSTAMP:20260418T231854 CREATED:20190910T133412Z LAST-MODIFIED:20240707T090017Z UID:1366-1572048000-1572220799@dimag.ibs.re.kr SUMMARY:Extremal and Structural Graph Theory (2019 KMS Annual Meeting) DESCRIPTION:Focus Session @ 2019 KMS Annual Meeting\nA focus session “Extremal and Structural Graph Theory” at the 2019 KMS Annual Meeting is organized by Sang-il Oum. URL: http://www.kms.or.kr/meetings/fall2019/ \nSpeakers\n\nIlkyoo Choi (최일규)\, Hankuk University of Foreign Studies\nKevin Hendrey\, IBS Discrete Mathematics Group\nPascal Gollin\, IBS Discrete Mathematics Group\nJaehoon Kim (김재훈)\, KAIST\nRingi Kim (김린기)\, KAIST\nSeog-Jin Kim (김석진)\, Konkuk University\nO-joung Kwon (권오정)\, Incheon National University / IBS Discrete Mathematics Group\nZi-Xia Song (宋梓霞)\, University of Central Florida\nCasey Tompkins\, IBS Discrete Mathematics Group\n\nSchedules\n\nSlot A: October 26\, 2019 Saturday\, 9:00am-10:15am\n\nSeog-Jin Kim\nKevin Hendrey\nIlkyoo Choi\n\n\nSlot B: October 26\, 2019 Saturday\, 10:40am-11:55pm\n\nJaehoon Kim\nRingi Kim\nCasey Tompkins\n\n\nSlot D: October 27\, 2019 Sunday\, 9:00am-10:15am\n\nZi-Xia Song\nPascal Gollin\nO-joung Kwon\n\n\n\nAbstracts\nIlkyoo Choi (최일규)\, Degeneracy and colorings of squares of planar graphs without 4-cycles\nWe prove several results on coloring squares of planar graphs without 4-cycles. First\, we show that if $G$ is such a graph\, then $G^2$ is $(\Delta(G)+72)$-degenerate. This implies an upper bound of $\Delta(G)+73$ on the chromatic number of $G^2$ as well as on several variants of the chromatic number such as the list-chromatic number\, paint number\, Alon–Tarsi number\, and correspondence chromatic number. We also show that if $\Delta(G)$ is sufficiently large\, then the upper bounds on each of these parameters of $G^2$ can all be lowered to $\Delta(G)+2$ (which is best possible). To complement these results\, we show that 4-cycles are unique in having this property. Specifically\, let $S$ be a finite list of positive integers\, with $4\notin S$. For each constant $C$\, we construct a planar graph $G_{S\,C}$ with no cycle with length in $S$\, but for which $\chi(G_{S\,C}^2) > \Delta(G_{S\,C})+C$. This is joint work with Dan Cranston and Theo Pierron. \nKevin Hendrey\, Defective and clustered choosability of sparse graphs\nAn (improper) graph colouring has defect $d$ if each monochromatic subgraph has maximum degree at most $d$\, and has clustering $c$ if each monochromatic component has at most $c$ vertices. Given an infinite class of graphs $\mathcal{G}$\, it is interesting to ask for the minimum integer $\chi_{\Delta}(\mathcal{G})$ for which there exist an integer $d$ such that every graph in $\mathcal{G}$ has a $\chi_{\Delta}(\mathcal{G})$-colouring with defect at most $d$\, and the minimum integer $\chi_{\star}(\mathcal{G})$-colouring for which there exist an integer $c$ such that every graph in $\mathcal{G}$ has a $\chi_{\star}(\mathcal{G})$-colouring with clustering at most $c$. We explore clustered and defective colouring in graph classes with bounded maximum average degree. As an example\, our results show that every earth-moon graph has an 8-colouring with clustering at most 405. Our results hold in the stronger setting of list-colouring. Joint work with David Wood. \nPascal Gollin\, Progress on the Ubiquity Conjecture\nA classic result of Halin says that if a graph $G$ contains for every $n \in \mathbb{N}$ as subgraphs $n$ disjoint rays\, i.e.\, one-way infinite paths\, then $G$ already contains infinitely many disjoint rays as subgraphs. We say a graph $G$ is ubiquitous with respect to the subgraph relation if whenever a graph $\Gamma$ contains $n$ disjoint copies of $G$ as a subgraph for all $n \in \mathbb{N}$\, then $\Gamma$ already contains infinitely many disjoint copies of $G$ as a subgraph. We define ubiquity w.r.t. the minor relation or topological minor relation analogously. A fundamental conjecture about infinite graphs due to Andreae is the Ubiquity Conjecture. It states that every locally finite connected graph is ubiquitous w.r.t. the minor relation. In a series of papers we make progress on the conjecture proving various ubiquity results w.r.t. both the topological minor relation and the minor relation\, making use of well-quasi ordering techniques. \nJaehoon Kim (김재훈)\, A rainbow version of Dirac’s theorem\nFor a collection $\mathbf{G}=\{G_1\,\dots\, G_s\}$ of graphs\, we say that a graph $H$ is $\mathbf{G}$-transversal\, or $\mathbf{G}$-rainbow\, if there exists a bijection $\phi:E(H)\rightarrow [s]$ with $e\in G_{\phi(e)}$ for all $e\in E(H)$. Aharoni conjectured that if for each $i\in [r]$\, then graph $G_i$ is an $n$-vertex graph on the same vertex set $V$ and $\delta(G_i)\geq n/2$ for all $i\in [s]$\, then there exists a $\mathbf{G}$-transversal Hamilton cycle on $V$. We prove this conjecture. We also prove a similar result for $K_r$-factors. This is joint work with Felix Joos. \nRingi Kim (김린기)\, Obstructions for partitioning into forests\nFor a class $\mathcal{C}$ of graphs\, we de fine $\mathcal{C}$-edge-brittleness of a graph $G$ as the minimum $\ell$ such that the vertex set of $G$ can be partitioned into sets inducing a subgraph in $\mathcal{C}$ and there are $\ell$ edges having ends in distinct parts. In this talk\, we characterize classes of graphs having bounded $\mathcal{C}$-edge-brittleness for a class $\mathcal{C}$ of forests in terms of forbidden obstructions. This is joint work with Sang-il Oum and Sergey Norin. \nSeog-Jin Kim (김석진)\, The Alon-Tarsi number of subgraphs of a planar graph\nThis paper constructs a planar graph $G_1$ such that for any subgraph $H$ of $G_1$ with maximum degree $\Delta(H) \le 3$\, $G_1-E(H)$ is not $3$-choosable\, and a planar graph $G_2$ such that for any star forest $F$ in $G_2$\, $G_2-E(F)$ contains a copy of $K_4$ and hence $G_2-E(F)$ is not $3$-colourable. On the other hand\, we prove that every planar graph $G$ contains a forest $F$ such that the Alon-Tarsi number of $G – E(F)$ is at most $3$\, and hence $G – E(F)$ is 3-paintable and 3-choosable. This is joint work with Ringi Kim and Xuding Zhu. \nO-joung Kwon (권오정)\, Erdős-Pósa property of H-induced subdivisions\nA class $\mathcal{F}$ of graphs has the induced Erdős-Pósa property if there exists a function $f$ such that for every graph $G$ and every positive integer $k$\, $G$ contains either $k$ pairwise vertex-disjoint induced subgraphs that belong to $\mathcal{F}$\, or a vertex set of size at most $f(k)$ hitting all induced copies of graphs in $\mathcal{F}$. Kim and Kwon (SODA’18) showed that for a cycle $C_{\ell}$ of length $\ell$\, the class of $C_{\ell}$-subdivisions has the induced Erdős-Pósa property if and only if $\ell\le 4$. In this paper\, we investigate whether or not the class of $H$-subdivisions has the induced Erdős-Pósa property for other graphs $H$. We completely settle the case when $H$ is a forest or a complete bipartite graph. Regarding the general case\, we identify necessary conditions on $H$ for the class of $H$-subdivisions to have the induced Erdős-Pósa property. For this\, we provide three basic constructions that are useful to prove that the class of the subdivisions of a graph does not have the induced Erdős-Pósa property. Among remaining graphs\, we prove that if $H$ is either the diamond\, the $1$-pan\, or the $2$-pan\, then the class of $H$-subdivisions has the induced Erdős-Pósa property. \nZi-Xia Song\, On the size of $(K_t\,\mathcal{T}_k)$-co-critical graphs\nGiven an integer $r\ge1$ and graphs $G\, H_1\, \ldots\, H_r$\, we write $G \rightarrow ({H}_1\, \ldots\, {H}_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$ for some $i\in\{1\, \ldots\, r\}$. A non-complete graph $G$ is $(H_1\, \ldots\, H_r)$-co-critical if $G \nrightarrow ({H}_1\, \ldots\, {H}_r)$\, but $G+e\rightarrow ({H}_1\, \ldots\, {H}_r)$ for every edge $e$ in $\overline{G}$. Motivated by Hanson and Toft’s conjecture\, we study the minimum number of edges over all $(K_t\, \mathcal{T}_k)$-co-critical graphs on $n$ vertices\, where $\mathcal{T}_k$ denotes the family of all trees on $k$ vertices. In this talk\, we will present our recent results on this topic. This is joint work with Jingmei Zhang. \nCasey Tompkins\, Generalizations of the Erdős-Gallai theorem\nA classical result of Erdős and Gallai bounds the number of edges in an $n$-vertex graph with no path of length $k$ (denoted $P_k$). In this talk\, I will discuss generalizations of this result in multiple settings. In one direction\, I will consider so-called generalized Turán problems for $P_k$-free graphs. That is\, rather than maximizing the number of edges\, we consider maximizing the number of copies of some graph $H$. Building on results of Luo where $H$ is a clique\, we consider the case when $H$ is also a path. In another direction\, I will consider Erdős-Gallai type problems in a hypergraph setting. Here I will discuss recent results involving forbidding Berge copies of a path\, including the solution to some problems and conjectures of Győri\, Katona and Lemons as well Füredi\, Kostochka and Luo. I will also mention some Kopylov-type variants of this problem where the hypergraph is assumed to be connected. Moreover\, I will discuss some recent work on forbidding Berge copies of a tree. Finally\, as time permits I will mention some colored variants of the Erdős-Gallai problem. The new results presented are joint work with various subsets of the authors Akbar Davoodi\, Beka Ergemlidze\, Ervin Győri\, Abhishek Methuku\, Nika Salia\, Mate Vizer\, Oscar Zamora. URL:https://dimag.ibs.re.kr/event/2019-10-26/ LOCATION:Room 426\, Hong-Mun Hall\, Hongik University\, Seoul CATEGORIES:Workshops and Conferences END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191022T163000 DTEND;TZID=Asia/Seoul:20191022T173000 DTSTAMP:20260418T231854 CREATED:20190920T222518Z LAST-MODIFIED:20240707T090027Z UID:1407-1571761800-1571765400@dimag.ibs.re.kr SUMMARY:Joonkyung Lee (이준경)\, On some properties of graph norms DESCRIPTION:For a graph $H$\, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$\, $p\geq e(H)$\, denoted by $t_H(W)$. One may then define corresponding functionals $\|W\|_{H}:=|t_H(W)|^{1/e(H)}$ and $\|W\|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $\|.\|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $\|.\|_{r(H)}$ is a norm. \nWe obtain some results that contribute to the theory of (weakly) norming graphs. Firstly\, we show that ‘twisted’ blow-ups of cycles\, which include $K_{5\,5}\setminus C_{10}$ and $C_6\square K_2$\, are not weakly norming. This answers two questions of Hatami\, who asked whether the two graphs are weakly norming. Secondly\, we prove that $\|.\|_{r(H)}$ is not uniformly convex nor uniformly smooth\, provided that $H$ is weakly norming. This answers another question of Hatami\, who estimated the modulus of convexity and smoothness of $\|.\|_{H}$. We also prove that every graph $H$ without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of $H$ when studying graph norms. Based on joint work with Frederik Garbe\, Jan Hladký\, and Bjarne Schülke. URL:https://dimag.ibs.re.kr/event/2019-10-22/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191015T163000 DTEND;TZID=Asia/Seoul:20191015T173000 DTSTAMP:20260418T231854 CREATED:20190920T222934Z LAST-MODIFIED:20240707T090036Z UID:1409-1571157000-1571160600@dimag.ibs.re.kr SUMMARY:Zi-Xia Song (宋梓霞)\, Ramsey numbers of cycles under Gallai colorings DESCRIPTION:For a graph $H$ and an integer $k\ge1$\, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4 $ vertices. For odd cycles\, Bondy and Erd\H{o}s in 1973 conjectured that for all $k\ge1$ and $n\ge2$\, $R_k(C_{2n+1})=n\cdot 2^k+1$. Recently\, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson. Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings\, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings. \nJoint work with Dylan Bruce\, Christian Bosse\, Yaojun Chen and Fangfang Zhang. URL:https://dimag.ibs.re.kr/event/2019-10-15/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191010T163000 DTEND;TZID=Asia/Seoul:20191010T173000 DTSTAMP:20260418T231854 CREATED:20190710T015315Z LAST-MODIFIED:20240707T090044Z UID:1081-1570725000-1570728600@dimag.ibs.re.kr SUMMARY:Alexandr V. Kostochka\, Reconstructing graphs from smaller subgraphs DESCRIPTION:A graph or graph property is $\ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $\ell$ vertices. Apart from the famous Graph Reconstruction Conjecture\, Kelly conjectured in 1957 that for each $\ell\in\mathbb N$\, there is an integer $n=n(\ell)$ such that every graph with at least $n$ vertices is $\ell$-reconstructible. \nWe show that for each $n\ge7$ and every $n$-vertex graph $G$\, the degree list and connectedness of $G$ are $3$-reconstructible\, and the threshold $n\geq 7$ is sharp for both properties.‌ We also show that all $3$-regular graphs are $2$-reconstructible. URL:https://dimag.ibs.re.kr/event/2019-10-10/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191008T163000 DTEND;TZID=Asia/Seoul:20191008T173000 DTSTAMP:20260418T231854 CREATED:20190709T235022Z LAST-MODIFIED:20240705T210004Z UID:1072-1570552200-1570555800@dimag.ibs.re.kr SUMMARY:Alexandr V. Kostochka\, On Ramsey-type problems for paths and cycles in dense graphs DESCRIPTION:A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally\, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors\, there is a monochromatic copy of $H$. In these terms\, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$. \nWe consider sufficient conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular\, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás\, Ruszinkó\, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp. \nThis is joint work with Jozsef Balogh\, Mikhail Lavrov and Xujun Liu. URL:https://dimag.ibs.re.kr/event/2019-10-08/ LOCATION:Room 1501\, Bldg. E6-1\, KAIST CATEGORIES:Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191001T163000 DTEND;TZID=Asia/Seoul:20191001T173000 DTSTAMP:20260418T231854 CREATED:20190916T044737Z LAST-MODIFIED:20240705T204218Z UID:1387-1569947400-1569951000@dimag.ibs.re.kr SUMMARY:Casey Tompkins\, Extremal problems for Berge hypergraphs DESCRIPTION:Given a graph $G$\, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In this talk\, we discuss Turán problems for families $BG$ in $r$-uniform hypergraphs for various graphs $G$. In particular\, we are interested in general results in two settings: the case when $r$ is large and $G$ is any graph where this Turán number is shown to be eventually subquadratic\, as well as the case when $G$ is a tree where several exact results can be obtained. The results in the first part are joint with Grósz and Methuku\, and the second part with Győri\, Salia and Zamora. URL:https://dimag.ibs.re.kr/event/2019-10-01/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190919T163000 DTEND;TZID=Asia/Seoul:20190919T173000 DTSTAMP:20260418T231854 CREATED:20190815T090406Z LAST-MODIFIED:20240707T090104Z UID:1277-1568910600-1568914200@dimag.ibs.re.kr SUMMARY:Cory Palmer\, A survey of Turán-type subgraph counting problems DESCRIPTION:Let $F$ and $H$ be graphs. The subgraph counting function $\operatorname{ex}(n\,H\,F)$ is defined as the maximum possible number of subgraphs $H$ in an $n$-vertex $F$-free graph. This function is a direct generalization of the Turán function as $\operatorname{ex}(n\,F)=\operatorname{ex}(n\,K_2\,F)$. The systematic study of $\operatorname{ex}(n\,H\,F)$ was initiated by Alon and Shikhelman in 2016 who generalized several classical results in extremal graph theory to the subgraph counting setting. Prior to their paper\, a number of individual cases were investigated; a well-known example is the question to determine the maximum number of pentagons in a triangle-free graph. In this talk we will survey results on the function $\operatorname{ex}(n\,H\,F)$ including a number of recent papers. We will also discuss this function’s connection to hypergraph Turán problems. URL:https://dimag.ibs.re.kr/event/2019-09-19/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190910T163000 DTEND;TZID=Asia/Seoul:20190910T173000 DTSTAMP:20260418T231854 CREATED:20190903T042102Z LAST-MODIFIED:20240707T090111Z UID:1337-1568133000-1568136600@dimag.ibs.re.kr SUMMARY:Kevin Hendrey\, The minimum connectivity forcing forest minors in large graphs DESCRIPTION:Given a graph $G$\, we define $\textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t\,G)$ such that every $t$-connected graph with at least $N(t\,G)$ vertices contains $G$ as a minor. The value of $\textrm{ex}_c(G)$ is known to be tied to the vertex cover number $\tau(G)$\, and in fact $\tau(G)\leq \textrm{ex}_c(G)\leq \frac{31}{2}(\tau(G)+1)$. We give the precise value of $\textrm{ex}_c(G)$ when $G$ is a forest. In particular we find that $\textrm{ex}_c(G)\leq \tau(G)+2$ in this setting\, which is tight for infinitely many forests. URL:https://dimag.ibs.re.kr/event/2019-09-10/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190820T163000 DTEND;TZID=Asia/Seoul:20190820T173000 DTSTAMP:20260418T231854 CREATED:20190619T105835Z LAST-MODIFIED:20240707T090132Z UID:1031-1566318600-1566322200@dimag.ibs.re.kr SUMMARY:Mihyun Kang (강미현)\, The genus of a random graph and the fragile genus property DESCRIPTION:In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges can increase the genus of a randomly perturbed graph. (Joint work with Chris Dowden and Michael Krivelevich) URL:https://dimag.ibs.re.kr/event/2019-08-20/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;VALUE=DATE:20190813 DTEND;VALUE=DATE:20190816 DTSTAMP:20260418T231854 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:20260418T231854 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)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:20260418T231855 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