The entropy lower-bound conjecture for graphs with a given degree sequence

Let DD be a strict graphic sequence of type ε\varepsilon, and let H1(x)H_{1}(x) be the entropy function whose maximum is attained at p~\widetilde{\mathbf{p}}. Write GD\mathbb{G}^{D} for the set of graphs with degree sequence DD. Entropy lower-bound conjecture. There exists a number η>0\eta>0 independent of nn such that

eηnlog(n)eH1(p~)GDeH1(p~).e^{-\eta n\cdot\log(n)}\cdot e^{H_{1}(\widetilde{\mathbf{p}})}\leq\left|\mathbb{G}^{D}\right|\leq e^{H_{1}(\widetilde{\mathbf{p}})}.

The upper bound is the easy part and follows from the entropy estimate, while the lower bound is explicitly identified as open. This conjecture would provide the needed estimate for the number of graphs with the prescribed degree sequence.

Sources & referencesView supporting material

Primary source

Behzad Mehrdad, “Trees in Random Sparse Graphs with a Given Degree Sequence”, arXiv:1401.0220 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.