Phase transition of degenerate Turán problems in $p$-norms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929737385902080 |
|---|---|
| author | Gao, Jun Liu, Xizhi Ma, Jie Pikhurko, Oleg |
| author_facet | Gao, Jun Liu, Xizhi Ma, Jie Pikhurko, Oleg |
| contents | For a positive real number $p$, the $p$-norm $\left\lVert G \right\rVert_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. Füredi and Kündgen \cite{FK06} show 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, assuming a mild assumption on the growth rate of $\mathrm{ex}(n,F)$. The main contribution of our paper is extending this result to hypergraph. Moreover, in the case of graph, our proof differs from that in \cite{FK06}, offering the advantage of producing the correct constant factor when $p > p_{F}$.
When $p = p_F$, Füredi and Kündgen proved a general upper bound on $\mathrm{ex}_{p}(n,F)$, tight up to a $\log n$ factor, and conjectured that this factor is unnecessary. We confirm this conjecture for several well-studied bipartite graphs, including one-side degree-bounded graphs and families of short even cycles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15579 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Phase transition of degenerate Turán problems in $p$-norms Gao, Jun Liu, Xizhi Ma, Jie Pikhurko, Oleg Combinatorics For a positive real number $p$, the $p$-norm $\left\lVert G \right\rVert_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. Füredi and Kündgen \cite{FK06} show 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, assuming a mild assumption on the growth rate of $\mathrm{ex}(n,F)$. The main contribution of our paper is extending this result to hypergraph. Moreover, in the case of graph, our proof differs from that in \cite{FK06}, offering the advantage of producing the correct constant factor when $p > p_{F}$. When $p = p_F$, Füredi and Kündgen proved a general upper bound on $\mathrm{ex}_{p}(n,F)$, tight up to a $\log n$ factor, and conjectured that this factor is unnecessary. We confirm this conjecture for several well-studied bipartite graphs, including one-side degree-bounded graphs and families of short even cycles. |
| title | Phase transition of degenerate Turán problems in $p$-norms |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.15579 |