Unbounded arc-complexity conjecture for gammoids

Let CA(M)\mathrm{C}_A(M) denote the arc complexity of a gammoid M=(E,I)M=(E,\mathcal{I}), where E|E| is its ground-set size. Unbounded arc-complexity conjecture for gammoids. For every qQq\in\mathbb{Q} there is a gammoid M=(E,I)M=(E,\mathcal{I}) such that

CA(M)qE.\mathrm{C}_A(M)\geq q\cdot |E|.

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 F\mathbb{F}, there is a constant cFc_{\mathbb{F}} such that every gammoid representable over F\mathbb{F} satisfies CA(M)cFE\mathrm{C}_A(M)\leq c_{\mathbb{F}}|E|; 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

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.