The entropy lower-bound conjecture for graphs with a given degree sequence
The entropy lower-bound conjecture for graphs with a given degree sequence
Let be a strict graphic sequence of type , and let be the entropy function whose maximum is attained at . Write for the set of graphs with degree sequence . Entropy lower-bound conjecture. There exists a number independent of such that
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.