Balanced extensions of graphs and hypergraphs (Q805632)

For a hypergraph G with v vertices and \(e_ i\) edges of size i, the average vertex degree is \(d(G)=\Sigma ie_ i/v\). Call G balanced if d(H)\(\leq d(G)\) for all subhypergraphs H of G. Let \[ m(G)=\max_{H\subseteq G}d(H). \] A hypergraph F is said to be a balanced extension of G if \(G\subset 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)<c_ 1n^ 2\) is proved. This is best possible in the sense that \(ext(G)>c_ 2n^ 2\) for an infinite family of graphs. However for sufficiently dense graphs an improved upper bound \(ext(G)<c_ 3n\) can be obtained, confirming a conjecture of P. Erdős.