The concise contingency-table realization conjecture

From papers

Let aNr\mathbf a\in\mathbb N^r and bNs\mathbf b\in\mathbb N^s have common size n=a=bn=|\mathbf a|=|\mathbf b|, and let CT(a,b)\operatorname{CT}(\mathbf a,\mathbf b) be the number of contingency tables with these margins. Contingency-table conciseness conjecture. For every k>0k>0, there exist vectors a,b\mathbf a,\mathbf b of size nn such that

CT(a,b)=k\operatorname{CT}(\mathbf a,\mathbf b)=k

and

nC(logk)cn\le C(\log k)^c

for some fixed C,c>0C,c>0. This asks for short unary-margin representations of every positive counting value and is open; the paper notes consequences for related counting functions.

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.