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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230530T163000
DTEND;TZID=Asia/Seoul:20230530T173000
DTSTAMP:20260419T061454
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