​​

بالتعاون مع مركز البحوث بكلية العلوم وفي إطار سيمنارات حوافز النشر العالمي يقدم د. براهيم شورار من قسم الرياضيات والإحصاء عرضا بعنوان:

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

وذلك يوم الثلاثاء القادم 10/06/1441 هـ الموافق 04/02/2020 م الساعة 09:10 بالقاعة 2-031A إن شاء الله وفيما يلي ملخص العرض.

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.​