Linear three-uniform hypergraphs with no Berge path of given length

Ervin Győri; Nika Salia

doi:10.1016/j.jctb.2024.11.003

Linear three-uniform hypergraphs with no Berge path of given length

Ervin Győri
, Nika Salia

Department of Mathematics

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

1 Scopus citations

Abstract

Extensions of Erdős-Gallai Theorem for general hypergraphs are well studied. In this work, we prove the extension of Erdős-Gallai Theorem for linear hypergraphs. In particular, we show that the number of hyperedges in an n-vertex 3-uniform linear hypergraph, without a Berge path of length k as a subgraph is at most [Formula presented] for k≥4. The bound is sharp for infinitely many k and n.

Original language	English
Pages (from-to)	36-48
Number of pages	13
Journal	Journal of Combinatorial Theory. Series B
Volume	171
DOIs	https://doi.org/10.1016/j.jctb.2024.11.003
State	Published - Mar 2025

Bibliographical note

Publisher Copyright:
© 2024 Elsevier Inc.

Keywords

Berge path
Extremal
Linear hypergraph
Turán

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2024.11.003

Cite this

@article{c27378bc37fc420abeb8c89fe72917b4,

title = "Linear three-uniform hypergraphs with no Berge path of given length",

abstract = "Extensions of Erd{\H o}s-Gallai Theorem for general hypergraphs are well studied. In this work, we prove the extension of Erd{\H o}s-Gallai Theorem for linear hypergraphs. In particular, we show that the number of hyperedges in an n-vertex 3-uniform linear hypergraph, without a Berge path of length k as a subgraph is at most [Formula presented] for k≥4. The bound is sharp for infinitely many k and n.",

keywords = "Berge path, Extremal, Linear hypergraph, Tur{\'a}n",

author = "Ervin Gy{\H o}ri and Nika Salia",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier Inc.",

year = "2025",

month = mar,

doi = "10.1016/j.jctb.2024.11.003",

language = "English",

volume = "171",

pages = "36--48",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Linear three-uniform hypergraphs with no Berge path of given length

AU - Győri, Ervin

AU - Salia, Nika

PY - 2025/3

Y1 - 2025/3

N2 - Extensions of Erdős-Gallai Theorem for general hypergraphs are well studied. In this work, we prove the extension of Erdős-Gallai Theorem for linear hypergraphs. In particular, we show that the number of hyperedges in an n-vertex 3-uniform linear hypergraph, without a Berge path of length k as a subgraph is at most [Formula presented] for k≥4. The bound is sharp for infinitely many k and n.

AB - Extensions of Erdős-Gallai Theorem for general hypergraphs are well studied. In this work, we prove the extension of Erdős-Gallai Theorem for linear hypergraphs. In particular, we show that the number of hyperedges in an n-vertex 3-uniform linear hypergraph, without a Berge path of length k as a subgraph is at most [Formula presented] for k≥4. The bound is sharp for infinitely many k and n.

KW - Berge path

KW - Extremal

KW - Linear hypergraph

KW - Turán

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

U2 - 10.1016/j.jctb.2024.11.003

DO - 10.1016/j.jctb.2024.11.003

M3 - Article

AN - SCOPUS:85211061740

SN - 0095-8956

VL - 171

SP - 36

EP - 48

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Linear three-uniform hypergraphs with no Berge path of given length

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this