Stability of extremal connected hypergraphs avoiding Berge-paths

Dániel Gerbner; Dániel T. Nagy; Balázs Patkós; Nika Salia; Máté Vizer

doi:10.1016/j.ejc.2024.103930

Stability of extremal connected hypergraphs avoiding Berge-paths

Dániel Gerbner
, Dániel T. Nagy
, Balázs Patkós
, Nika Salia
, Máté Vizer

Department of Mathematics

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

2 Scopus citations

Abstract

A Berge-path of length k in a hypergraph H is a sequence v₁,e₁,v₂,e₂,…,v_k,e_k,v_k+1 of distinct vertices and hyperedges with v_i,v_i+1∈e_i, for i≤k. Füredi, Kostochka and Luo, and independently Győri, Salia and Zamora determined the maximum number of hyperedges in an n-vertex, connected, r-uniform hypergraph that does not contain a Berge-path of length k provided k is large enough compared to r. They also determined the unique extremal hypergraph H₁. We prove a stability version of this result by presenting another construction H₂ and showing that any n-vertex, connected, r-uniform hypergraph without a Berge-path of length k, that contains more than |H₂| hyperedges must be a sub-hypergraph of the extremal hypergraph H₁, provided k is large enough compared to r.

Original language	English
Article number	103930
Journal	European Journal of Combinatorics
Volume	118
DOIs	https://doi.org/10.1016/j.ejc.2024.103930
State	Published - May 2024

Bibliographical note

Publisher Copyright:
© 2024

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2024.103930

Cite this

@article{14bdac71324e4ef8bd4ee564123e5378,

title = "Stability of extremal connected hypergraphs avoiding Berge-paths",

abstract = "A Berge-path of length k in a hypergraph H is a sequence v1,e1,v2,e2,…,vk,ek,vk+1 of distinct vertices and hyperedges with vi,vi+1∈ei, for i≤k. F{\"u}redi, Kostochka and Luo, and independently Gy{\H o}ri, Salia and Zamora determined the maximum number of hyperedges in an n-vertex, connected, r-uniform hypergraph that does not contain a Berge-path of length k provided k is large enough compared to r. They also determined the unique extremal hypergraph H1. We prove a stability version of this result by presenting another construction H2 and showing that any n-vertex, connected, r-uniform hypergraph without a Berge-path of length k, that contains more than |H2| hyperedges must be a sub-hypergraph of the extremal hypergraph H1, provided k is large enough compared to r.",

author = "D{\'a}niel Gerbner and Nagy, \{D{\'a}niel T.\} and Bal{\'a}zs Patk{\'o}s and Nika Salia and M{\'a}t{\'e} Vizer",

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

year = "2024",

month = may,

doi = "10.1016/j.ejc.2024.103930",

language = "English",

volume = "118",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Stability of extremal connected hypergraphs avoiding Berge-paths

AU - Gerbner, Dániel

AU - Nagy, Dániel T.

AU - Patkós, Balázs

AU - Salia, Nika

AU - Vizer, Máté

PY - 2024/5

Y1 - 2024/5

N2 - A Berge-path of length k in a hypergraph H is a sequence v1,e1,v2,e2,…,vk,ek,vk+1 of distinct vertices and hyperedges with vi,vi+1∈ei, for i≤k. Füredi, Kostochka and Luo, and independently Győri, Salia and Zamora determined the maximum number of hyperedges in an n-vertex, connected, r-uniform hypergraph that does not contain a Berge-path of length k provided k is large enough compared to r. They also determined the unique extremal hypergraph H1. We prove a stability version of this result by presenting another construction H2 and showing that any n-vertex, connected, r-uniform hypergraph without a Berge-path of length k, that contains more than |H2| hyperedges must be a sub-hypergraph of the extremal hypergraph H1, provided k is large enough compared to r.

AB - A Berge-path of length k in a hypergraph H is a sequence v1,e1,v2,e2,…,vk,ek,vk+1 of distinct vertices and hyperedges with vi,vi+1∈ei, for i≤k. Füredi, Kostochka and Luo, and independently Győri, Salia and Zamora determined the maximum number of hyperedges in an n-vertex, connected, r-uniform hypergraph that does not contain a Berge-path of length k provided k is large enough compared to r. They also determined the unique extremal hypergraph H1. We prove a stability version of this result by presenting another construction H2 and showing that any n-vertex, connected, r-uniform hypergraph without a Berge-path of length k, that contains more than |H2| hyperedges must be a sub-hypergraph of the extremal hypergraph H1, provided k is large enough compared to r.

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

U2 - 10.1016/j.ejc.2024.103930

DO - 10.1016/j.ejc.2024.103930

M3 - Article

AN - SCOPUS:85184031361

SN - 0195-6698

VL - 118

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103930

ER -