|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Turan numbers of bipartite subdivisions | | Tao Jiang
; Yu Qiu
; | | Date: |
22 May 2019 | | Abstract: | Given a graph $H$, the Tur’an number $ex(n,H)$ is the largest number of
edges in an $H$-free graph on $n$ vertices. We make progress on a recent
conjecture of Conlon, Janzer, and Lee on the Tur’an numbers of bipartite
graphs, which in turn yields further progress on a conjecture of ErdH{o}s and
Simonovits. Let $s,t,kgeq 2$ be integers. Let $K_{s,t}^k$ denote the graph
obtained from the complete bipartite graph $K_{s,t}$ by replacing each edge
$uv$ in it with a path of length $k$ between $u$ and $v$ such that the $st$
replacing paths are internally disjoint. It follows from a general theorem of
Bukh and Conlon that $ex(n,K_{s,t}^k)=Omega(n^{1+frac{1}{k}-frac{1}{sk}})$.
Conlon, Janzer, and Lee recently conjectured that for any integers $s,t,kgeq
2$, $ex(n,K_{s,t}^k)=O(n^{1+frac{1}{k}-frac{1}{sk}})$. Among many other
things, they settled the $k=2$ case of their conjecture. As the main result of
this paper, we prove their conjecture for $k=3,4$. Our main results also yield
infinitely many new so-called Tur’an exponents: rationals $rin (1,2)$ for
which there exists a bipartite graph $H$ with $ex(n, H)=Theta(n^r)$, adding to
the lists recently obtained by Jiang, Ma, Yepremyan, by Kang, Kim, Liu, and by
Conlon, Janzer, Lee. Our method builds on an extension of the Conlon-Janzer-Lee
method. We also note that the extended method also gives a weaker version of
the Conlon-Janzer-Lee conjecture for all $kgeq 2$. | | Source: | arXiv, 1905.8994 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER