Arc-complexity conjecture for uniform matroids

About 8 years old · traced to

Let r,n→Nr,n\to\mathbb{N} with n≥rn\geq r. The uniform matroid of rank rr on nn elements is Ur,n=({1,2,…,n},Ir,n)U_{r,n}=({\{1,2,\ldots,n\}},\mathcal{I}_{r,n}), where

Ir,n={X⊆{1,2,…,n}∣∣X∣≤r}.\mathcal{I}_{r,n}=\{X\subseteq\{1,2,\ldots,n\}\mid |X|\leq r\}.

Let T={1,2,…,r}T=\{1,2,\ldots,r\}, X={r+1,r+2,…,n}X=\{r+1,r+2,\ldots,n\}, and D=(X∪T,X×T)D=(X\cup T,X\times T). For a gammoid MM, let CA(M)\mathrm{C}_A(M) denote its arc complexity. Arc-complexity conjecture for uniform matroids.

CA(Ur,n)=r⋅(n−r).\mathrm{C}_A(U_{r,n})=r\cdot(n-r).

The displayed construction gives the upper bound CA(Ur,n)≤r⋅(n−r)\mathrm{C}_A(U_{r,n})\leq r\cdot(n-r); 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.

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.