Loading Events

« All Events

  • This event has passed.
:

David Wood, Tree densities of sparse graph classes

Wednesday, February 17, 2021 @ 10:00 AM - 11:00 AM KST

Zoom ID: 869 4632 6610 (ibsdimag)

Speaker

David Wood
School of Mathematics, Monash University
https://users.monash.edu.au/~davidwo/

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 G as n? I will answer this question for a variety of sparse graph classes G. In particular, we show that the answer is Θ(nαd(T)) where α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 G. For example, when G is the class of k-degenerate graphs then d=k; when G is the class of graphs containing no Ks,t-minor (ts) then d=s1; and when 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).

Details

Date:
Wednesday, February 17, 2021
Time:
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.