The concise degree-sequence graph-counting conjecture

From papers

Let d=(d1,,dn)Nn\mathbf d=(d_1,\ldots,d_n)\in\mathbb N^n satisfy 0din10\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

nC(logk)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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.