Unbounded arc-complexity conjecture for gammoids

At least 7 years old · documented by

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 q∈Qq\in\mathbb{Q} there is a gammoid M=(E,I)M=(E,\mathcal{I}) such that

CA(M)≥q⋅∣E∣.\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)≤cF∣E∣\mathrm{C}_A(M)\leq c_{\mathbb{F}}|E|; the conjecture gives a contrary unboundedness assertion, but no resolution is supplied here.

References

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.