On the maximum size of connected hypergraphs without a path of given length

Ervin Győri; Abhishek Methuku; Nika Salia; Casey Tompkins; Máté Vizer

doi:10.1016/j.disc.2018.06.006

On the maximum size of connected hypergraphs without a path of given length

Ervin Győri, Abhishek Methuku, Nika Salia, Casey Tompkins, Máté Vizer^*

^*Corresponding author for this work

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

12 Scopus citations

Abstract

In this note we asymptotically determine the maximum number of hyperedges possible in an r-uniform, connected n-vertex hypergraph without a Berge path of length k, as n and k tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.

Original language	English
Pages (from-to)	2602-2605
Number of pages	4
Journal	Discrete Mathematics
Volume	341
Issue number	9
DOIs	https://doi.org/10.1016/j.disc.2018.06.006
State	Published - Sep 2018
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2018 Elsevier B.V.

Keywords

Berge hypergraph
Connected
Erdős–Gallai

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2018.06.006

Cite this

@article{6278f42f31b04c72a55387adf715ab99,

title = "On the maximum size of connected hypergraphs without a path of given length",

abstract = "In this note we asymptotically determine the maximum number of hyperedges possible in an r-uniform, connected n-vertex hypergraph without a Berge path of length k, as n and k tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.",

keywords = "Berge hypergraph, Connected, Erd{\H o}s–Gallai",

author = "Ervin Gy{\H o}ri and Abhishek Methuku and Nika Salia and Casey Tompkins and M{\'a}t{\'e} Vizer",

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

year = "2018",

month = sep,

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

language = "English",

volume = "341",

pages = "2602--2605",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "9",

}

TY - JOUR

T1 - On the maximum size of connected hypergraphs without a path of given length

AU - Győri, Ervin

AU - Methuku, Abhishek

AU - Salia, Nika

AU - Tompkins, Casey

AU - Vizer, Máté

PY - 2018/9

Y1 - 2018/9

N2 - In this note we asymptotically determine the maximum number of hyperedges possible in an r-uniform, connected n-vertex hypergraph without a Berge path of length k, as n and k tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.

AB - In this note we asymptotically determine the maximum number of hyperedges possible in an r-uniform, connected n-vertex hypergraph without a Berge path of length k, as n and k tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.

KW - Berge hypergraph

KW - Connected

KW - Erdős–Gallai

UR - http://www.scopus.com/inward/record.url?scp=85048856738&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2018.06.006

DO - 10.1016/j.disc.2018.06.006

M3 - Article

AN - SCOPUS:85048856738

SN - 0012-365X

VL - 341

SP - 2602

EP - 2605

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 9

ER -

On the maximum size of connected hypergraphs without a path of given length

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this