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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230502T163000
DTEND;TZID=Asia/Seoul:20230502T173000
DTSTAMP:20260419T061525
CREATED:20230315T140009Z
LAST-MODIFIED:20240705T164210Z
UID:6916-1683045000-1683048600@dimag.ibs.re.kr
SUMMARY:Rob Morris\, An exponential improvement for diagonal Ramsey
DESCRIPTION:The Ramsey number $R(k)$ is the minimum n such that every red-blue colouring of the edges of the complete graph on n vertices contains a monochromatic copy of $K_k$. It has been known since the work of Erdős and Szekeres in 1935\, and Erdős in 1947\, that $2^{k/2} < R(k) < 4^k$\, but in the decades since the only improvements have been by lower order terms. In this talk I will sketch the proof of a very recent result\, which improves the upper bound of Erdős and Szekeres by a (small) exponential factor. \nBased on joint work with Marcelo Campos\, Simon Griffiths and Julian Sahasrabudhe.
URL:https://dimag.ibs.re.kr/event/2023-05-02/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230509T163000
DTEND;TZID=Asia/Seoul:20230509T173000
DTSTAMP:20260419T061525
CREATED:20230413T233653Z
LAST-MODIFIED:20240707T073713Z
UID:7041-1683649800-1683653400@dimag.ibs.re.kr
SUMMARY:Jozef Skokan\, Separating the edges of a graph by a linear number of paths
DESCRIPTION:Recently\, Letzter proved that any graph of order n contains a collection P of $O(n \log^*n)$ paths with the following property: for all distinct edges e and f there exists a path in P which contains e but not f. We improve this upper bound to 19n\, thus answering a question of Katona and confirming a conjecture independently posed by Balogh\, Csaba\, Martin\, and Pluhar and by Falgas-Ravry\, Kittipassorn\, Korandi\, Letzter\, and Narayanan. \nOur proof is elementary and self-contained.
URL:https://dimag.ibs.re.kr/event/2023-05-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230511T161500
DTEND;TZID=Asia/Seoul:20230511T171500
DTSTAMP:20260419T061525
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:20230516T163000
DTEND;TZID=Asia/Seoul:20230516T173000
DTSTAMP:20260419T061525
CREATED:20230116T010528Z
LAST-MODIFIED:20240707T073700Z
UID:6669-1684254600-1684258200@dimag.ibs.re.kr
SUMMARY:Oliver Janzer\, Small subgraphs with large average degree
DESCRIPTION:We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$\, we prove that every graph on $n$ vertices with average degree at least $d$ contains a subgraph of average degree at least $s$ on at most $nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}$ vertices. This is optimal up to the polylogarithmic factor\, and resolves a conjecture of Feige and Wagner. In addition\, we show that every graph with $n$ vertices and average degree at least $n^{1-\frac{2}{s}+\varepsilon}$ contains a subgraph of average degree at least $s$ on $O_{\varepsilon\,s}(1)$ vertices\, which is also optimal up to the constant hidden in the $O(.)$ notation\, and resolves a conjecture of Verstraëte. \nJoint work with Benny Sudakov and Istvan Tomon.
URL:https://dimag.ibs.re.kr/event/2023-05-16/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230517T160000
DTEND;TZID=Asia/Seoul:20230517T170000
DTSTAMP:20260419T061525
CREATED:20230220T090319Z
LAST-MODIFIED:20240705T165050Z
UID:6807-1684339200-1684342800@dimag.ibs.re.kr
SUMMARY:Szymon Toruńczyk\, Flip-width: Cops and Robber on dense graphs
DESCRIPTION:We define new graph parameters\, called flip-width\, that generalize treewidth\, degeneracy\, and generalized coloring numbers for sparse graphs\, and clique-width and twin-width for dense graphs. The flip-width parameters are defined using variants of the Cops and Robber game\, in which the robber has speed bounded by a fixed constant  r∈N∪{∞}\, and the cops perform flips (or perturbations) of the considered graph. We then propose a new notion of tameness of a graph class\, called bounded flip-width\, which is a dense counterpart of classes of bounded expansion of Nešetril and Ossona de Mendez\, and includes classes of bounded twin-width of Bonnet\, Kim\, Thomassé\, and Watrigant. This unifies Sparsity Theory and Twin-width Theory\, providing a common language for studying the central notions of the two theories\, such as weak coloring numbers and twin-width — corresponding to winning strategies of one player — or dense shallow minors\, rich divisions\, or well-linked sets\, corresponding to winning strategies of the other player. We prove that boundedness of flip-width is preserved by first-order interpretations\, or transductions\, generalizing previous results concerning classes of bounded expansion and bounded twin-width. We provide an algorithm approximating the flip-width of a given graph\, which runs in slicewise polynomial time (XP) in the size of the graph. Finally\, we propose a more general notion of tameness\, called almost bounded flip-width\, which is a dense counterpart of nowhere dense classes. We conjecture\, and provide evidence\, that classes with almost bounded flip-width coincide with monadically dependent (or monadically NIP) classes\, introduced by Shelah in model theory. We also provide evidence that classes of almost bounded flip-width characterise the hereditary graph classes for which the model-checking problem is fixed-parameter tractable.
URL:https://dimag.ibs.re.kr/event/2023-05-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230530T163000
DTEND;TZID=Asia/Seoul:20230530T173000
DTSTAMP:20260419T061525
CREATED:20230323T234815Z
LAST-MODIFIED:20240707T073642Z
UID:6946-1685464200-1685467800@dimag.ibs.re.kr
SUMMARY:Suyun Jiang (江素云)\, How connectivity affects the extremal number of trees
DESCRIPTION:The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest\, the conjecture remains unsolved. Recently\, Caro\, Patkós\, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them\, for a $k$-vertex tree $T$\, we construct $n$-vertex connected graphs that are $T$-free with at least $(1/4-o_k(1))nk$ edges\, showing that the additional connectivity condition can reduce the maximum size by at most a factor of 2. Furthermore\, we show that this is optimal: there is a family of $k$-vertex brooms $T$ such that the maximum size of an $n$-vertex connected $T$-free graph is at most $(1/4+o_k(1))nk$.
URL:https://dimag.ibs.re.kr/event/2023-05-30/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR