The bicircular-matroid basis conciseness conjecture

From papers

Let b(M)b(M) denote the number of bases of a matroid MM, and restrict bb to bicircular matroids. A counting function is concise if every positive integer occurs on an input of size polynomial in the logarithm of that integer. Bicircular-matroid basis conjecture. The function bb restricted to bicircular matroids is concise. Bicircular matroids give a natural concise presentation for a known #P\#\mathrm P-complete basis-counting problem, but the stronger value-realization bound remains open.

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.