​تحت إشراف قسم الرياضيات والإحصاء وبالتعاون مع مركز البحوث بالكلية أقيم يوم الثلاثاء ١٠ / ٦ / ١٤٤١هـ سيمنار بعنوان:

A short proof of a min-max relation for ​the bases packing of a matroid​

قدمه د.براهيم شورار وذلك في تمام الساعة 9:10 ص في قاعة 2-31A .

Abstract:

Let E be a finite set, and M be a matroid defined on E. Given $w\in R_+^E$, we use the notations (w-maximum bases packing for the first one): $\lambda (w)=Max \{\sum_{B  basis}\lambda_B$ such that $\sum_{B\ni e} \lambda_B \leq w(e)$ for any $e\in E$, and $\lambda_B\geq 0$ for any basis $B\}$, and $w_{\ell}=Min\{ \frac{w(E)-w(U)}{r(E)-r(U)}$ such that $U\subset E$ and $r(U)\leq r(E)-1\}$.

In this talk, we present a short proof for the known min-max relation $\lambda (w)=w_{\ell}$. Moreover, we prove that the minimum $w_{\ell}$ can be restricted to single elements and semi locked subsets only. A subset $L\subset E$ is semi locked in $M$ if $M^*|(E\backslash L)$ is closed and 2-connected, and $min\{r(L), r^*(E\backslash L)\} \geq 2$. We deduce then a polynomial algorithm to compute $w_{\ell}$ in a large class of matroids by using a matroid oracle related to semi locked subsets.​