Densest hypergraph with bounded vertex degree.

37 Views Asked by At

Given integer $m$, what is the maximal number $d$, such that there exists a hypergraph with vertices of degree at most $d$, and the number of hyperedges is $d \cdot m \cdot const$?

Using k-uniform hypergraphs one can show that $d \geq m^{c}$ for a constant $c$, but can $d$ be even larger? Say, super-polynomial in $m$? or even $2^{O(m)}$?

A degree of a vertex is the number of hyperedges that contain it.