Balanced extensions of graphs and hypergraphs

Authors:

• Andrzej Ruciński,
• A. Vince

Abstract

For a hypergraph G with v vertices and e_i edges of size i, the average vertex degree is d(G)= ∑ie₁/v. Call balanced if d(H)≦d(G) for all subhypergraphs H of G. Let {Mathematical expression} A hypergraph F is said to be a balanced extension of G if G⊂F, F is balanced and d(F)=m(G), i.e. F is balanced and does not increase the maximum average degree. It is shown that for every hypergraph G there exists a balanced extension F of G. Moreover every r-uniform hypergraph has an r-uniform balanced extension. For a graph G let ext (G) denote the minimum number of vertices in any graph that is a balanced extension of G. If G has n vertices, then an upper bound of the form ext (G)1n² is proved. This is best possible in the sense that ext (G)>c₂n² for an infinite family of graphs. However for sufficiently dense graphs an improved upper bound ext (G)3n can be obtained, confirming a conjecture of P. Erdõs. © 1988 Akadémiai Kiadó.