Balanced extensions of graphs and hypergraphs

For a hypergraphG withv vertices ande _i edges of sizei, the average vertex degree isd(G)= ∑ie ₁/v. Callbalanced ifd(H)≦d(G) for all subhypergraphsH ofG. Let $$m(G) = \mathop {\max }\limits_{H \subseteqq G} d(H).$$ A hypergraphF is said to be abalanced extension ofG ifG?F, F is balanced andd(F)=m(G), i.e.F is balanced and does not increase the maximum average degree. It is shown that for every hypergraphG there exists a balanced extensionF ofG. Moreover everyr-uniform hypergraph has anr-uniform balanced extension. For a graphG let ext (G) denote the minimum number of vertices in any graph that is a balanced extension ofG. IfG hasn vertices, then an upper bound of the form ext(G) ₁ n ² 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) ₃ n can be obtained, confirming a conjecture of P. Erdõs.