EUVIMEDEUVIMED entdecken
Crossref

On Turán exponents of bipartite graphs

Tao Jiang, Jie Ma, Liana Yepremyan

Combinatorics, Probability and Computing · 2022-03 · 31 (2) · 333-344

DOI: 10.1017/s0963548321000341 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Combinatorics, Probability and Computing, online erschienen am 04.08.2021. Verfasst von Tao Jiang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 32 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A long-standing conjecture of Erdős and Simonovits asserts that for every rational number $r\in (1,2)$ there exists a bipartite graph H such that $\mathrm{ex}(n,H)=\Theta(n^r)$ . So far this conjecture is known to be true only for rationals of form $1+1/k$ and $2-1/k$ , for integers $k\geq 2$ . In this paper, we add a new form of rationals for which the conjecture is true: $2-2/(2k+1)$ , for $k\geq 2$ . This in turn also gives an affirmative answer to a question of Pinchasi and Sharir on cube-like graphs. Recently, a version of Erdős and Simonovits $^{\prime}$ s conjecture, where one replaces a single graph by a finite family, was confirmed by Bukh and Conlon. They proposed a construction of bipartite graphs which should satisfy Erdős and Simonovits $^{\prime}$ s conjecture. Our result can also be viewed as a first step towards verifying Bukh and Conlon $^{\prime}$ s conjecture. We also prove an upper bound on the Turán number of theta graphs in an asymmetric setting and employ this result to obtain another new rational exponent for Turán exponents: $r=7/5$ .

Zitieren

APA

Jiang, T., Ma, J., & Yepremyan, L. (2022). On Turán exponents of bipartite graphs. Combinatorics, Probability and Computing, 31(2), 333-344. https://doi.org/10.1017/s0963548321000341

Vancouver

Jiang T, Ma J, Yepremyan L. On Turán exponents of bipartite graphs. Combinatorics, Probability and Computing. 2022;31(2):333-344. doi:10.1017/s0963548321000341

BibTeX
@article{Jiang2022,
  author = {Jiang, Tao and Ma, Jie and Yepremyan, Liana},
  title = {On Turán exponents of bipartite graphs},
  journal = {Combinatorics, Probability and Computing},
  year = {2022},
  volume = {31},
  number = {2},
  pages = {333--344},
  doi = {10.1017/s0963548321000341}
}
Kostenlos starten →