The concise degree-sequence graph-counting conjecture
The concise degree-sequence graph-counting conjecture
From papers
Let satisfy , and let be the number of simple graphs on vertices with for every . Degree-sequence conciseness conjecture. For every , there exists such that and
for some fixed . 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
Sign in to submit a solution.
No solutions have been posted yet.