TOPICS
Search

Berge Hypergraph


A Berge F hypergraph, where F is a graph, is a hypergraph B for which there is a bijection phi:E(F)->E(B) such that

 e subset= phi(e)
(1)

for every graph edge e of F. The vertices of each graph edge are therefore contained in its corresponding hyperedge, but a hyperedge may contain additional vertices. A hypergraph is Berge F-free if it contains no Berge F as a subhypergraph.

For k>=3, a Berge cycle of length k is an alternating sequence of distinct vertices and distinct hyperedges

 v_1,e_1,v_2,e_2,...,v_k,e_k,v_1
(2)

with v_i,v_(i+1) in e_i, where subscripts are read cyclically. Thus it is a Berge C_k. Dong et al. (2026) give spectral radius bounds for Berge C_5-free linear hypergraphs.

A Berge path on k vertices is an alternating sequence v_1,e_1,v_2,e_2,...,e_(k-1),v_k of distinct vertices and distinct hyperedges with v_i,v_(i+1) in e_i for 1<=i<k. It has length k-1 and is a Berge P_k, where P_k is the path graph on k vertices.

Li and Luo (2026) determined a connected extremal number for these paths. Let ex_r^(conn)(n,BP_k) be the largest number of hyperedges in a connected n-vertex r-uniform hypergraph with no Berge path on k vertices. Here every hyperedge has exactly r vertices, repeated hyperedges are excluded, and connected means that any two vertices are joined by a Berge path. For integers r and k with r+3<=k<=2r+1 and n>=max{(r-1)^2,k-3+2(k-3; r-1)}, Li and Luo (2026) proved

 ex_r^(conn)(n,BP_k)=n-(k-3)+(k-3; r).
(3)

The bound is attained by taking all r-element subsets of a fixed set of k-3 vertices as hyperedges and giving each remaining graph vertex one hyperedge containing it and r-1 of the fixed vertices.


See also

Graph, Hypergraph, Linear Hypergraph

Explore with Wolfram|Alpha

References

Dong, B.; Duan, C.; and Wang, L. "Bounds on the Spectral Radii of Berge C_5-Free Linear r-Graphs." Elec. J. Combin. 33, P3.82, 2026. https://doi.org/10.37236/12561.Gerbner, D. and Palmer, C. "Extremal Results for Berge Hypergraphs." SIAM J. Disc. Math. 31, 2314-2327, 2017. https://doi.org/10.1137/16M1066191.Li, Y. and Luo, R. "The Turán Number of Berge Paths in Connected Hypergraphs." 23 Oct 2026. https://arxiv.org/abs/2610.32875.

Cite this as:

Weisstein, Eric W. "Berge Hypergraph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BergeHypergraph.html

Subject classifications