Name
Abstract | ||
|---|---|---|
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 is an element of E(G) we have e subset of 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 Kovari-Sos-Turan theorem. In case G is C-4, we improve the bounds given by Gyori and Lemons |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1137/16M1066191 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Berge hypergraphs,extremal graphs,extremal hypergraphs | Journal | 31 |
Issue | ISSN | Citations |
4 | 0895-4801 | 1 |
PageRank | References | Authors |
0.36 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Gerbner | 1 | 46 | 21.61 |
| Cory Palmer | 2 | 44 | 10.33 |