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:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240306T160000
DTEND;TZID=Asia/Seoul:20240306T170000
DTSTAMP:20260418T041933
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:20240312T163000
DTEND;TZID=Asia/Seoul:20240312T173000
DTSTAMP:20260418T041933
CREATED:20240215T014045Z
LAST-MODIFIED:20240707T072526Z
UID:8255-1710261000-1710264600@dimag.ibs.re.kr
SUMMARY:Linda Cook\, On polynomial degree-boundedness
DESCRIPTION:We prove a conjecture of Bonamy\, Bousquet\, Pilipczuk\, Rzążewski\, Thomassé\, and Walczak\, that for every graph $H$\, there is a polynomial $p$ such that for every positive integer $s$\, every graph of average degree at least $p(s)$ contains either $K_{s\,s}$ as a subgraph or contains an induced subdivision of $H$. This improves upon a result of Kühn and Osthus from 2004 who proved it for graphs whose average degree is at least triply exponential in $s$ and a recent result of Du\, Girão\, Hunter\, McCarty and Scott for graphs with average degree at least singly exponential in $s$. \nAs an application\, we prove that the class of graphs that do not contain an induced subdivision of $K_{s\,t}$ is polynomially $\chi$-bounded. In the case of $K_{2\,3}$\, this is the class of theta-free graphs\, and answers a question of Davies. Along the way\, we also answer a recent question of McCarty\, by showing that if $\mathcal{G}$ is a hereditary class of graphs for which there is a polynomial $p$ such that every bipartite $K_{s\,s}$-free graph in $\mathcal{G}$ has average degree at most $p(s)$\, then more generally\, there is a polynomial $p’$ such that every $K_{s\,s}$-free graph in $\mathcal{G}$ has average degree at most $p'(s)$. Our main new tool is an induced variant of the Kővári-Sós-Turán theorem\, which we find to be of independent interest. \nThis is joint work with Romain Bourneuf (ENS de Lyon)\, Matija Bucić (Princeton)\, and James Davies (Cambridge)\,
URL:https://dimag.ibs.re.kr/event/2024-03-12/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240326T163000
DTEND;TZID=Asia/Seoul:20240326T173000
DTSTAMP:20260418T041933
CREATED:20240115T052614Z
LAST-MODIFIED:20240707T072512Z
UID:8129-1711470600-1711474200@dimag.ibs.re.kr
SUMMARY:Evangelos Protopapas\, Erdős-Pósa Dualities for Minors
DESCRIPTION:Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graphs classes. The class $\mathcal{H}$ has the Erdős-Pósa property in $\mathcal{G}$ if there is a function $f : \mathbb{N} \to \mathbb{N}$ such that every graph $G$ in $\mathcal{G}$ either contains (a packing of) $k$ disjoint copies of some subgraph minimal graph $H \not\in \mathcal{H}$ or contains (a covering of) $f(k)$ vertices\, whose removal creates a graph in $\mathcal{H}$. A class $\mathcal{G}$ is a minimal EP-counterexample for $\mathcal{H}$ if $\mathcal{H}$ does not have the Erdős-Pósa property in $\mathcal{G}$\, however it does have this property for every minor-closed graph class that is properly contained in $\mathcal{G}$. The set $\frak{C}_{\mathcal{H}}$ of the subset-minimal EP-counterexamples\, for every $\mathcal{H}$\, can be seen as a way to consider all possible Erdős-Pósa dualities that can be proven for minor-closed classes. We prove that\, for every $\mathcal{H}$\, $\frak{C}_{\mathcal{H}}$ is finite and we give a complete characterization of it. In particular\, we prove that $|\frak{C}_{\mathcal{H}}| = 2^{\operatorname{poly}(\ell(h))}$\, where $h$ is the maximum size of a minor-obstruction of $\mathcal{H}$ and $\ell(\cdot)$ is the unique linkage function. As a corollary of this\, we obtain a constructive proof of Thomas’ conjecture claiming that every minor-closed graph class has the half-integral Erdős-Pósa property in all graphs. \nThis is joint work with Christophe Paul\, Dimitrios Thilikos\, and Sebastian Wiederrecht.
URL:https://dimag.ibs.re.kr/event/2024-03-26/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR