Turán numbers of Berge trees

Ervin Győri; Nika Salia; Casey Tompkins; Oscar Zamora

doi:10.1016/j.disc.2022.113286

Turán numbers of Berge trees

Ervin Győri
, Nika Salia^*
, Casey Tompkins
, Oscar Zamora

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

A classical conjecture of Erdős and Sós asks to determine the Turán number of a tree. We consider variants of this problem in the settings of hypergraphs and multi-hypergraphs. In particular, for all k and r, with r≥k(k−2), we show that any r-uniform hypergraph H with more than [Formula presented] hyperedges contains a Berge copy of any tree with k edges different from the k-edge star. This bound is sharp when r+1 divides n and for such values of n we determine the extremal hypergraphs.

Original language	English
Article number	113286
Journal	Discrete Mathematics
Volume	346
Issue number	4
DOIs	https://doi.org/10.1016/j.disc.2022.113286
State	Published - Apr 2023
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2022 Elsevier B.V.

Keywords

Berge
Extremal
Star
Tree

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2022.113286

Cite this

@article{e61e54f6b4654401ac0bb7df0357aa47,

title = "Tur{\'a}n numbers of Berge trees",

abstract = "A classical conjecture of Erd{\H o}s and S{\'o}s asks to determine the Tur{\'a}n number of a tree. We consider variants of this problem in the settings of hypergraphs and multi-hypergraphs. In particular, for all k and r, with r≥k(k−2), we show that any r-uniform hypergraph H with more than [Formula presented] hyperedges contains a Berge copy of any tree with k edges different from the k-edge star. This bound is sharp when r+1 divides n and for such values of n we determine the extremal hypergraphs.",

keywords = "Berge, Extremal, Star, Tree",

author = "Ervin Gy{\H o}ri and Nika Salia and Casey Tompkins and Oscar Zamora",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2023",

month = apr,

doi = "10.1016/j.disc.2022.113286",

language = "English",

volume = "346",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "4",

}

TY - JOUR

T1 - Turán numbers of Berge trees

AU - Győri, Ervin

AU - Salia, Nika

AU - Tompkins, Casey

AU - Zamora, Oscar

PY - 2023/4

Y1 - 2023/4

N2 - A classical conjecture of Erdős and Sós asks to determine the Turán number of a tree. We consider variants of this problem in the settings of hypergraphs and multi-hypergraphs. In particular, for all k and r, with r≥k(k−2), we show that any r-uniform hypergraph H with more than [Formula presented] hyperedges contains a Berge copy of any tree with k edges different from the k-edge star. This bound is sharp when r+1 divides n and for such values of n we determine the extremal hypergraphs.

AB - A classical conjecture of Erdős and Sós asks to determine the Turán number of a tree. We consider variants of this problem in the settings of hypergraphs and multi-hypergraphs. In particular, for all k and r, with r≥k(k−2), we show that any r-uniform hypergraph H with more than [Formula presented] hyperedges contains a Berge copy of any tree with k edges different from the k-edge star. This bound is sharp when r+1 divides n and for such values of n we determine the extremal hypergraphs.

KW - Berge

KW - Extremal

KW - Star

KW - Tree

UR - https://www.scopus.com/pages/publications/85143790224

U2 - 10.1016/j.disc.2022.113286

DO - 10.1016/j.disc.2022.113286

M3 - Article

AN - SCOPUS:85143790224

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 4

M1 - 113286

ER -

Turán numbers of Berge trees

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this