Loading Events

« All Events

:

Jun Gao (高峻), Phase transition of degenerate Turán problems in p-norms

December 13 Friday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)

Speaker

Jun Gao (高峻)
IBS Extremal Combinatorics and Probability Group
https://www.ibs.re.kr/ecopro/jungao/

For a positive real number $p$, the $p$-norm $\|G\|_p$ of a graph $G$ is the sum of the $p$-th powers of all vertex degrees. We study the maximum $p$-norm $\mathrm{ex}_{p}(n,F)$ of $F$-free graphs on $n$ vertices, focusing on the case where $F$ is a bipartite graph. It is natural to conjecture that for every bipartite graph $F$, there exists a threshold $p_F$ such that for $p< p_{F}$, the order of $\mathrm{ex}_{p}(n,F)$ is governed by pseudorandom constructions, while for $p > p_{F}$, it is governed by star-like constructions. We determine the exact value of $p_{F}$, under a mild assumption on the growth rate of $\mathrm{ex}(n,F)$. Our results extend to $r$-uniform hypergraphs as well.

We also prove a general upper bound that is tight up to a $\log n$ factor for $\mathrm{ex}_{p}(n,F)$ when $p = p_{F}$.
We conjecture that this $\log n$ factor is unnecessary and prove this conjecture for several classes of well-studied bipartite graphs, including one-side degree-bounded graphs and families of short even cycles.

This is a joint work with Xizhi Liu, Jie Ma and Oleg Pikhurko.

Details

Date:
December 13 Friday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Room B332
IBS (기초과학연구원) + Google Map

Organizer

Sang-il Oum (엄상일)
View Organizer Website
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.