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:20210101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230215T163000 DTEND;TZID=Asia/Seoul:20230215T173000 DTSTAMP:20260417T063247 CREATED:20230103T235641Z LAST-MODIFIED:20240705T170041Z UID:6623-1676478600-1676482200@dimag.ibs.re.kr SUMMARY:Robert Hickingbotham\, Treewidth\, Circle Graphs and Circular Drawings DESCRIPTION:A circle graph is an intersection graph of a set of chords of a circle. In this talk\, I will describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects’. Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs\, and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. I will also discuss applications of our results to the treewidth of graphs $G$ that have a circular drawing whose crossing graph is well-behaved in some way. In this setting\, our results show that if the crossing graph is $K_t$-minor-free\, then $G$ has treewidth at most $12t-23$ and has no $K_{2\,4t}$-topological minor. On the other hand\, I’ll present a construction of graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are $2$-degenerate. This is joint work with Freddie Illingworth\, Bojan Mohar\, and David R. Wood URL:https://dimag.ibs.re.kr/event/2023-02-15/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230214T163000 DTEND;TZID=Asia/Seoul:20230214T173000 DTSTAMP:20260417T063247 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:20230201T163000 DTEND;TZID=Asia/Seoul:20230201T173000 DTSTAMP:20260417T063247 CREATED:20230115T151551Z LAST-MODIFIED:20240705T170041Z UID:6664-1675269000-1675272600@dimag.ibs.re.kr SUMMARY:Benjamin Bergougnoux\, Tight Lower Bounds for Problems Parameterized by Rank-width DESCRIPTION:We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$\, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by Bui-Xuan\, Telle\, and Vatshelle [Discret. Appl. Math.\, 2010] and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math.\, 2021]. We also show that the known $2^{O(k^2)} n^{O(1)}$ time algorithms for Weighted Dominating Set\, Maximum Induced Matching and Feedback Vertex Set parameterized by rank-width $k$ are optimal assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that do not follow directly from lower bounds for $n$-vertex graphs. \nThis is a joint work with Tuukka Korhonen and Jesper Nederlof.\nAccepted to STACS 2023 and available on arXiv https://arxiv.org/abs/2210.02117 URL:https://dimag.ibs.re.kr/event/2023-02-01/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230131T163000 DTEND;TZID=Asia/Seoul:20230131T173000 DTSTAMP:20260417T063247 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:20230125T163000 DTEND;TZID=Asia/Seoul:20230125T173000 DTSTAMP:20260417T063247 CREATED:20221109T131052Z LAST-MODIFIED:20240705T171112Z UID:6458-1674664200-1674667800@dimag.ibs.re.kr SUMMARY:Jan Hladký\, Invitation to graphons DESCRIPTION:The first course in graph theory usually covers concepts such as matchings\, independent sets\, colourings\, and forbidden subgraphs. Around 2004\, Borgs\, Chayes\, Lovász\, Sós\, Szegedy\, and Vestergombi introduced a very fruitful limit perspective on graphs. The central objects of this theory\, so-called graphons\, are suitable measurable counterparts to graphs. In the talk\, I will outline the syllabus of a hypothetical first course in graphon theory\, in particular introducing versions of all the aforementioned concepts in the graphon setting. Based on work with Doležal\, Hu\, Máthé\, Piguet\, Rocha. URL:https://dimag.ibs.re.kr/event/2023-01-25/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230119T100000 DTEND;TZID=Asia/Seoul:20230119T110000 DTSTAMP:20260417T063247 CREATED:20230103T142421Z LAST-MODIFIED:20240705T170041Z UID:6619-1674122400-1674126000@dimag.ibs.re.kr SUMMARY:Pedro Montealegre\, A Meta-Theorem for Distributed Certification DESCRIPTION:Distributed certification\, whether it be proof-labeling schemes\, locally checkable proofs\, etc.\, deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle\, and the processes are in charge of verifying these certificates\, so that two properties are satisfied: completeness\, i.e.\, for every legal instance\, there is a certificate assignment leading all processes to accept\, and soundness\, i.e.\, for every illegal instance\, and for every certificate assignment\, at least one process rejects. The verification of the certificates must be fast\, and the certificates themselves must be small. \nA large quantity of results have been produced in this framework\, each aiming at designing a distributed certification mechanism for specific boolean predicates. In this talk\, I will present a “meta-theorem”\, applying to many boolean predicates at once. Specifically\, I will show that\, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs\, there exists a distributed certification mechanism using certificates on $O(log^2 n)$ bits in n-node graphs of bounded treewidth\, with a verification protocol involving a single round of communication between neighbors. URL:https://dimag.ibs.re.kr/event/2023-01-19/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20230117T163000 DTEND;TZID=Asia/Seoul:20230117T173000 DTSTAMP:20260417T063247 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:20260417T063247 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:20260417T063247 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:20260417T063247 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:20221215T100000 DTEND;TZID=Asia/Seoul:20221215T110000 DTSTAMP:20260417T063247 CREATED:20221109T130647Z LAST-MODIFIED:20240707T074155Z UID:6454-1671098400-1671102000@dimag.ibs.re.kr SUMMARY:Maya Sankar\, Homotopy and the Homomorphism Threshold of Odd Cycles DESCRIPTION:Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs\, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently\, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that are themselves $C_{2r+1}$-free. Specifically\, we construct a family of dense $C_{2r+1}$-free graphs with no $C_{2r+1}$-free homomorphic image of bounded size. This provides the first nontrivial lower bound on the homomorphism threshold of longer odd cycles and answers a question of Ebsen and Schacht. \nOur proof relies on a graph-theoretic analogue of homotopy equivalence\, which allows us to analyze the relative placement of odd closed walks in a graph. This notion has surprising connections to the neighborhood complex\, and opens many further interesting questions. URL:https://dimag.ibs.re.kr/event/2022-12-15/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221206T163000 DTEND;TZID=Asia/Seoul:20221206T173000 DTSTAMP:20260417T063247 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:20221201T100000 DTEND;TZID=Asia/Seoul:20221201T110000 DTSTAMP:20260417T063247 CREATED:20221016T112526Z LAST-MODIFIED:20240707T074433Z UID:6354-1669888800-1669892400@dimag.ibs.re.kr SUMMARY:Cosmin Pohoata\, Convex polytopes from fewer points DESCRIPTION:Finding the smallest integer $N=ES_d(n)$ such that in every configuration of $N$ points in $\mathbb{R}^d$ in general position\, there exist $n$ points in convex position is one of the most classical problems in extremal combinatorics\, known as the Erdős-Szekeres problem. In 1935\, Erdős and Szekeres famously conjectured that $ES_2(n)=2^{n−2}+1$ holds\, which was nearly settled by Suk in 2016\, who showed that $ES_2(n)≤2^{n+o(n)}$. We discuss a recent proof that $ES_d(n)=2^{o(n)}$ holds for all $d≥3$. Joint work with Dmitrii Zakharov. URL:https://dimag.ibs.re.kr/event/2022-12-01/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;VALUE=DATE:20221128 DTEND;VALUE=DATE:20221130 DTSTAMP:20260417T063247 CREATED:20221118T114614Z LAST-MODIFIED:20240705T171025Z UID:6495-1669593600-1669766399@dimag.ibs.re.kr SUMMARY:The 2nd Workshop on Developments in Combinatorics DESCRIPTION:Official website (with the abstract)\nOnline workshop “Developments in Combinatorics” \n \n\nInvited Speakers\nNov. 28 Monday\nJie Han\, Beijing Institute of Technology\n15:30 Seoul\, 14:30 Beijing\, 06:30 UK\, 07:30 EU \nJoonkyung Lee (이준경)\, Hanyang University\n16:10 Seoul\, 15:10 Beijing\, 07:10 UK\, 08:10 EU \nLior Gishboliner\, ETH Zürich\n16:50 Seoul\, 15:50 Beijing\, 07:50 UK\, 08:50 EU \nAlex Scott\, University of Oxford\n17:40 Seoul\, 16:40 Beijing\, 08:40 UK\, 09:40 EU \nDongyeap Kang (강동엽)\, University of Birmingham\n18:20 Seoul\, 17:20 Beijing\, 09:20 UK\, 10:20 EU \nNov. 29 Tuesday\nChong Shangguan\, Shandong University\n15:30 Seoul\, 14:30 Beijing\, 06:30 UK\, 07:30 EU \nZdeněk Dvořák\, Charles University\n16:10 Seoul\, 15:10 Beijing\, 07:10 UK\, 08:10 EU \nAndrzej Grzesik\, Jagiellonian University\n16:50 Seoul\, 15:50 Beijing\, 07:50 UK\, 08:50 EU \nImre Leader\, University of Cambridge\n17:40 Seoul\, 16:40 Beijing\, 08:40 UK\, 09:40 EU \nJozef Skokan\, The London School of Ecnomics and Political Science\n18:20 Seoul\, 17:20 Beijing\, 09:20 UK\, 10:20 EU \nOrganizers\n\nHong Liu\nGuanghui Wang\nBingyu Luan\n\nSponsors\n\nIBS Extremal Combinatorics and Probability Group\nShandong University\n\n  URL:https://dimag.ibs.re.kr/event/2022-11-28/ LOCATION:Zoom ID: 346 934 4087 (202209) CATEGORIES:Workshops and Conferences ATTACH;FMTTYPE=image/jpeg:https://dimag.ibs.re.kr/cms/wp-content/uploads/2022/11/ecopro-sdu-workshop2022-scaled-1.jpeg END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221122T163000 DTEND;TZID=Asia/Seoul:20221122T173000 DTSTAMP:20260417T063247 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:20221117T100000 DTEND;TZID=Asia/Seoul:20221117T110000 DTSTAMP:20260417T063247 CREATED:20221109T131844Z LAST-MODIFIED:20240707T074503Z UID:6462-1668679200-1668682800@dimag.ibs.re.kr SUMMARY:Chong Shangguan (上官冲)\, On the sparse hypergraph problem of Brown\, Erdős and Sós DESCRIPTION:For fixed integers $r\ge 3\, e\ge 3$\, and $v\ge r+1$\, let $f_r(n\,v\,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ distinct edges contains at least $v+1$ vertices. In 1973\, Brown\, Erdős and Sós initiated the study of the function $f_r(n\,v\,e)$ and they proved that $\Omega(n^{\frac{er-v}{e-1}})=f_r(n\,v\,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil})$. We will survey the state-of-art results about the study of $f_r(n\,er-(e-1)k+1\,e)$ and $f_r(n\,er-(e-1)k\,e)$\, where $r>k\ge 2$ and $e\ge 3$. Although these two functions have been extensively studied\, many interesting questions remain open. URL:https://dimag.ibs.re.kr/event/2022-11-17/ LOCATION:Zoom ID: 224 221 2686 (ibsecopro) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221115T163000 DTEND;TZID=Asia/Seoul:20221115T173000 DTSTAMP:20260417T063247 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:20221109T163000 DTEND;TZID=Asia/Seoul:20221109T173000 DTSTAMP:20260417T063247 CREATED:20221015T061909Z LAST-MODIFIED:20240705T171133Z UID:6342-1668011400-1668015000@dimag.ibs.re.kr SUMMARY:Hugo Jacob\, On the parameterized complexity of computing tree-partitions DESCRIPTION:Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender\, Cornelissen\, and van der Wegen\, we consider the parameterized problem of computing a decomposition. We prove that computing an optimal tree-partition is XALP-complete\, which is likely to exclude FPT algorithms. However\, we prove that computing a tree-partition of approximate width is tractable using a relatively simple sketch. This is sufficient to remove the requirement of having a given tree-partition for FPT algorithms. Our simple sketch can be adapted for several regimes within polynomial time and FPT time. Furthermore\, we adapt some simple structural results about the tree-partition-width of subdivisions\, and use them to compare tree-cut width and tree-partition-width. \nBased on joint work with Hans Bodlaender and Carla Groenland. URL:https://dimag.ibs.re.kr/event/2022-11-09/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221108T163000 DTEND;TZID=Asia/Seoul:20221108T173000 DTSTAMP:20260417T063247 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:20221027T161500 DTEND;TZID=Asia/Seoul:20221027T171500 DTSTAMP:20260417T063247 CREATED:20221012T134118Z LAST-MODIFIED:20240705T171136Z UID:6311-1666887300-1666890900@dimag.ibs.re.kr SUMMARY:Dabeen Lee (이다빈)\, Non-smooth and Hölder-smooth submodular optimization DESCRIPTION:We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an [(1−1/e)OPT−ϵ] guarantee when the function is monotone and Hölder-smooth\, meaning that it admits a Hölder-continuous gradient. For functions that are non-differentiable or non-smooth\, we propose a variant of the mirror-prox algorithm that attains an [(1/2)OPT−ϵ] guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular\, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least (1/2)OPT−ϵ. For distributionally robust maximization under Wasserstein ambiguity\, we deduce and work over a submodular-convex maximin reformulation whose objective function is Hölder-smooth\, for which we may apply both the continuous greedy method and the mirror-prox method.\nJoint work with Duksang Lee and Nam Ho-Ngyuen. URL:https://dimag.ibs.re.kr/event/2022-10-27/ LOCATION:Room 1501\, Bldg. E6-1\, KAIST CATEGORIES:Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221018T163000 DTEND;TZID=Asia/Seoul:20221018T173000 DTSTAMP:20260417T063247 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:20221013T161500 DTEND;TZID=Asia/Seoul:20221013T171500 DTSTAMP:20260417T063247 CREATED:20221006T054719Z LAST-MODIFIED:20240705T171138Z UID:6264-1665677700-1665681300@dimag.ibs.re.kr SUMMARY:Xavier Goaoc\, Order types and their symmetries DESCRIPTION:Order types are a combinatorial classification of finite point sets used in discrete and computational geometry. This talk will give an introduction to these objects and their analogue for the projective plane\, with an emphasis on their symmetry groups. \nThis is joint work with Emo Welzl. URL:https://dimag.ibs.re.kr/event/2022-10-13/ LOCATION:Room 1501\, Bldg. E6-1\, KAIST CATEGORIES:Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221011T163000 DTEND;TZID=Asia/Seoul:20221011T173000 DTSTAMP:20260417T063247 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:20221006T100000 DTEND;TZID=Asia/Seoul:20221006T110000 DTSTAMP:20260417T063247 CREATED:20221002T082503Z LAST-MODIFIED:20240705T171138Z UID:6236-1665050400-1665054000@dimag.ibs.re.kr SUMMARY:Konstantin Tikhomirov\, A remark on the Ramsey number of the hypercube DESCRIPTION:A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper\, we show that $r(Q_n)=O(2^{2n−cn})$ for a universal constant $c>0$\, improving upon the previous best-known bound $r(Q_n)=O(2^{2n})$\, due to Conlon\, Fox\, and Sudakov. URL:https://dimag.ibs.re.kr/event/2022-10-06/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221004T163000 DTEND;TZID=Asia/Seoul:20221004T173000 DTSTAMP:20260417T063247 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:20220929T100000 DTEND;TZID=Asia/Seoul:20220929T110000 DTSTAMP:20260417T063247 CREATED:20220904T134540Z LAST-MODIFIED:20240707T074627Z UID:6134-1664445600-1664449200@dimag.ibs.re.kr SUMMARY:Santiago Guzmán-Pro\, Local expressions of graphs classes DESCRIPTION:A common technique to characterize hereditary graph classes is to exhibit their minimal obstructions. Sometimes\, the set of minimal obstructions might be infinite\, or too complicated to describe. For instance\, for any $k\ge 3$\, the set of minimal obstructions of the class of $k$-colourable graphs is yet unknown. Nonetheless\, the Roy-Gallai-Hasse-Vitaver Theorem asserts that a graph $G$ is $k$-colourable if and only if it admits an orientation with no directed walk on $k+1$ vertices. We say that a class of graphs $\mathcal{P}$ is expressible by forbidden orientations if there is a finite set $F$ of oriented graphs such that $\mathcal{P}$ is the class of graphs that admit an $F$-free orientation. We are interested in understanding which graph classes are expressible by forbidden orientations (and why). In this talk\, we present some limitations of this expression system. In particular\, we show that the class of even-hole free graphs is not expressible by forbidden orientations. \nThroughout the talk\, we also mention some other related expression systems. In particular\, each of these systems provides a certification method to the $\mathcal{P}$-decision problem; i.e.\, decide if an input graph belongs to the class $\mathcal{P}$. We conclude this talk by proposing a general framework to talk about these expression systems. This framework allows us to formalize the question\, what can be certified this way? \nBased on a joint work with César Hernández-Cruz. URL:https://dimag.ibs.re.kr/event/2022-09-29/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220927T163000 DTEND;TZID=Asia/Seoul:20220927T173000 DTSTAMP:20260417T063247 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_1