NDA
Bejelentkezés
Kapcsolat
Extremal results for berge hypergraphs |
Tartalom: | http://real.mtak.hu/74181/ |
---|---|
Archívum: | MTA Könyvtár |
Gyűjtemény: |
Status = Published
Type = Article |
Cím: |
Extremal results for berge hypergraphs
|
Létrehozó: |
Gerbner, Dániel
Palmer, Cory
|
Kiadó: |
Society for Industrial and Applied Mathematics (SIAM)
|
Dátum: |
2017
|
Téma: |
QA166-QA166.245 Graphs theory / gráfelmélet
|
Tartalmi leírás: |
Let E(G) and V (G) denote the edge set and vertex set of a (hyper)graph G. Let G be a graph and H be a hypergraph. We say that a hypergraph H is a Berge-G if there is a bijection f : E(G) → E(H) such that for each e ϵ E(G) we have e ? f(e). This generalizes the established definitions of "Berge path" and "Berge cycle" to general graphs. For a fixed graph G we examine the maximum possible size of a hypergraph with no Berge-G as a subhypergraph. In the present paper we prove general bounds for this maximum when G is an arbitrary graph. We also consider the specific case when G is a complete bipartite graph and prove an analogue of the K?ovári-Sós-Turán theorem. In case G is C4, we improve the bounds given by Gy?ori and Lemons [Discrete Math., 312, (2012), pp. 1518-1520]. © 2017 Society for Industrial and Applied Mathematics.
|
Nyelv: |
angol
|
Típus: |
Article
PeerReviewed
info:eu-repo/semantics/article
|
Formátum: |
text
|
Azonosító: |
Gerbner, Dániel and Palmer, Cory (2017) Extremal results for berge hypergraphs. SIAM JOURNAL ON DISCRETE MATHEMATICS, 31 (4). pp. 2314-2327. ISSN 0895-4801
|
Kapcsolat: |
https://doi.org/10.1137/16M1066191
MTMT:3332601; doi:10.1137/16M1066191
|