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:20230110T163000 DTEND;TZID=Asia/Seoul:20230110T173000 DTSTAMP:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20260417T071513 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:20220831T163000 DTEND;TZID=Asia/Seoul:20220831T173000 DTSTAMP:20260417T071513 CREATED:20220816T233139Z LAST-MODIFIED:20240707T075512Z UID:6033-1661963400-1661967000@dimag.ibs.re.kr SUMMARY:Raphael Steiner\, Congruence-constrained subdivisions in digraphs DESCRIPTION:I will present the short proof from [1] that for every digraph F and every assignment of pairs of integers $(r_e\,q_e)_{e\in A(F)}$ to its arcs\, there exists an integer $N$ such that every digraph D with dichromatic number at least $N$ contains a subdivision of $F$ in which $e$ is subdivided into a directed path of length congruent to $r_e$ modulo $q_e$ for every $e \in  A(F)$. This generalizes to the directed setting the analogous result by Thomassen for undirected graphs and at the same time yields a novel proof of his result. I will also talk about how a hypergraph coloring result from [2] may help to obtain good bounds on $N$ in the special case when $F$ is subcubic. \n[1] https://arxiv.org/abs/2208.06358 \n[2] https://arxiv.org/abs/2206.13635 URL:https://dimag.ibs.re.kr/event/2022-08-31/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220830T163000 DTEND;TZID=Asia/Seoul:20220830T173000 DTSTAMP:20260417T071513 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:20220825T100000 DTEND;TZID=Asia/Seoul:20220825T110000 DTSTAMP:20260417T071513 CREATED:20220825T010000Z LAST-MODIFIED:20240707T075527Z UID:6007-1661421600-1661425200@dimag.ibs.re.kr SUMMARY:Brett Leroux\, Expansion of random 0/1 polytopes DESCRIPTION:A conjecture of Milena Mihail and Umesh Vazirani states that the edge expansion of the graph of every $0/1$ polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a $0/1$ polytope in $\mathbb{R}^d$ is greater than 1 over some polynomial function of $d$. This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of a random $0/1$ polytope in $\mathbb{R}^d$ is at least $\frac{1}{12d}$ with high probability. \nAfter discussing this result and the proof\, we will mention some possible extensions. To conclude\, we will discuss some related questions about the combinatorics of random polytopes\, including the diameter problem. \nThis is joint work with Luis Rademacher. URL:https://dimag.ibs.re.kr/event/2022-08-25/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220823T163000 DTEND;TZID=Asia/Seoul:20220823T173000 DTSTAMP:20260417T071513 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 BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220816T163000 DTEND;TZID=Asia/Seoul:20220816T173000 DTSTAMP:20260417T071513 CREATED:20220718T235006Z LAST-MODIFIED:20240705T171145Z UID:5967-1660667400-1660671000@dimag.ibs.re.kr SUMMARY:Noleen Köhler\, Testing first-order definable properties on bounded degree graphs DESCRIPTION:Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree model. We show that any FO property that is defined by a formula with quantifier prefix ∃*∀* is testable\, while there exists an FO property that is expressible by a formula with quantifier prefix ∀*∃* that is not testable. In the dense graph model\, a similar picture is long known (Alon\, Fischer\, Krivelevich\, Szegedy\, Combinatorica 2000)\, despite the very different nature of the two models. In particular\, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders\, based on zig-zag products of graphs. \nThis is joint work with Isolde Adler and Pan Peng. URL:https://dimag.ibs.re.kr/event/2022-08-16/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220810T163000 DTEND;TZID=Asia/Seoul:20220810T173000 DTSTAMP:20260417T071513 CREATED:20220713T073000Z LAST-MODIFIED:20240705T171145Z UID:5849-1660149000-1660152600@dimag.ibs.re.kr SUMMARY:Akash Kumar\, Random walks and Forbidden Minors DESCRIPTION:Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk\, I will present how random walks helped make progress on algorithmic problems on planar graphs.\nIn particular\, I show how random walk based (i.e.\, spectral) approaches led to progress on finding forbidden minors [K.-Seshadhri-Stolman\, FOCS 2018] as well as on deciding planarity [K.-Seshadhri-Stolman\, STOC 2019] in bounded degree graphs within the property testing framework. I will also cover how these approaches eventually led to progress on the so-called “efficient partition oracle” problem [K.-Seshadhri-Stolman\, FOCS 2021].\nThe talk will assume minimal background by presenting a stand-alone story that should be of interest to students/researchers in computer science. URL:https://dimag.ibs.re.kr/event/2022-08-10/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT END:VCALENDAR