Connectivity of the lifts of a greedoid
Summary: Recently, attempts were made to generalize the undirected branching greedoid to a greedoid whose feasible sets consist of sets of edges containing the root satisfying additional size restrictions. Although this definition does not always result in a greedoid, the lift of the undirected branching greedoid has the properties desired by the authors. The \(k\)th lift of a greedoid has sets whose nullity is at most \(k\) in the original greedoid. We prove that if the greedoid is \(n\)-connected, then its lift is also \(n\)-connected. Additionally, for any cut-vertex \(v\) and cut-edge \(e\) of a graph \(\Gamma\), let \(C(v)\) be the component of \(\Gamma\setminus v\) containing the root and \(C(e)\) be the component of \(\Gamma\setminus e\) containing the root. We prove that if the \(k\)th lift of the undirected branching greedoid is 2-connected, then \[ \begin{align*}{ |{E(C(v))}|&<|{V(C(v))}|+k-1\text{ and }\cr |{E(C(e))}|&>|{E(\Gamma)}|-{k}-2.\cr }\end{align*} \] We also give examples indicating that no sufficient conditions for the \(k\)th lift to be 2-connected exists similar to these necessary conditions.
This page was built for publication: Connectivity of the lifts of a greedoid
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372894)
