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:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210217T100000
DTEND;TZID=Asia/Seoul:20210217T110000
DTSTAMP:20260423T203121
CREATED:20201231T022333Z
LAST-MODIFIED:20240707T081843Z
UID:3423-1613556000-1613559600@dimag.ibs.re.kr
SUMMARY:David Wood\, Tree densities of sparse graph classes
DESCRIPTION:This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $\mathcal{G}$ as $n\to \infty$? I will answer this question for a variety of sparse graph classes $\mathcal{G}$. In particular\, we show that the answer is $\Theta(n^{\alpha_d(T)})$ where $\alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$\, for some integer $d$ that depends on $\mathcal{G}$. For example\, when $\mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $\mathcal{G}$ is the class of graphs containing no $K_{s\,t}$-minor ($t\geq s$) then $d=s-1$; and when $\mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs. This is joint work with Tony Huynh (arXiv:2009.12989).
URL:https://dimag.ibs.re.kr/event/2021-02-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR