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:20221109T163000 DTEND;TZID=Asia/Seoul:20221109T173000 DTSTAMP:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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:20260417T073207 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 BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220809T163000 DTEND;TZID=Asia/Seoul:20220809T173000 DTSTAMP:20260417T073207 CREATED:20220808T073000Z LAST-MODIFIED:20240707T075550Z UID:5821-1660062600-1660066200@dimag.ibs.re.kr SUMMARY:Eun Jung Kim (김은정)\, Directed flow-augmentation DESCRIPTION:We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that\, given a directed graph G\, two integers $s\,t\in V(G)$\, and an integer $k$\, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$\, with probability $2^{−\operatorname{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph.\nThe directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set\, whose parameterized complexity status was repeatedly posed as open problems:\n(1) Chain SAT\, defined by Chitnis\, Egri\, and Marx [ESA’13\, Algorithmica’17]\,\n(2) a number of weighted variants of classic directed cut problems\, such as Weighted st-Cut\, Weighted Directed Feedback Vertex Set\, or Weighted Almost 2-SAT.\nBy proving that Chain SAT is FPT\, we confirm a conjecture of Chitnis\, Egri\, and Marx that\, for any graph H\, if the List H-Coloring problem is polynomial-time solvable\, then the corresponding vertex-deletion problem is fixed-parameter tractable. \nJoint work with Stefan Kratsch\, Marcin Pilipczuk\, Magnus Wahlström. URL:https://dimag.ibs.re.kr/event/2022-08-09/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220803T163000 DTEND;TZID=Asia/Seoul:20220803T173000 DTSTAMP:20260417T073207 CREATED:20220720T073000Z LAST-MODIFIED:20240707T075557Z UID:5637-1659544200-1659547800@dimag.ibs.re.kr SUMMARY:Lars Jaffke\, Taming graphs with no large creatures and skinny ladders DESCRIPTION:We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladder as an induced minor\, then there exists a polynomial $p$ such that every $G \in \mathcal{G}$ contains at most $p(|V(G)|)$ minimal separators. By a result of Fomin\, Todinca\, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set\, Feedback Vertex Set and many other problems\, when restricted to an input graph from $\mathcal{G}$. Furthermore\, as shown by Gartland and Lokshtanov\, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators). \nJoint work with Jakub Gajarský\, Paloma T. Lima\, Jana Novotná\, Marcin Pilipczuk\, Paweł Rzążewski\, and Uéverton S. Souza. URL:https://dimag.ibs.re.kr/event/2022-08-03/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220801T163000 DTEND;TZID=Asia/Seoul:20220801T173000 DTSTAMP:20260417T073207 CREATED:20220801T073000Z LAST-MODIFIED:20240707T075606Z UID:5867-1659371400-1659375000@dimag.ibs.re.kr SUMMARY:Seunghun Lee (이승훈)\, Inscribable order types DESCRIPTION:We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk\, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable\, and that the number of such order types is $\Theta(\frac{4^n}{n^{3/2}})$. We further construct an infinite family of minimally uninscribable order types. The proof of uninscribability mainly uses Möbius transformations. We also suggest open problems around inscribability. This is a joint work with Michael Gene Dobbins. URL:https://dimag.ibs.re.kr/event/2022-08-01/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220727T163000 DTEND;TZID=Asia/Seoul:20220727T173000 DTSTAMP:20260417T073207 CREATED:20220727T073000Z LAST-MODIFIED:20240705T171144Z UID:5830-1658939400-1658943000@dimag.ibs.re.kr SUMMARY:Noam Lifshitz\, Product free sets in the alternating group DESCRIPTION:A subset of a group is said to be product free if it does not contain the product of two elements in it. We consider how large can a product free subset of $A_n$ be? \nIn the talk we will completely solve the problem by determining the largest product free subset of $A_n$. \nOur proof combines a representation theoretic argument due to Gowers\, with an analytic tool called hypercontractivity for global functions. We also make use of a dichotomy between structure and a pseudorandomness notion of functions over the symmetric group known as globalness. \nBased on a joint work with Peter Keevash and Dor Minzer. URL:https://dimag.ibs.re.kr/event/2022-07-27/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220719T140000 DTEND;TZID=Asia/Seoul:20220719T160000 DTSTAMP:20260417T073207 CREATED:20220719T050000Z LAST-MODIFIED:20240705T171145Z UID:5880-1658239200-1658246400@dimag.ibs.re.kr SUMMARY:Jinyoung Park (박진영)\, Thresholds 2/2 DESCRIPTION:Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006\, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set\, its threshold is never far from its “expectation-threshold\,” which is a natural (and often easy to calculate) lower bound on the threshold. \nIn the first talk on Monday\, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself. \nIn the second talk on Tuesday\, I will discuss our proof of the conjecture in detail. URL:https://dimag.ibs.re.kr/event/2022-07-19/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220718T163000 DTEND;TZID=Asia/Seoul:20220718T173000 DTSTAMP:20260417T073207 CREATED:20220622T073000Z LAST-MODIFIED:20240705T171147Z UID:5878-1658161800-1658165400@dimag.ibs.re.kr SUMMARY:Jinyoung Park (박진영)\, Thresholds 1/2 DESCRIPTION:Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006\, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set\, its threshold is never far from its “expectation-threshold\,” which is a natural (and often easy to calculate) lower bound on the threshold. \nIn the first talk on Monday\, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself. \nIn the second talk on Tuesday\, I will discuss our proof of the conjecture in detail. URL:https://dimag.ibs.re.kr/event/2022-07-18/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220711T163000 DTEND;TZID=Asia/Seoul:20220711T173000 DTSTAMP:20260417T073207 CREATED:20220711T073000Z LAST-MODIFIED:20240707T075632Z UID:5896-1657557000-1657560600@dimag.ibs.re.kr SUMMARY:Kevin Hendrey\, Product Structure of Graph Classes with Bounded Treewidth DESCRIPTION:The strong product $G\boxtimes H$ of graphs $G$ and $H$ is the graph on the cartesian product $V(G)\times V(H)$ such that vertices $(v\,w)$ and $(x\,y)$ are adjacent if and only if $\max\{d_G(v\,x)\,d_H(w\,y)\}=1$. Graph product structure theory aims to describe complicated graphs in terms of subgraphs of strong products of simpler graphs. This area of research was initiated by Dujmović\, Joret\, Micek\, Morin\, Ueckerdt and Wood\, who showed that every planar graph is a subgraph of the strong product of a $H\boxtimes P\boxtimes K_3$ for some path $P$ and some graph $H$ of treewidth at most $3$. In this talk\, I will discuss the product structure of various graph classes of bounded treewidth. As an example\, we show that there is a function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that every planar graph of treewidth at most $k$ is a subgraph of $H\boxtimes K_{f(k)}$ for some graph $H$ of treewidth at most $3$. \nThis is based on joint work with Campbell\, Clinch\, Distel\, Gollin\, Hickingbotham\, Huynh\, Illingworth\, Tamitegama\, Tan and Wood. URL:https://dimag.ibs.re.kr/event/2022-07-11/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220707T100000 DTEND;TZID=Asia/Seoul:20220707T110000 DTSTAMP:20260417T073207 CREATED:20220707T010000Z LAST-MODIFIED:20240707T075642Z UID:5783-1657188000-1657191600@dimag.ibs.re.kr SUMMARY:Sepehr Hajebi\, Holes\, hubs and bounded treewidth DESCRIPTION:A hole in a graph $G$ is an induced cycle of length at least four\, and for every hole $H$ in $G$\, a vertex $h\in G\setminus H$ is called a $t$-hub for $H$ if $h$ has at least $t$ neighbor in $H$. Sintiari and Trotignon were the first to construct graphs with arbitrarily large treewidth and no induced subgraph isomorphic to the “basic obstructions\,” that is\, a fixed complete graph\, a fixed complete bipartite graph (with parts of equal size)\, all subdivisions of a fixed wall and line graphs of all subdivisions of a fixed wall. They named their counterexamples “layered wheels” for a good reason: layered wheels contain wheels in abundance\, where a wheel means a hole with a $3$-hub. In accordance\, one may ask whether graphs with no wheel and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. This was also disproved by a recent construction due to Davies. But holes with a $2$-hub cannot be avoided in graphs with large treewidth: graphs containing no hole with a $2$-hub and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. I will present a proof of this result\, and will also give an overview of related works.\nBased on joint work with Tara Abrishami\, Bogdan Alecu\, Maria Chudnovsky\, Sophie Spirkl and Kristina Vušković. URL:https://dimag.ibs.re.kr/event/2022-07-07/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220704T163000 DTEND;TZID=Asia/Seoul:20220704T173000 DTSTAMP:20260417T073207 CREATED:20220704T073000Z LAST-MODIFIED:20240707T075651Z UID:5797-1656952200-1656955800@dimag.ibs.re.kr SUMMARY:Eric Vigoda\, Computational phase transition and MCMC algorithms DESCRIPTION:This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to sample from the equilibrium distribution of the model or equivalently approximate the corresponding normalizing factor known as the partition function. We show that when correlations die off on the infinite D-regular tree then the Gibbs sampler has optimal mixing time of $O(n \log n)$ on any graph of maximum degree D\, whereas when the correlations persist (in the limit) then the sampling/counting problem are NP-hard to approximate.  The Gibbs sampler is a simple Markov Chain Monte Carlo (MCMC) algorithm. Key to these mixing results are a new technique known as spectral independence which considers the pairwise influence of vertices. We show that spectral independence implies an optimal convergence rate for a variety of MCMC algorithms. URL:https://dimag.ibs.re.kr/event/2022-07-04/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220629T163000 DTEND;TZID=Asia/Seoul:20220629T173000 DTSTAMP:20260417T073207 CREATED:20220611T121204Z LAST-MODIFIED:20240705T171148Z UID:5827-1656520200-1656523800@dimag.ibs.re.kr SUMMARY:Xizhi Liu\, Hypergraph Turán problem: from 1 to ∞ DESCRIPTION:One interesting difference between (nondegenerate) Graph Turán problem and Hypergraph Turán problem is that the hypergraph families can have at least two very different extremal constructions. In this talk\, we will look at some recent progress and approaches to constructing hypergraph families with at least two different extremal constructions.\nBased on some joint work with Dhruv Mubayi\, Christian Reiher\, Jianfeng Hou\, Heng Li\, and Yixiao Zhang. URL:https://dimag.ibs.re.kr/event/2022-06-29/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT END:VCALENDAR