Arc-complexity conjecture for uniform matroids
Arc-complexity conjecture for uniform matroids
Let with . The uniform matroid of rank on elements is , where
Let , , and . For a gammoid , let denote its arc complexity. Arc-complexity conjecture for uniform matroids.
The displayed construction gives the upper bound ; the conjecture asserts that this representation is optimal. The authors state that they were unable to find a known graph- or digraph-theoretic result implying the matching lower bound.
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.