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

About 12 years old · traced to

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−ηn⋅log⁡(n)⋅eH1(p~)≤∣GD∣≤eH1(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.

References

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.