The concise contingency-table realization conjecture

About 3 years old · traced to

Let a∈Nr\mathbf a\in\mathbb N^r and b∈Ns\mathbf b\in\mathbb N^s have common size n=∣a∣=∣b∣n=|\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

n≤C(log⁡k)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.

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.