BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.16.2//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:20260526T003911
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:20260526T003911
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:20230516T163000
DTEND;TZID=Asia/Seoul:20230516T173000
DTSTAMP:20260526T003911
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:20230530T163000
DTEND;TZID=Asia/Seoul:20230530T173000
DTSTAMP:20260526T003911
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