Sobre el grafo de intersección de una matriz 0, 1

G. R. ARGIROFFO; M. P. DOBSON; P. D. TORRES

Congreso; LVIII Reunión anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2008

Unión Matemática Argentina

Dada una matriz  $Min {0,1}^{m imes n}$, se definen su número de matching, $ u(M)=max{mathbf 1y: ; yin {0,1}^{m},; yMleq mathbf 1}$ y su número de cubrimiento $ au(M)=min{mathbf 1x: ; xin {0,1}^{n},; Mxgeq mathbf 1}$. Es claro que siempre se satisface que $ u(M)leq au(M)$.  Una matriz $M$ tiene la emph{propiedad de empaquetamiento} si $ u(M´)= au(M´)$ se satisface para todo menor $M´$ de $M$ cite{CGM}. La matrices con la propiedad de empaquetamiento no están, hasta el momento, caracterizadas por menores prohibidos, aunque en cite{CGM}, se presentan conjeturas sobre una tal caracterización.En este trabajo se introduce el emph{grafo de intersección} de una matriz $0,1$ $M$, $L(M)$, como el grafo de intersección de las filas de $M$, interpretadas como vectores de incidencia de subconjuntos de ${1,ldots,n}$, y en este caso obtenemos que egin{equation}label{eee} u(M)=alpha(L(M))leqkappa(L(M))leq au(M),  end{equation}donde $alpha(L(M))$ y $kappa(L(M))$ representan el número de estabilidad y el número de cubrimiento de vértices por cliques del grafo $L(M)$, respectivamente. Diremos, entonces, que una matriz $M$ es emph{linda} si $alpha(L(M´))=kappa(L(M´))$ para todo menor $M´$ de $M$.A partir de estas definiciones, vemos que toda matriz con la propiedad de empaquetamiento, es linda.  Esto último, nos permite obtener propiedades de las matrices con la propiedad de empaquetamiento, a través de propiedades de sus grafos de intersección. Esto  llevó al estudio de las desigualdades en eqref{eee}. En particular, egin{enumerate}item Hallamos una condición suficiente para que $kappa(L(M))= au(M)$.item Hallamos una condición suficiente para que una matriz linda tenga la propiedad de empaquetamiento.item Dada una matriz $M$, definimos matrices $mathcal E(G)$ y $mathcal Q(G)$, extremales en el siguiente sentido:egin{enumerate}item si $mathcal E(G)$ packs, entonces $M$ packs para toda matriz $M$ tal que $L(M)=G$. item si $M$  packs, entonces $mathcal Q(G)$ packs.end{enumerate}end{enumerate}