Unbounded arc-complexity conjecture for gammoids
Unbounded arc-complexity conjecture for gammoids
Let denote the arc complexity of a gammoid , where is its ground-set size. Unbounded arc-complexity conjecture for gammoids. For every there is a gammoid such that
This conjecture asserts that no universal linear bound on arc complexity holds for all gammoids. Immediately before the statement, the paper asks whether, for each finite field , there is a constant such that every gammoid representable over satisfies ; the conjecture gives a contrary unboundedness assertion, but no resolution is supplied here.
Sources & referencesView supporting material
Primary source
Immanuel Albrecht, “Duality Respecting Representations and Compatible Complexity Measures for Gammoids”, arXiv:1807.00588 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.