DeVos–Kwon–Oum branch-depth obstruction conjecture for matroids

A matroid is a matroid, and M(Fn)M(F_n) denotes the cycle matroid of the fan FnF_n, formed from a star K1,nK_{1,n} together with a path through the nn leaves. The uniform matroid Un,2nU_{n,2n} has rank nn on 2n2n elements. Branch-depth is the matroid parameter described in the source.

DeVos–Kwon–Oum's branch-depth obstruction conjecture. For every positive integer nn, there is an integer dd such that every matroid of branch-depth at least dd contains a minor isomorphic to M(Fn)M(F_n) or Un,2nU_{n,2n}.

DeVos, Kwon, and Oum introduced branch-depth as an analogue of tree-depth for graphs. Their results show that fan matroids have branch-depth Θ(logn/loglogn)\Theta(\log n/\log\log n), so they are obstructions to bounded branch-depth; the conjecture asserts that, together with the uniform matroids Un,2nU_{n,2n}, these are the only required minor obstructions.

Sources & referencesView supporting material

Primary source

J. Pascal Gollin, Kevin Hendrey, Dillon Mayhew and Sang-il Oum, “Obstructions for bounded branch-depth in matroids”, arXiv:2003.13975 (2021).

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.