BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN CALSCALE:GREGORIAN METHOD:PUBLISH X-ORIGINAL-URL:https://dimag.ibs.re.kr X-WR-CALDESC:Events for Discrete Mathematics Group REFRESH-INTERVAL;VALUE=DURATION:PT1H X-Robots-Tag:noindex X-PUBLISHED-TTL:PT1H BEGIN:VTIMEZONE TZID:Asia/Seoul BEGIN:STANDARD TZOFFSETFROM:+0900 TZOFFSETTO:+0900 TZNAME:KST DTSTART:20210101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230516T163000 DTEND;TZID=Asia/Seoul:20230516T173000 DTSTAMP:20260506T084659 CREATED:20230116T010528Z LAST-MODIFIED:20240707T073700Z UID:6669-1684254600-1684258200@dimag.ibs.re.kr SUMMARY:Oliver Janzer\, Small subgraphs with large average degree DESCRIPTION:We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$\, we prove that every graph on $n$ vertices with average degree at least $d$ contains a subgraph of average degree at least $s$ on at most $nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}$ vertices. This is optimal up to the polylogarithmic factor\, and resolves a conjecture of Feige and Wagner. In addition\, we show that every graph with $n$ vertices and average degree at least $n^{1-\frac{2}{s}+\varepsilon}$ contains a subgraph of average degree at least $s$ on $O_{\varepsilon\,s}(1)$ vertices\, which is also optimal up to the constant hidden in the $O(.)$ notation\, and resolves a conjecture of Verstraëte. \nJoint work with Benny Sudakov and Istvan Tomon. URL:https://dimag.ibs.re.kr/event/2023-05-16/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230509T163000 DTEND;TZID=Asia/Seoul:20230509T173000 DTSTAMP:20260506T084659 CREATED:20230413T233653Z LAST-MODIFIED:20240707T073713Z UID:7041-1683649800-1683653400@dimag.ibs.re.kr SUMMARY:Jozef Skokan\, Separating the edges of a graph by a linear number of paths DESCRIPTION:Recently\, Letzter proved that any graph of order n contains a collection P of $O(n \log^*n)$ paths with the following property: for all distinct edges e and f there exists a path in P which contains e but not f. We improve this upper bound to 19n\, thus answering a question of Katona and confirming a conjecture independently posed by Balogh\, Csaba\, Martin\, and Pluhar and by Falgas-Ravry\, Kittipassorn\, Korandi\, Letzter\, and Narayanan. \nOur proof is elementary and self-contained. URL:https://dimag.ibs.re.kr/event/2023-05-09/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230502T163000 DTEND;TZID=Asia/Seoul:20230502T173000 DTSTAMP:20260506T084659 CREATED:20230315T140009Z LAST-MODIFIED:20240705T164210Z UID:6916-1683045000-1683048600@dimag.ibs.re.kr SUMMARY:Rob Morris\, An exponential improvement for diagonal Ramsey DESCRIPTION:The Ramsey number $R(k)$ is the minimum n such that every red-blue colouring of the edges of the complete graph on n vertices contains a monochromatic copy of $K_k$. It has been known since the work of Erdős and Szekeres in 1935\, and Erdős in 1947\, that $2^{k/2} < R(k) < 4^k$\, but in the decades since the only improvements have been by lower order terms. In this talk I will sketch the proof of a very recent result\, which improves the upper bound of Erdős and Szekeres by a (small) exponential factor. \nBased on joint work with Marcelo Campos\, Simon Griffiths and Julian Sahasrabudhe. URL:https://dimag.ibs.re.kr/event/2023-05-02/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230425T163000 DTEND;TZID=Asia/Seoul:20230425T173000 DTSTAMP:20260506T084659 CREATED:20230315T025543Z LAST-MODIFIED:20240707T073739Z UID:6905-1682440200-1682443800@dimag.ibs.re.kr SUMMARY:Hyunwoo Lee (이현우)\, On perfect subdivision tilings DESCRIPTION:For a given graph $H$\, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of $G.$ Let $\delta_{sub}(n\, H)$ be the smallest integer $k$ such that any $n$-vertex graph $G$ with minimum degree at least $k$ has a perfect $H$-subdivision tiling. For every graph $H$\, we asymptotically determined the value of $\delta_{sub}(n\, H)$. More precisely\, for every graph $H$ with at least one edge\, there is a constant $1 < \xi^*(H)\leq 2$ such that $\delta_{sub}(n\, H) = \left(1 - \frac{1}{\xi^*(H)} + o(1) \right)n$ if $H$ has a bipartite subdivision with two parts having different parities. Otherwise\, the threshold depends on the parity of $n$. URL:https://dimag.ibs.re.kr/event/2023-04-25/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230411T163000 DTEND;TZID=Asia/Seoul:20230411T173000 DTSTAMP:20260506T084659 CREATED:20230220T150254Z LAST-MODIFIED:20240705T165050Z UID:6812-1681230600-1681234200@dimag.ibs.re.kr SUMMARY:James Davies\, Two structural results for pivot-minors DESCRIPTION:Pivot-minors can be thought of as a dense analogue of graph minors. We shall discuss pivot-minors and two recent results for proper pivot-minor-closed classes of graphs. In particular\, that for every graph H\, the class of graphs containing no H-pivot-minor is 𝜒-bounded\, and also satisfies the (strong) Erdős-Hajnal property. URL:https://dimag.ibs.re.kr/event/2023-04-11/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230404T163000 DTEND;TZID=Asia/Seoul:20230404T173000 DTSTAMP:20260506T084659 CREATED:20230116T010354Z LAST-MODIFIED:20240707T073814Z UID:6667-1680625800-1680629400@dimag.ibs.re.kr SUMMARY:István Tomon\, Configurations of boxes DESCRIPTION:Configurations of axis-parallel boxes in $\mathbb{R}^d$ are extensively studied in combinatorial geometry. Despite their perceived simplicity\, there are many problems involving their structure that are not well understood. I will talk about a construction that shows that their structure might be more complicated than people conjectured. URL:https://dimag.ibs.re.kr/event/2023-04-04/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230328T163000 DTEND;TZID=Asia/Seoul:20230328T173000 DTSTAMP:20260506T084659 CREATED:20230223T141945Z LAST-MODIFIED:20240705T165050Z UID:6831-1680021000-1680024600@dimag.ibs.re.kr SUMMARY:Tianchi Yang\, On the maximum number of edges in k-critical graphs DESCRIPTION:In this talk\, we will discuss the problem of determining the maximum number of edges in an n-vertex k-critical graph. A graph is considered k-critical if its chromatic number is k\, but any proper subgraph has a chromatic number less than k. The problem remains open for any integer k ≥ 4. Our presentation will showcase an improvement on previous results achieved by employing a combination of extremal graph theory and structural analysis. We will introduce a key lemma\, which may be of independent interest\, as it sheds light on the partial structure of dense k-critical graphs. This is joint work with Cong Luo and Jie Ma. URL:https://dimag.ibs.re.kr/event/2023-03-28/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230321T163000 DTEND;TZID=Asia/Seoul:20230321T173000 DTSTAMP:20260506T084659 CREATED:20230204T071556Z LAST-MODIFIED:20240705T170008Z UID:6762-1679416200-1679419800@dimag.ibs.re.kr SUMMARY:Younjin Kim (김연진)\, Problems on Extremal Combinatorics DESCRIPTION:Extremal Combinatorics studies the maximum or minimum size of finite objects (numbers\, sets\, graphs) satisfying certain properties. In this talk\, I introduce the conjectures I solved on Extremal Combinatorics\, and also introduce recent extremal problems. URL:https://dimag.ibs.re.kr/event/2023-03-21/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230314T163000 DTEND;TZID=Asia/Seoul:20230314T173000 DTSTAMP:20260506T084659 CREATED:20230120T011459Z LAST-MODIFIED:20240707T073956Z UID:6701-1678811400-1678815000@dimag.ibs.re.kr SUMMARY:Stijn Cambie\, Recent progress on the Union-closed conjecture and related DESCRIPTION:We give a summary on the work of the last months related to Frankl’s Union-Closed conjecture and its offsprings. The initial conjecture is stated as a theorem in extremal set theory; when a family F is union-closed (the union of sets of F is itself a set of $\mathcal F$)\, then $\mathcal F$ contains an (abundant) element that belongs to at least half of the sets. Meanwhile\, there are many related versions of the conjecture due to Frankl. For example\, graph theorists may prefer the equivalent statement that every bipartite graph has a vertex that belongs to no more than half of the maximal independent sets. While even proving the ε-Union-Closed Sets Conjecture was out of reach\, Poonen and Cui & Hu conjectured already stronger forms. \nAt the end of last year\, progress was made on many of these conjectures. Gilmer proved the ε-Union-Closed Sets Conjecture using an elegant entropy-based method which was sharpened by many others. Despite a sharp approximate form of the union-closed conjecture as stated by Chase and Lovett\, a further improvement was possible. In a different direction\, Kabela\, Polak and Teska constructed union-closed family sets with large sets and few abundant elements. \nThis talk will keep the audience up-to-date and give them insight in the main ideas. \nPeople who would like more details\, can join the Ecopro-reading session on the 14th of March (10 o’clock\, B332) as well. Here we go deeper in the core of the proofs and discuss possible directions for the full resolution. URL:https://dimag.ibs.re.kr/event/2023-03-14/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230307T163000 DTEND;TZID=Asia/Seoul:20230307T173000 DTSTAMP:20260506T084659 CREATED:20230111T063520Z LAST-MODIFIED:20240707T074009Z UID:6655-1678206600-1678210200@dimag.ibs.re.kr SUMMARY:Eunjin Oh (오은진)\, Parameterized algorithms for the planar disjoint paths problem DESCRIPTION:Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i\,t_i)_{i=1}^k$ of vertices\, the goal of the planar disjoint paths problem is to find a set $\mathcal P$ of $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all indices $i\in\{1\,\ldots\,k\}$. This problem has been studied extensively due to its numerous applications such as VLSI layout and circuit routing. However\, this problem is NP-complete even for grid graphs. This motivates the study of this problem from the viewpoint of parameterized algorithms. \nIn this talk\, I will present a $2^{O(k^2)}n$-time algorithm for the planar disjoint paths problem. This improves the two previously best-known algorithms: $2^{2^{O(k)}}n$-time algorithm [Discrete Applied Mathematics 1995] and $2^{O(k^2)}n^6$-time algorithm [STOC 2020]. \nThis is joint work with Kyungjin Cho and Seunghyeok Oh. URL:https://dimag.ibs.re.kr/event/2023-03-07/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230228T163000 DTEND;TZID=Asia/Seoul:20230228T173000 DTSTAMP:20260506T084659 CREATED:20230213T001557Z LAST-MODIFIED:20240707T074017Z UID:6782-1677601800-1677605400@dimag.ibs.re.kr SUMMARY:Maya Sankar\, The Turán Numbers of Homeomorphs DESCRIPTION:Let $X$ be a 2-dimensional simplicial complex. Denote by $\text{ex}_{\hom}(n\,X)$ the maximum number of 2-simplices in an $n$-vertex simplicial complex that has no sub-simplicial complex homeomorphic to $X$. The asymptotics of $\text{ex}_{\hom}(n\,X)$ have recently been determined for all surfaces $X$. I will discuss these results\, as well as ongoing work bounding $\text{ex}_{\hom}(n\,X)$ for arbitrary 2-dimensional simplicial complexes $X$. URL:https://dimag.ibs.re.kr/event/2023-02-28/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230221T163000 DTEND;TZID=Asia/Seoul:20230221T173000 DTSTAMP:20260506T084659 CREATED:20230110T061742Z LAST-MODIFIED:20240705T170041Z UID:6636-1676997000-1677000600@dimag.ibs.re.kr SUMMARY:Meike Hatzel\, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation DESCRIPTION:We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem\, given a directed graph $G$\, pairs of vertices (called terminals) $(s_1\,t_1)$\, $(s_2\,t_2)$\, and $(s_3\,t_3)$\, and an integer $k$\, asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths\, all $s_2t_2$-paths\, and all $s_3t_3$-paths. The parameterized complexity of this case has been open since Chitnis\, Cygan\, Hajiaghayi\, and Marx proved fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012\, and Pilipczuk and Wahlström proved the W[1]-hardness of the 4-terminal-pairs case at SODA 2016. \nOn the technical side\, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim\, Kratsch\, Pilipczuk\, Wahlström\, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width\, a recently introduced structural parameter [Bonnet\, Kim\, Thomassé\, Watrigant\, FOCS 2020]: By a recent characterization [Bonnet\, Giocanti\, Ossona de Mendez\, Simon\, Thomassé\, Toruńczyk\, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof\, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor\, a vertex corresponding to the “middle” box in the grid minor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced. URL:https://dimag.ibs.re.kr/event/2023-02-21/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230214T163000 DTEND;TZID=Asia/Seoul:20230214T173000 DTSTAMP:20260506T084659 CREATED:20221122T113208Z LAST-MODIFIED:20240705T171025Z UID:6504-1676392200-1676395800@dimag.ibs.re.kr SUMMARY:Raphael Steiner\, Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs DESCRIPTION:Hadwiger’s famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd [Bull. London Math. Soc. 29\, (1997)\, pp. 139-144] conjectured the following strengthening of Hadwiger’s conjecture: If G is a t-chromatic graph and S⊆V(G) takes all colors in every t-coloring of G\, then G contains a $K_t$-minor rooted at S. We prove this conjecture in the first open case of t=4. Notably\, our result also directly implies a stronger version of Hadwiger’s conjecture for 5-chromatic graphs as follows: Every 5-chromatic graph contains a $K_5$-minor with a singleton branch-set. In fact\, in a 5-vertex-critical graph we may specify the singleton branch-set to be any vertex of the graph. Joint work with Anders Martinsson (ETH). URL:https://dimag.ibs.re.kr/event/2023-02-14/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230131T163000 DTEND;TZID=Asia/Seoul:20230131T173000 DTSTAMP:20260506T084659 CREATED:20230110T062223Z LAST-MODIFIED:20240707T074122Z UID:6639-1675182600-1675186200@dimag.ibs.re.kr SUMMARY:Abhishek Methuku\, A proof of the Erdős–Faber–Lovász conjecture DESCRIPTION:The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk\, I will sketch a proof of this conjecture for every large n. Joint work with D. Kang\, T. Kelly\, D. Kühn and D. Osthus. URL:https://dimag.ibs.re.kr/event/2023-01-31/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230117T163000 DTEND;TZID=Asia/Seoul:20230117T173000 DTSTAMP:20260506T084659 CREATED:20221213T152329Z LAST-MODIFIED:20240707T074134Z UID:6556-1673973000-1673976600@dimag.ibs.re.kr SUMMARY:Noleen Köhler\, Twin-Width VIII: Delineation and Win-Wins DESCRIPTION:We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated by twin-width (or simply\, delineated) if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$\, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for a class $\mathcal C$ implies that tractable FO model checking on $\mathcal C$ is perfectly understood: On hereditary closures of subclasses $\mathcal D$ of $\mathcal C$\, FO model checking on $\mathcal D$ is fixed-parameter tractable (FPT) exactly when $\mathcal D$ has bounded twin-width. Ordered graphs [BGOdMSTT\, STOC ’22] and permutation graphs [BKTW\, JACM ’22] are effectively delineated\, while subcubic graphs are not. On the one hand\, we prove that interval graphs\, and even\, rooted directed path graphs are delineated. On the other hand\, we observe or show that segment graphs\, directed path graphs (with arbitrarily many roots)\, and visibility graphs of simple polygons are not delineated. \nIn an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not)\, we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW\, SODA ’21]. We show that $K_{t\,t}$-free segment graphs\, and axis-parallel $H_t$-free unit segment graphs have bounded twin-width\, where $H_t$ is the half-graph or ladder of height $t$. In contrast\, axis-parallel $H_4$-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. \nMore broadly\, we explore which structures (large bicliques\, half-graphs\, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results\, combined with the FPT algorithm for first-order model checking on graphs given with $O(1)$-sequences [BKTW\, JACM ’22]\, give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If $p$ is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C\, then $p(G) \ge k$ can be decided in FPT time $f(k)\cdot |V (G)|O(1)$. For instance\, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains\, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width. \nJoint work with Édouard Bonnet\, Dibyayan Chakraborty\, Eun Jung Kim\, Raul Lopes and Stéphan Thomassé. URL:https://dimag.ibs.re.kr/event/2023-01-17/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230110T163000 DTEND;TZID=Asia/Seoul:20230110T173000 DTSTAMP:20260506T084659 CREATED:20221123T222545Z LAST-MODIFIED:20240705T171022Z UID:6518-1673368200-1673371800@dimag.ibs.re.kr SUMMARY:Mamadou Moustapha Kanté\, MSOL-Definable decompositions DESCRIPTION:I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step\, I will discuss relations with decompositions of graphs/matroids and why their MSOL-definability is related to understanding recognisable sets. I will finally explain  how to define in MSOL branch-decompositions for finitely representable matroids of bounded path-width. This is joint work with Rutger Campbell\, Bruno Guillon\, Eun Jung Kim\, and Sang-il Oum. URL:https://dimag.ibs.re.kr/event/2023-01-10/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230103T163000 DTEND;TZID=Asia/Seoul:20230103T173000 DTSTAMP:20260506T084659 CREATED:20221010T054006Z LAST-MODIFIED:20240707T074146Z UID:6280-1672763400-1672767000@dimag.ibs.re.kr SUMMARY:Youngho Yoo (유영호)\, Approximating TSP walks in subcubic graphs DESCRIPTION:The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous $\frac{4}{3}$-integrality-gap conjecture on the “subtour elimination” linear programming relaxation of the Metric TSP. \nWe prove that every simple 2-connected subcubic graph on $n$ vertices with $n_2$ vertices of degree 2 has a TSP walk of length at most $\frac{5n+n_2}{4}-1$\, confirming a conjecture of Dvořák\, Král’\, and Mohar. This bound is best possible and we characterize the extremal subcubic examples meeting this bound. We also give a quadratic time combinatorial algorithm to find such a TSP walk. In particular\, we obtain a $\frac{5}{4}$-approximation algorithm for the Graphic TSP on cubic graphs. Joint work with Michael Wigal and Xingxing Yu. URL:https://dimag.ibs.re.kr/event/2023-01-03/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221228T163000 DTEND;TZID=Asia/Seoul:20221228T173000 DTSTAMP:20260506T084659 CREATED:20221221T082326Z LAST-MODIFIED:20240705T170042Z UID:6590-1672245000-1672248600@dimag.ibs.re.kr SUMMARY:Stijn Cambie\, The 69-conjecture and more surprises on the number of independent sets DESCRIPTION:Various types of independent sets have been studied for decades. As an example\, the minimum number of maximal independent sets in a connected graph of given order is easy to determine (hint; the answer is written in the stars). When considering this question for twin-free graphs\, it becomes less trivial and one discovers some surprising behaviour. The minimum number of maximal independent sets turns out to be; \n\nlogarithmic in the number of vertices for arbitrary graphs\,\nlinear for bipartite graphs\nand exponential for trees.\n\nFinally\, we also have a sneak peek on the 69-conjecture\, part of an unpublished work on an inverse problem on the number of independent sets. \nIn this talk\, we will focus on the basic concepts\, the intuition behind the statements and sketch some proof ideas. \nThe talk is based on joint work with Stephan Wagner\, with the main chunk being available at arXiv:2211.04357. URL:https://dimag.ibs.re.kr/event/2022-12-28/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221206T163000 DTEND;TZID=Asia/Seoul:20221206T173000 DTSTAMP:20260506T084659 CREATED:20220908T152618Z LAST-MODIFIED:20240707T074218Z UID:6153-1670344200-1670347800@dimag.ibs.re.kr SUMMARY:Giannos Stamoulis\, Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes DESCRIPTION:The disjoint paths logic\, FOL+DP\,  is an extension of First Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1\,y_1\,\ldots\,x_k\,y_k)\,$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i\,$ for $i\in \{1\,\ldots\, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every minor-closed graph class\, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP\, namely the scattered disjoint paths logic\, FOL+SDP\, where we further consider the atomic predicate $\mathsf{s-sdp}_k(x_1\,y_1\,\ldots\,x_k\,y_k)\,$ demanding that the disjoint paths are within distance bigger than some fixed value $s$. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus.\nJoint work with Petr A. Golovach and Dimitrios M. Thilikos. URL:https://dimag.ibs.re.kr/event/2022-12-06/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221122T163000 DTEND;TZID=Asia/Seoul:20221122T173000 DTSTAMP:20260506T084659 CREATED:20221018T043943Z LAST-MODIFIED:20240707T074455Z UID:6362-1669134600-1669138200@dimag.ibs.re.kr SUMMARY:Seonghyuk Im (임성혁)\, A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems DESCRIPTION:A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices.  A linear $3$-graph is called a Steiner triple system if each pair of two distinct vertices belong to a unique edge. \nA simple greedy algorithm shows that every $n$-vertex Steiner triple system $G$ contains all hypertrees $T$ of order at most $\frac{n+3}{2}$. On the other hand\, it is not immediately clear whether one can always find larger hypertrees in $G$. In 2011\, Goodall and de Mier proved that a Steiner triple system $G$ contains at least one spanning tree. However\, one cannot expect the Steiner triple system to contain all possible spanning trees\, as there are many Steiner triple systems that avoid numerous spanning trees as subgraphs. Hence it is natural to wonder how much one can improve the bound from the greedy algorithm. \nIndeed\, Elliott and Rödl conjectured that an $n$-vertex Steiner triple system $G$ contains all hypertrees of order at most $(1-o(1))n$. We prove the conjecture by Elliott and Rödl. \nThis is joint work with Jaehoon Kim\, Joonkyung Lee\, and Abhishek Methuku. URL:https://dimag.ibs.re.kr/event/2022-11-22/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221115T163000 DTEND;TZID=Asia/Seoul:20221115T173000 DTSTAMP:20260506T084659 CREATED:20221011T041240Z LAST-MODIFIED:20240705T171137Z UID:6283-1668529800-1668533400@dimag.ibs.re.kr SUMMARY:Sebastian Wiederrecht\, Excluding single-crossing matching minors in bipartite graphs DESCRIPTION:By a seminal result of Valiant\, computing the permanent of (0\, 1)-matrices is\, in general\, #P-hard. In 1913 Pólya asked for which (0\, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975\, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding $K_{3\,3}$ as a matching minor. This was turned into a polynomial time algorithm by McCuaig\, Robertson\, Seymour\, and Thomas in 1999. However\, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K3\,3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0\, 1)-matrices can be computed efficiently. \nIn this paper we unify the two results above into a single\, more general result in the style of the celebrated structure theorem for single-crossing minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and $K_{3\,3}$ which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover\, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude $K_{5\,5}$ as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem\, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth. \nThis is joint work with Archontia Giannopoulou and Dimitrios Thilikos. URL:https://dimag.ibs.re.kr/event/2022-11-15/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221108T163000 DTEND;TZID=Asia/Seoul:20221108T173000 DTSTAMP:20260506T084659 CREATED:20221018T044028Z LAST-MODIFIED:20240707T074529Z UID:6364-1667925000-1667928600@dimag.ibs.re.kr SUMMARY:Jungho Ahn (안정호)\, Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes DESCRIPTION:Let $\mathcal{F}$ be a family of graphs\, and let $p$ and $r$ be nonnegative integers.\nThe $(p\,r\,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$\, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^p\setminus N_G^r[D]$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$\, where $G^p$ is the $p$-th power of $G$ and $N^r_G[D]$ is the set of all vertices in $G$ at distance at most $r$ from $D$ in $G$. The $(p\,r\,\mathcal{F})$-Packing problem asks whether for a graph $G$ and an integer $k$\, $G^p$ has $k$ induced subgraphs $H_1\,\ldots\,H_k$ such that each $H_i$ is isomorphic to a graph in $\mathcal{F}$\, and for distinct $i\,j\in \{1\, \ldots\, k\}$\, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. The $(p\,r\,\mathcal{F})$-Covering problem generalizes Distance-$r$ Dominating Set and Distance-$r$ Vertex Cover\, and the $(p\,r\,\mathcal{F})$-Packing problem generalizes Distance-$r$ Independent Set and Distance-$r$ Matching. By taking $(p’\,r’\,\mathcal{F}’)=(pt\, rt\, \mathcal{F})$\, we may formulate the $(p\,r\,\mathcal{F})$-Covering and $(p\, r\, \mathcal{F})$-Packing problems on the $t$-th power of a graph. Moreover\, $(1\,0\,\mathcal{F})$-Covering is the $\mathcal{F}$-Free Vertex Deletion problem\, and $(1\,0\,\mathcal{F})$-Packing is the Induced-$\mathcal{F}$-Packing problem. \nWe show that for every fixed nonnegative integers $p\,r$ and every fixed nonempty finite family $\mathcal{F}$ of connected graphs\, the $(p\,r\,\mathcal{F})$-Covering problem with $p\leq2r+1$ and the $(p\,r\,\mathcal{F})$-Packing problem with $p\leq2\lfloor r/2\rfloor+1$ admit almost linear kernels on every nowhere dense class of graphs\, and admit linear kernels on every class of graphs with bounded expansion\, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries\, we prove that Distance-$r$ Vertex Cover\, Distance-$r$ Matching\, $\mathcal{F}$-Free Vertex Deletion\, and Induced-$\mathcal{F}$-Packing for any fixed finite family $\mathcal{F}$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for Distance-$r$ Dominating Set by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017)\, and the result for Distance-$r$ Independent Set by Pilipczuk and Siebertz (EJC 2021). \nThis is joint work with Jinha Kim and O-joung Kwon. URL:https://dimag.ibs.re.kr/event/2022-11-08/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221018T163000 DTEND;TZID=Asia/Seoul:20221018T173000 DTSTAMP:20260506T084659 CREATED:20220824T133830Z LAST-MODIFIED:20240705T171142Z UID:6071-1666110600-1666114200@dimag.ibs.re.kr SUMMARY:Florent Koechlin\, Uniform random expressions lack expressivity DESCRIPTION:In computer science\, random expressions are commonly used to analyze algorithms\, either to study their average complexity\, or to generate benchmarks to test them experimentally. In general\, these approaches only consider the expressions as purely syntactic trees\, and completely ignore their semantics — i.e. the mathematical object represented by the expression. \nHowever\, two different expressions can be equivalent (for example “0*(x+y)” and “0” represent the same expression\, the null expression). Can these redundancies question the relevance of the analyses and tests that do not take into account the semantics of the expressions? \nI will present how the uniform distribution over syntactic expression becomes completely degenerate when we start taking into account their semantics\, in a very simple but common case where there is an absorbing element. If time permits it\, I will briefly explain why the BST distribution offers more hope. \nThis is a joint work with Cyril Nicaud and Pablo Rotondo. URL:https://dimag.ibs.re.kr/event/2022-10-18/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221011T163000 DTEND;TZID=Asia/Seoul:20221011T173000 DTSTAMP:20260506T084659 CREATED:20220824T132239Z LAST-MODIFIED:20240707T074556Z UID:6067-1665505800-1665509400@dimag.ibs.re.kr SUMMARY:Nika Salia\, Exact results for generalized extremal problems forbidding an even cycle DESCRIPTION:We determine the maximum number of copies of $K_{s\,s}$ in a $C_{2s+2}$-free $n$-vertex graph for all integers $s \ge 2$ and sufficiently large $n$. Moreover\, for $s\in\{2\,3\}$ and any integer $n$ we obtain the maximum number of cycles of length $2s$ in an $n$-vertex $C_{2s+2}$-free bipartite graph. \nThis is joint work with Ervin Győri (Renyi Institute)\, Zhen He (Tsinghua University)\, Zequn Lv (Tsinghua University)\, Casey Tompkins (Renyi Institute)\, Kitti Varga (Technical University of Budapest BME)\, and Xiutao Zhu (Nanjing University). URL:https://dimag.ibs.re.kr/event/2022-10-11/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221004T163000 DTEND;TZID=Asia/Seoul:20221004T173000 DTSTAMP:20260506T084659 CREATED:20220825T224353Z LAST-MODIFIED:20240707T074613Z UID:6077-1664901000-1664904600@dimag.ibs.re.kr SUMMARY:Zixiang Xu (徐子翔)\, On the degenerate Turán problems DESCRIPTION:For a graph $F$\, the Turán number is the maximum number of edges in an $n$-vertex simple graph not containing $F$. The celebrated Erdős-Stone-Simonovits Theorem gives that \[ \text{ex}(n\,F)=\bigg(1-\frac{1}{\chi(F)-1}+o(1)\bigg)\binom{n}{2}\,\] where $\chi(F)$ is the chromatic number of $H$. This theorem asymptotically solves the problem when $\chi(F)\geqslant 3$. In case of bipartite graphs $F$\, not even the order of magnitude is known in general. In this talk\, I will introduce some recent progress on Turán numbers of bipartite graphs and related generalizations and discuss several methods developed in recent years. Finally\, I will introduce some interesting open problems on this topic. URL:https://dimag.ibs.re.kr/event/2022-10-04/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220927T163000 DTEND;TZID=Asia/Seoul:20220927T173000 DTSTAMP:20260506T084659 CREATED:20220825T021718Z LAST-MODIFIED:20240707T074701Z UID:6074-1664296200-1664299800@dimag.ibs.re.kr SUMMARY:Alexander Clifton\, Ramsey Theory for Diffsequences DESCRIPTION:Van der Waerden’s theorem states that any coloring of $\mathbb{N}$ with a finite number of colors will contain arbitrarily long monochromatic arithmetic progressions. This motivates the definition of the van der Waerden number $W(r\,k)$ which is the smallest $n$ such that any $r$-coloring of $\{1\,2\,\cdots\,n\}$ guarantees the presence of a monochromatic arithmetic progression of length $k$. \nIt is natural to ask what other arithmetic structures exhibit van der Waerden-type results. One notion\, introduced by Landman and Robertson\, is that of a $D$-diffsequence\, which is an increasing sequence $a_12k$ and every intersecting family $\mathcal F\subseteq [n]^{(k)}$\, there is some $i\in[n]$ such that $\vert \partial \mathcal F(i)\vert\geq \vert\mathcal F(i)\vert$\, where $\mathcal F(i)=\{F\setminus i:i\in F\in\mathcal F\}$ is the link of $\mathcal F$ at $i$. \nHere\, we prove this conjecture in a very strong form for $n> \binom{k+1}{2}$. \nIn particular\, our result implies that for any $j\in[k]$\, there is a $j$-set $\{a_1\,\dots\,a_j\}\in[n]^{(j)}$ such that \[ \vert \partial \mathcal F(a_1\,\dots\,a_j)\vert\geq \vert\mathcal F(a_1\,\dots\,a_j)\vert.\]A similar statement is also obtained for cross-intersecting families. URL:https://dimag.ibs.re.kr/event/2022-09-06/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220830T163000 DTEND;TZID=Asia/Seoul:20220830T173000 DTSTAMP:20260506T084659 CREATED:20220830T073000Z LAST-MODIFIED:20240707T075520Z UID:6018-1661877000-1661880600@dimag.ibs.re.kr SUMMARY:Jun Gao\, Number of (k-1)-cliques in k-critical graph DESCRIPTION:We prove that for $n>k\geq 3$\, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number\, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai. \nThis is joint work with Jie Ma. URL:https://dimag.ibs.re.kr/event/2022-08-30/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220823T163000 DTEND;TZID=Asia/Seoul:20220823T173000 DTSTAMP:20260506T084659 CREATED:20220823T073000Z LAST-MODIFIED:20240705T171142Z UID:5971-1661272200-1661275800@dimag.ibs.re.kr SUMMARY:Raul Lopes\, Temporal Menger and related problems DESCRIPTION:A temporal graph is a graph whose edges are available only at specific times. In this scenario\, the only valid walks are the ones traversing adjacent edges respecting their availability\, i.e. sequence of adjacent edges whose appearing times are non-decreasing. \nGiven a graph G and vertices s and t of G\, Menger’s Theorem states that the maximum number of (internally) vertex disjoint s\,t-paths is equal to the minimum size of a subset X for which G-X contains no s\,t-path. This is a classical result in Graph Theory\, taught in most basic Graph Theory courses\, and it holds also when G is directed and when edge disjoint paths and edge cuts are considered instead. A direct translation of Menger’s Theorem to the temporal context has been known not to hold since an example was shown in the seminal paper by Kempe\, Kleinberg and Kumar (STOC’00). In this talk\, an overview of possible temporal versions of Menger’s Theorem will be discussed\, as well as the complexity of the related problems. URL:https://dimag.ibs.re.kr/event/2022-08-23/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT END:VCALENDAR