[2018 Discrete Math 세미나 ]

** Date: ** 2018-09-17

**Speaker :** Lee Joonkyung (Universität Hamburg)

**Abstract : **One of the cornerstones of extremal graph theory is a result of Füredi, later reproved and given due prominence by Alon, Krivelevich and Sudakov, saying that if H is a bipartite graph with maximum degree r on one side, then there is a constant C such that every graph with n vertices and C n2 – 1/r edges contains a copy of H. This result is tight up to the constant when H contains a copy of Kr,s with s sufficiently large in terms of r. We conjecture that this is essentially the only situation in which Füredi’s result can be tight and prove this conjecture for r = 2. More precisely, we show that if H is a C4-free bipartite graph with maximum degree 2 on one side, then there are positive constants C and δ such that every graph with n vertices and C n3/2 – δ edges contains a copy of H. This answers a question by Erdős from 1988. The proof relies on a novel variant of the dependent random choice technique which may be of independent interest. This is joint work with David Conlon.

**VOD : **[VIDEO] [YOUTUBE]

Information Center for Mathematical Sciences KAIST

34141 대전광역시 유성구 대학로 291 (구성동373-1)

한국과학기술원(KAIST) 수리과학정보센터

전화 042-350-8196

e-mail : mathnet@mathnet.or.kr

Copyright (C) 2018. ICMS All Rights Reserved.

34141 대전광역시 유성구 대학로 291 (구성동373-1)

한국과학기술원(KAIST) 수리과학정보센터

전화 042-350-8196

e-mail : mathnet@mathnet.or.kr

Copyright (C) 2018. ICMS All Rights Reserved.