The bicircular-matroid basis conciseness conjecture
The bicircular-matroid basis conciseness conjecture
Let denote the number of bases of a matroid , and restrict 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 restricted to bicircular matroids is concise. Bicircular matroids give a natural concise presentation for a known -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
Sign in to submit a solution.
No solutions have been posted yet.