Turán numbers for Berge-hypergraphs and related extremal problems

Cory Palmer; Michael Tait; Craig Timmons; Adam Zsolt Wagner

doi:10.1016/j.disc.2019.02.003

Turán numbers for Berge-hypergraphs and related extremal problems

Cory Palmer
, Michael Tait
, Craig Timmons
, Adam Zsolt Wagner

Mathematical Sciences

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

22 Scopus citations

Abstract

Let F be a graph. We say that a hypergraph H is a Berge-F if there is a bijection f:E(F)→E(H) such that e⊆f(e) for every e∈E(F). Note that Berge-F actually denotes a class of hypergraphs. The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-F is denoted ex _r (n,Berge-F). In this paper, we investigate the case when F=K _s,t and establish an upper-bound when r≥3, and a lower-bound when r=4 and t is large enough compared to s. Additionally, we prove a counting result for r-graphs of girth five that complements the asymptotic formula ex ₃ (n,Berge-{C ₂ ,C ₃ ,C ₄ })=[Formula presented]n ^3∕2 +o(n ^3∕2 ) of Lazebnik and Verstraëte (2003).

Original language	English
Pages (from-to)	1553-1563
Number of pages	11
Journal	Discrete Mathematics
Volume	342
Issue number	6
DOIs	https://doi.org/10.1016/j.disc.2019.02.003
State	Published - Jun 2019

Funding

Research supported by University of Montana, United States UGP Grant #M25460.Research is supported by National Science Foundation, United States grant DMS-1606350.Research supported in part by Simons Foundation, United States Grant #359419.

Funders	Funder number
DMS-1606350
Simons Foundation	#359419
#M25460

Keywords

Berge-hypergraph
Turán number
extremal problems

Access to Document

10.1016/j.disc.2019.02.003

Cite this

@article{aeb9b0dd7d324231b770c2203c4b684d,

title = "Tur{\'a}n numbers for Berge-hypergraphs and related extremal problems",

abstract = " Let F be a graph. We say that a hypergraph H is a Berge-F if there is a bijection f:E(F)→E(H) such that e⊆f(e) for every e∈E(F). Note that Berge-F actually denotes a class of hypergraphs. The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-F is denoted ex r (n,Berge-F). In this paper, we investigate the case when F=K s,t and establish an upper-bound when r≥3, and a lower-bound when r=4 and t is large enough compared to s. Additionally, we prove a counting result for r-graphs of girth five that complements the asymptotic formula ex 3 (n,Berge-\{C 2 ,C 3 ,C 4 \})=[Formula presented]n 3∕2 +o(n 3∕2 ) of Lazebnik and Verstra{\"e}te (2003).",

keywords = "Berge-hypergraph, Tur{\'a}n number, extremal problems",

author = "Cory Palmer and Michael Tait and Craig Timmons and Wagner, \{Adam Zsolt\}",

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

year = "2019",

month = jun,

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

language = "English",

volume = "342",

pages = "1553--1563",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Turán numbers for Berge-hypergraphs and related extremal problems

AU - Palmer, Cory

AU - Tait, Michael

AU - Timmons, Craig

AU - Wagner, Adam Zsolt

PY - 2019/6

Y1 - 2019/6

N2 - Let F be a graph. We say that a hypergraph H is a Berge-F if there is a bijection f:E(F)→E(H) such that e⊆f(e) for every e∈E(F). Note that Berge-F actually denotes a class of hypergraphs. The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-F is denoted ex r (n,Berge-F). In this paper, we investigate the case when F=K s,t and establish an upper-bound when r≥3, and a lower-bound when r=4 and t is large enough compared to s. Additionally, we prove a counting result for r-graphs of girth five that complements the asymptotic formula ex 3 (n,Berge-{C 2 ,C 3 ,C 4 })=[Formula presented]n 3∕2 +o(n 3∕2 ) of Lazebnik and Verstraëte (2003).

AB - Let F be a graph. We say that a hypergraph H is a Berge-F if there is a bijection f:E(F)→E(H) such that e⊆f(e) for every e∈E(F). Note that Berge-F actually denotes a class of hypergraphs. The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-F is denoted ex r (n,Berge-F). In this paper, we investigate the case when F=K s,t and establish an upper-bound when r≥3, and a lower-bound when r=4 and t is large enough compared to s. Additionally, we prove a counting result for r-graphs of girth five that complements the asymptotic formula ex 3 (n,Berge-{C 2 ,C 3 ,C 4 })=[Formula presented]n 3∕2 +o(n 3∕2 ) of Lazebnik and Verstraëte (2003).

KW - Berge-hypergraph

KW - Turán number

KW - extremal problems

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

U2 - 10.1016/j.disc.2019.02.003

DO - 10.1016/j.disc.2019.02.003

M3 - Article

AN - SCOPUS:85062678511

SN - 0012-365X

VL - 342

SP - 1553

EP - 1563

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

ER -

Turán numbers for Berge-hypergraphs and related extremal problems

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this