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.1007/978-3-030-83823-2_19

Stability of Extremal Connected Hypergraphs Avoiding Berge-Paths

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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

1 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 ₊ ₁ of distinct vertices and hyperedges with v_i ₊ ₁∈ e_i, e_i ₊ ₁ for all 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 subhypergraph of the extremal hypergraph H₁, provided k is large enough compared to r.

Original language	English
Title of host publication	Trends in Mathematics
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	117-122
Number of pages	6
DOIs	https://doi.org/10.1007/978-3-030-83823-2_19
State	Published - 2021
Externally published	Yes

Publication series

Name	Trends in Mathematics
Volume	14
ISSN (Print)	2297-0215
ISSN (Electronic)	2297-024X

Bibliographical note

Publisher Copyright:
© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

Berge-paths
Connectivity
Extremal hypergraph theory

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1007/978-3-030-83823-2_19

Cite this

@inbook{e97568f050cd4dda8f0d2a510df1086d,

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 + 1∈ ei, ei + 1 for all 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 subhypergraph of the extremal hypergraph H1, provided k is large enough compared to r.",

keywords = "Berge-paths, Connectivity, Extremal hypergraph theory",

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} 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2021",

doi = "10.1007/978-3-030-83823-2\_19",

language = "English",

series = "Trends in Mathematics",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "117--122",

booktitle = "Trends in Mathematics",

address = "Germany",

}

TY - CHAP

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 - 2021

Y1 - 2021

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 + 1∈ ei, ei + 1 for all 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 subhypergraph 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 + 1∈ ei, ei + 1 for all 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 subhypergraph of the extremal hypergraph H1, provided k is large enough compared to r.

KW - Berge-paths

KW - Connectivity

KW - Extremal hypergraph theory

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

U2 - 10.1007/978-3-030-83823-2_19

DO - 10.1007/978-3-030-83823-2_19

M3 - Chapter

AN - SCOPUS:85114099856

T3 - Trends in Mathematics

SP - 117

EP - 122

BT - Trends in Mathematics

PB - Springer Science and Business Media Deutschland GmbH

ER -

Stability of Extremal Connected Hypergraphs Avoiding Berge-Paths

Abstract

Publication series

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this