BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240306T160000
DTEND;TZID=Asia/Seoul:20240306T170000
DTSTAMP:20260511T102657
CREATED:20240205T021454Z
LAST-MODIFIED:20240705T154116Z
UID:8223-1709740800-1709744400@dimag.ibs.re.kr
SUMMARY:William Cook\, The Traveling Salesman Problem: Amazon Deliveries\, Pub Walks\, and Astro Tours
DESCRIPTION:Amazon drivers hit the road every day\, each taking a Prime van in a traveling salesman problem tour through 150 or more customer stops. But even a whisper of the TSP strikes fear in the heart of the computing world. A Washington Post article reported it would take “1\,000 years to compute the most efficient route between 22 cities.” Claims such as this\, however\, ignore 70 years of intense study. A 22-city TSP can be handled in a snap with modern methods\, even on an iPhone. And\, coming to the aid of Amazon drivers\, we describe techniques used to win the $100\,000 top prize in the Amazon Last Mile Routing Challenge\, together with Stephan Held and Keld Helsgaun. \nGoing larger\, we discuss methods used to find to precise optimality the shortest walking tour to 49\,687 pubs in the UK. Even larger\, if you want to visit 136\,606\,128 stars\, there is a 3D route\, ready to go\, that is guaranteed to be no more than 1.00018 times longer that a shortest-possible tour. \nThe general setting is the following. Complexity theory suggests there are limits to the power of general-purpose computational techniques\, in engineering\, science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this discussion\, demonstrating whether or not focused efforts on a single\, possibly unsolvable\, model will produce results beyond our expectations.
URL:https://dimag.ibs.re.kr/event/2024-03-06/
LOCATION:Room 1501\, Bldg. E2-2\, KAIST
CATEGORIES:Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230511T161500
DTEND;TZID=Asia/Seoul:20230511T171500
DTSTAMP:20260511T102657
CREATED:20230301T130657Z
LAST-MODIFIED:20240705T165043Z
UID:6864-1683821700-1683825300@dimag.ibs.re.kr
SUMMARY:Maria Chudnovsky\, Induced subgraphs and tree decompositions
DESCRIPTION:Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. Tree decompositions have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last couple of years we have made significant progress in this direction\, exploring both the classical notion of bounded tree-width\, and concepts of more structural flavor. This talk will survey some of these ideas and results.
URL:https://dimag.ibs.re.kr/event/2023-05-11/
LOCATION:Room 1501\, Bldg. E6-1\, KAIST
CATEGORIES:Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230427T161500
DTEND;TZID=Asia/Seoul:20230427T171500
DTSTAMP:20260511T102657
CREATED:20230321T001954Z
LAST-MODIFIED:20240705T164205Z
UID:6930-1682612100-1682615700@dimag.ibs.re.kr
SUMMARY:Rob Morris\, Ramsey theory: searching for order in chaos
DESCRIPTION:In many different areas of mathematics (such as number theory\, discrete geometry\, and combinatorics)\, one is often presented with a large “unstructured” object\, and asked to find a smaller “structured” object inside it. One of the earliest and most influential examples of this phenomenon was the theorem of Ramsey\, proved in 1930\, which states that if n = n(k) is large enough\, then in any red-blue colouring of the edges of the complete graph on n vertices\, there exists a monochromatic clique on k vertices. In this talk I will discuss some of the questions\, ideas\, and new techniques that were inspired by this theorem\, and present some recent progress on one of the central problems in the area: bounding the so-called “diagonal” Ramsey numbers. Based on joint work with Marcelo Campos\, Simon Griffiths and Julian Sahasrabudhe.
URL:https://dimag.ibs.re.kr/event/2023-04-27/
LOCATION:Room 1501\, Bldg. E6-1\, KAIST
CATEGORIES:Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221027T161500
DTEND;TZID=Asia/Seoul:20221027T171500
DTSTAMP:20260511T102657
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:20221013T161500
DTEND;TZID=Asia/Seoul:20221013T171500
DTSTAMP:20260511T102657
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:20220602T161500
DTEND;TZID=Asia/Seoul:20220602T171500
DTSTAMP:20260511T102657
CREATED:20220602T071500Z
LAST-MODIFIED:20240705T172222Z
UID:5763-1654186500-1654190100@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Graph minor theory and beyond
DESCRIPTION:[Colloquium\, Department of Mathematical Sciences\, KAIST] \nOne of the important work in graph theory is the graph minor theory developed by Robertson and Seymour in 1980-2010. This provides a complete description of the class of graphs that do not contain a fixed graph H as a minor. Later on\, several generalizations of H-minor free graphs\, which are sparse\, have been defined and studied. Also\, similar topics on dense graph classes have been deeply studied. In this talk\, I will survey topics in graph minor theory\, and discuss related topics in structural graph theory.
URL:https://dimag.ibs.re.kr/event/2022-06-02-kwon/
LOCATION:Room 1501\, Bldg. E6-1\, KAIST
CATEGORIES:Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220519T161500
DTEND;TZID=Asia/Seoul:20220519T171500
DTSTAMP:20260511T102657
CREATED:20220519T071500Z
LAST-MODIFIED:20240707T080000Z
UID:5661-1652976900-1652980500@dimag.ibs.re.kr
SUMMARY:Gil Kalai\, The Cascade Conjecture and other Helly-type Problems
DESCRIPTION:[Colloquium\, Department of Mathematical Sciences\, KAIST] \nFor a set $X$ of points $x(1)$\, $x(2)$\, $\ldots$\, $x(n)$ in some real vector space $V$ we denote by $T(X\,r)$ the set of points in $X$ that belong to the convex hulls of r pairwise disjoint subsets of $X$.\nWe let $t(X\,r)=1+\dim(T(X\,r))$. \nRadon’s theorem asserts that\nIf $t(X\,1)< |X|$\, then $t(X\, 2) >0$. \nThe first open case of the cascade conjecture asserts that\nIf $t(X\,1)+t(X\,2) < |X|$\, then $t(X\,3) >0$. \nIn the lecture\, I will discuss connections with topology and with various problems in graph theory. I will also mention questions regarding dimensions of intersection of convex sets. \nSome related material:\n1) A lecture (from 1999): An invitation to Tverberg Theorem: https://youtu.be/Wjg1_QwjUos\n2) A paper on Helly type problems by Barany and me https://arxiv.org/abs/2108.08804\n3) A link to Barany’s book: Combinatorial convexity https://www.amazon.com/Combinatorial-Convexity-University-Lecture-77/dp/1470467097
URL:https://dimag.ibs.re.kr/event/2022-05-19/
LOCATION:Zoom ID: 868 7549 9085
CATEGORIES:Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210506T161500
DTEND;TZID=Asia/Seoul:20210506T171500
DTSTAMP:20260511T102657
CREATED:20210427T013100Z
LAST-MODIFIED:20240705T185031Z
UID:4010-1620317700-1620321300@dimag.ibs.re.kr
SUMMARY:Hong Liu\, Sublinear expander and embeddings sparse graphs
DESCRIPTION:A notion of sublinear expander has played a central role in the resolutions of a couple of long-standing conjectures in embedding problems in graph theory\, including e.g. the odd cycle problem of Erdős and Hajnal that the harmonic sum of odd cycle length in a graph diverges with its chromatic number. I will survey some of these developments.
URL:https://dimag.ibs.re.kr/event/2021-05-06-2/
LOCATION:Zoom
CATEGORIES:Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20191008T163000
DTEND;TZID=Asia/Seoul:20191008T173000
DTSTAMP:20260511T102657
CREATED:20190709T235022Z
LAST-MODIFIED:20240705T210004Z
UID:1072-1570552200-1570555800@dimag.ibs.re.kr
SUMMARY:Alexandr V. Kostochka\, On Ramsey-type problems for paths and cycles in dense graphs
DESCRIPTION:A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally\, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors\, there is a monochromatic copy of $H$. In these terms\, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$. \nWe consider sufficient conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular\, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás\, Ruszinkó\, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp. \nThis is joint work with Jozsef Balogh\, Mikhail Lavrov and Xujun Liu.
URL:https://dimag.ibs.re.kr/event/2019-10-08/
LOCATION:Room 1501\, Bldg. E6-1\, KAIST
CATEGORIES:Colloquium
END:VEVENT
END:VCALENDAR