The concise degree-sequence graph-counting conjecture

About 3 years old · traced to

Let d=(d1,…,dn)∈Nn\mathbf d=(d_1,\ldots,d_n)\in\mathbb N^n satisfy 0≤di≤n−10\le d_i\le n-1, and let c(d)c(\mathbf d) be the number of simple graphs on vertices v1,…,vnv_1,\ldots,v_n with deg⁡(vi)=di\deg(v_i)=d_i for every ii. Degree-sequence conciseness conjecture. For every k>0k>0, there exists d\mathbf d such that c(d)=kc(\mathbf d)=k and

n≤C(log⁡k)cn\le C(\log k)^c

for some fixed C,c>0C,c>0. The decision problem for graphical degree sequences is polynomial-time decidable, while the conjectured concise value realization is open and can be viewed as a binary symmetric contingency-table problem.

References

Primary source

Swee Hong Chan and Igor Pak, “Computational complexity of counting coincidences”, arXiv:2308.10214 (2024).

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.