[2018 Discrete Math 세미나]

** Date: ** 2018-11-05

**Speaker :** 강동엽 (KAIST)

**Abstract : **The extremal number ex(n,F) of a graph F is the maximum number of edges in an n-vertex graph not containing F as a subgraph. A real number r∈[1,2] is realisable if there exists a graph F with ex(n , F) = Θ(nr). Several decades ago, Erdős and Simonovits conjectured that every rational number in [1,2] is realisable. Despite decades of effort, the only known realisable numbers are 1,7/5,2, and the numbers of the form 1+(1/m), 2-(1/m), 2-(2/m) for integers m≥1. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2.
We discuss some recent progress on the conjecture of Erdős and Simonovits. First, we show that 2-(a/b) is realisable for any integers a,b≥1 with b>a and b≡±1 (mod a). This includes all previously known ones, and gives infinitely many limit points 2-(1/m) in the set of all realisable numbers as a consequence.
Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.
This is joint work with Jaehoon Kim and Hong Liu.

**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.