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 ϵ 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].
| Original language | English |
|---|---|
| Pages (from-to) | 2314-2327 |
| Number of pages | 14 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 31 |
| Issue number | 4 |
| DOIs | |
| State | Published - 2017 |
Funding
∗Received by the editors March 16, 2016; accepted for publication (in revised form) July 11, 2017; published electronically October 12, 2017. http://www.siam.org/journals/sidma/31-4/M106619.html Funding: The first author’s research was supported by OTKA grant PD-109537. The second author’s research was supported by University of Montana UGP grant 325341. †Hungarian Academy of Sciences, Alfréd Rényi Institute of Mathematics, P.O.B. 127, Budapest H-1364, Hungary ([email protected]). ‡Department of Mathematical Sciences, University of Montana, Missoula, MT 59812 ([email protected]).
| Funder number |
|---|
| 325341 |
| PD-109537 |
Keywords
- Berge hypergraphs
- Extremal graphs
- Extremal hypergraphs