Arc-complexity conjecture for uniform matroids

Let r,nNr,n\to\mathbb{N} with nrn\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}Xr}.\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=(XT,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(nr).\mathrm{C}_A(U_{r,n})=r\cdot(n-r).

The displayed construction gives the upper bound CA(Ur,n)r(nr)\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.

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.