A note on saturation for Berge-\(G\) hypergraphs. (English) Zbl 1416.05196
Summary: For a graph \(G=(V,E)\), a hypergraph \(H\) is called Berge-\(G\) if there is a hypergraph \(H^\prime\), isomorphic to \(H\), so that \(V(G)\subseteq V(H^\prime)\) and there is a bijection \(\phi : E(G) \rightarrow E(H\prime)\) such that for each \(e\in E(G)\), \(e \subseteq \phi (e)\). The set of all Berge-\(G\) hypergraphs is denoted \(\mathcal {B}(G)\). A hypergraph \(H\) is called Berge-\(G\) saturated if it does not contain any subhypergraph from \(\mathcal {B}(G)\), but adding any new hyperedge of size at least 2 to \(H\) creates such a subhypergraph. Since each Berge-\(G\) hypergraph contains |\(E\)(\(G\))| hypergedges, it follows that each Berge-\(G\) saturated hypergraph must have at least \(|E(G)|-1\) edges. We show that for each graph \(G\) that is not a certain star and for any \(n\ge |V(G)|\), there are Berge-\(G\) saturated hypergraphs on \(n\) vertices and exactly \(|E(G)|-1\) hyperedges. This solves a problem of finding a saturated hypergraph with the smallest number of edges exactly.
MSC:
| 05C65 | Hypergraphs |
References:
| [1] | Axenovich, M., Gyárfás, A.: A note on Ramsey numbers for Berge-G hypergraphs. Discrete Math. 342(5), 1245-1252 (2019) · Zbl 1407.05168 · doi:10.1016/j.disc.2019.01.011 |
| [2] | English, S., Graber, N., Kirkpatrick, P., Methuku, A., Sullivan, E.C.: Saturation of Berge hypergraphs (2017). arXiv:1710.03735 · Zbl 1414.05209 |
| [3] | English, S., Gerbner, D., Methuku, A., Tait, M.: Linearity of saturation for Berge hypergraphs. European J. Combin. 78, 205-213 (2019) · Zbl 1414.05208 · doi:10.1016/j.ejc.2019.02.002 |
| [4] | Faudree, J., Faudree, R., Schmitt, J.: A survey of minimum saturated graphs. Electron. J. Combin. 1000, 19-29 (2011) · Zbl 1222.05113 |
| [5] | Gerbner, D., Palmer, C.: Extremal results for Berge-hypergraphs. SIAM J. Discrete Math. 31(4), 2314-2327 (2015) · Zbl 1372.05106 · doi:10.1137/16M1066191 |
| [6] | Grósz, D., Methuku, A., Tompkins, C.: Uniformity thresholds for the asymptotic size of extremal Berge-\[FF\]-free hypergraphs (2018). arXiv:1803.01953v1 · Zbl 1378.05145 |
| [7] | Gyárfás, A., Lehel, J., Sárközy, G.N., Schelp, R.H.: Monochromatic Hamiltonian Berge cycles in colored complete uniform hypergraphs. J. Combin. Theory B 98, 342-358 (2008) · Zbl 1140.05028 · doi:10.1016/j.jctb.2007.07.002 |
| [8] | Gyárfás, A., Sárközy, G.N.: The \[33\]-colour Ramsey number of a \[33\]-uniform Berge cycle. Combin. Probab. Comput. 20, 53-71 (2011) · Zbl 1215.05111 · doi:10.1017/S0963548310000209 |
| [9] | Győri, E.: Triangle-free hypergraphs. Combin. Probab. Comput. 15, 185-191 (2006) · Zbl 1082.05064 · doi:10.1017/S0963548305007108 |
| [10] | Kászonyi, L., Tuza, Z.: Saturated graphs with minimal number of edges. J. Graph Theory 10(2), 203-210 (1986) · Zbl 0593.05041 · doi:10.1002/jgt.3190100209 |
| [11] | Palmer, C., Tait, M., Timmons. C., Wagner, A. Z.: Turán numbers for Berge-hypergraphs and related extremal problems. Discrete Math. 342(6), 1553-1563 (2019) · Zbl 1414.05212 |
| [12] | Pikhurko, O.: The minimum size of saturated hypergraphs. Combin. Probab. Comput. 8(5), 483-492 (1999) · Zbl 0938.05035 · doi:10.1017/S0963548399003971 |
| [13] | Pikhurko, O.: Results and open problems on minimum saturated hypergraphs. ARS Combin. 72, 111-127 (2004) · Zbl 1069.05042 |
| [14] | Winter, C.: Berge saturation of non-uniform hypergraphs, Bachelor Thesis. Karlsruhe Institute of Technology (2018) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
