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

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

Mendoza

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

Unión Matemática Argentina

Dada una matriz  M in {0,1}^{m times n}, se definen su número de matching, u(M)=max{1y: y in {0,1}^{m}, yM leq 1} y su número de cubrimiento a(M)=min{1x: x in {0,1}^{n}, Mx geq 1}. Es claro que siempre se satisface que u(M) leq a(M). Una matriz M tiene la propiedad de empaquetamiento si u(M´)= a(M´) se satisface para todo menor M´ de M. La matrices con la propiedad de empaquetamiento no están, hasta el momento, caracterizadas por menores prohibidos, aunque se presentan conjeturas sobre una tal caracterización.En este trabajo se introduce el 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  u(M)=alpha(L(M)) leq kappa(L(M)) leq a(M),  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 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 diversas desigualdades. En particular, Hallamos una condición suficiente para que $kappa(L(M))= au(M)$.Hallamos una condición suficiente para que una matriz linda tenga la propiedad de empaquetamiento.Dada una matriz M, definimos matrices E(G) y Q(G), extremales en el siguiente sentido:si E(G) packs, entonces M packs para toda matriz M tal que L(M)=G. si M  packs, entonces Q(G) packs.