Rango de matroide

En la teoría matemática de los matroides , el rango de un matroide es el tamaño máximo de un conjunto independiente en el matroide. El rango de un subconjunto S de elementos del matroide es, de manera similar, el tamaño máximo de un subconjunto independiente de S , y la función de rango del matroide asigna conjuntos de elementos a sus rangos.

La función de rango es uno de los conceptos fundamentales de la teoría de matroides mediante el cual se pueden axiomatizar. Las funciones de rango de matroides forman una subclase importante de las funciones de conjunto submodulares . Las funciones de rango de matroides definidas a partir de ciertos otros tipos de objetos matemáticos, como grafos no dirigidos , matrices y extensiones de campo , son importantes dentro del estudio de esos objetos.

Ejemplos

En todos los ejemplos, E es el conjunto base del matroide y B es un subconjunto de E.

Sea M el matroide libre , donde los conjuntos independientes son todos subconjuntos de E. Entonces la función de rango de M es simplemente: r ( B ) = | B |.
Sea M un matroide uniforme , donde los conjuntos independientes son los subconjuntos de E con k elementos como máximo , para algún entero k . Entonces la función de rango de M es: r ( B ) = min( k , | B |).
Sea M un matroide de partición : los elementos de E están particionados en categorías, cada categoría c tiene capacidad k _c , y los conjuntos independientes son aquellos que contienen como máximo k _c elementos de la categoría c . Entonces la función de rango de M es: r ( B ) = suma _c min( k _c , | B _c |) donde B _c es el subconjunto B contenido en la categoría c .
Sea M un matroide gráfico , donde los conjuntos independientes son todos los conjuntos de aristas acíclicos ( bosques ) de algún grafo fijo no dirigido G. Entonces, la función de rango r ( B ) es el número de vértices en el grafo, menos el número de componentes conectados de B (incluidos los componentes de un solo vértice).

Propiedades y axiomatización

La función de rango de un matroide obedece las siguientes propiedades.

(R1) El valor de la función de rango es siempre un entero no negativo y el rango del conjunto vacío es 0.

(R2) Para dos subconjuntos cualesquiera y de , . Es decir, el rango es una función de conjunto submodular . ${\estilo de visualización A}$ ${\estilo de visualización B}$ ${\estilo de visualización E}$ $r(A\cup B)+r(A\cap B)\leq r(A)+r(B)$

(R3) Para cualquier conjunto y elemento , . ${\estilo de visualización A}$ ${\estilo de visualización x}$ $r(A)\leq r(A\cup \{x\})\leq r(A)+1$

Estas propiedades pueden usarse como axiomas para caracterizar la función de rango de los matroides: cada conjunto submodular de valor entero funciona en los subconjuntos de un conjunto finito que obedece las desigualdades para todos y es la función de rango de un matroide. ^[1]^[2] $r(A)\leq r(A\cup \{x\})\leq r(A)+1$ ${\estilo de visualización A}$ ${\estilo de visualización x}$

Las propiedades anteriores implican propiedades adicionales:

Si , entonces . Es decir, el rango es una función monótona . $A\subconjunto B\subconjunto E$ $r(A)\leq r(B)\leq r(E)$
$r(A)\leq |A|$ .

Otras propiedades de matroides de rango

La función de rango se puede utilizar para determinar otras propiedades importantes de un matroide:

Un conjunto es independiente si y sólo si su rango es igual a su cardinalidad, y dependiente si y sólo si tiene mayor cardinalidad que rango. ^[3]
Un conjunto no vacío es un circuito si su cardinalidad es igual a uno más su rango y cada subconjunto formado al eliminar un elemento del conjunto tiene el mismo rango. ^[3]
Un conjunto es una base si su rango es igual tanto a su cardinalidad como al rango del matroide. ^[3]
Un conjunto es cerrado si es máximo para su rango, en el sentido de que no existe otro elemento que pueda agregarse a él manteniendo el mismo rango.
La diferencia se denomina nulidad del subconjunto y es el número mínimo de elementos que se deben eliminar para obtener un conjunto independiente. ^[4] $|A|-r(A)$ ${\estilo de visualización A}$ ${\estilo de visualización A}$
El corank de un subconjunto puede referirse al menos a dos cantidades diferentes: algunos autores lo utilizan para referirse al rango de en el matroide dual, , mientras que otros autores utilizan corank para referirse a la diferencia . ${\estilo de visualización A}$ ${\estilo de visualización A}$ $r^{*}(A)=|A|+r(E\setminus A)-r(E)$ $r(E)-r(A)$

Rangos de matroides especiales

En teoría de grafos , el rango de circuito (o número ciclomático) de un grafo es el corank del matroide gráfico asociado ; mide el número mínimo de aristas que deben eliminarse del grafo para que las aristas restantes formen un bosque. ^[5] Varios autores han estudiado la complejidad parametrizada de los algoritmos de grafos parametrizados por este número. ^[6]^[7]

En álgebra lineal , el rango de un matroide lineal definido por la independencia lineal de las columnas de una matriz es el rango de la matriz, ^[8] y también es la dimensión del espacio vectorial abarcado por las columnas.

En álgebra abstracta , el rango de un matroide definido a partir de conjuntos de elementos en una extensión de campo L / K por independencia algebraica se conoce como grado de trascendencia . ^[9]

Las funciones de rango de Matroid son funciones de utilidad

Las funciones de rango matroide (MRF) se han utilizado para representar funciones de utilidad de agentes en problemas de asignación justa de ítems . Si la función de utilidad del agente es una MRF, significa que:

La utilidad del agente tiene rendimientos decrecientes (esto se deduce del hecho de que la MRF es una función submodular);
La utilidad marginal del agente para cada artículo es dicotómica (binaria): 0 o 1. Es decir, agregar un artículo a un paquete no agrega ninguna utilidad o agrega una utilidad de 1.

Se conocen las siguientes soluciones para esta configuración:

Babaioff, Ezra y Feige ^[10] diseñan un mecanismo determinista de tiempo polinomial veraz llamado Igualitario Priorizado, que produce una asignación dominante de Lorenz, que en consecuencia también es EFX _{0 , maximiza el producto de las utilidades, alcanza}una participación maximin de 1/2 fracción y alcanza la participación maximin completa cuando las valoraciones son aditivas. Con prioridades aleatorias, este mecanismo también está libre de envidia ex ante . También estudian valoraciones e -dicotómicas, en las que la utilidad marginal es no positiva o está en el rango [1,1+ e ].
Benabbou, Chakraborty, Igarashi y Zick ^[11] muestran que, en este contexto, cada asignación óptima de Pareto maximiza la suma de utilidades (el bienestar utilitarista ), el conjunto de asignaciones que maximizan una función estrictamente cóncava simétrica f sobre todas las asignaciones de suma máxima no depende de la elección de f , y todas estas asignaciones que maximizan f son EF1. Esto implica que las asignaciones de máximo producto son las asignaciones óptimas de leximin , y todas son de suma máxima y EF1. También presentan un algoritmo de tiempo polinomial que calcula una asignación de suma máxima y EF1 (que no necesariamente maximiza una función cóncava), y un algoritmo de tiempo polinomial que maximiza una función cóncava para el caso especial de MRF basadas en la correspondencia de cardinalidad máxima en grafos bipartitos.

Las funciones de rango matroide son una subclase de las valoraciones sustitutivas brutas .

Véase también

Oráculo de rango

Referencias

^ Shikare, MM; Waphare, BN (2004), Optimización combinatoria, Alpha Science Int'l Ltd., pág. 155, ISBN 9788173195600.
^ Welsh, DJA (2010), Teoría matroide , Publicaciones Courier Dover, p. 8, ISBN 9780486474397.
^ abc Oxley (2006), pág. 25.
^ Oxley (2006), pág. 34.
^ Berge, Claude (2001), "Número ciclomático", La teoría de grafos, Courier Dover Publications, págs. 27-30, ISBN 9780486419756.
^ Coppersmith, Don ; Vishkin, Uzi (1985), "Resolución de problemas NP-hard en 'casi árboles': cobertura de vértices", Discrete Applied Mathematics , 10 (1): 27–45, doi : 10.1016/0166-218X(85)90057-5 , Zbl 0573.68017 .
^ Fiala, Jiří; Kloks, tonelada; Kratochvíl, Jan (2001), "Complejidad de parámetros fijos de etiquetas λ", Matemáticas aplicadas discretas , 113 (1): 59–72, doi : 10.1016/S0166-218X(00)00387-5 , Zbl 0982.05085.
^ Oxley, James G. (2006), Teoría de matroides , Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pág. 81, ISBN 9780199202508.
^ Lindström, B. (1988), "Matroides algebraicas y no algebraicas", Combinatoria algebraica, extremal y métrica, 1986 (Montreal, PQ, 1986) , London Math. Soc. Lecture Note Ser., vol. 131, Cambridge: Cambridge Univ. Press, págs. 166-174, MR 1052666.
^ Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (27 de julio de 2020). "Mecanismos justos y veraces para valoraciones dicotómicas". arXiv : 2002.10704 [cs.GT].
^ Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). Encontrar asignaciones justas y eficientes cuando las valoraciones no cuadran . Apuntes de clase en informática. Vol. 12283. págs. 32–46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN . 978-3-030-57979-1. Número de identificación del sujeto 208328700.

[1] Shikare, MM; Waphare, BN (2004), Optimización combinatoria, Alpha Science Int'l Ltd., pág. 155, ISBN 9788173195600.

[2] Welsh, DJA (2010), Teoría matroide , Publicaciones Courier Dover, p. 8, ISBN 9780486474397.

[o25-3] Oxley (2006), pág. 25.

[4] Oxley (2006), pág. 34.

[5] Berge, Claude (2001), "Número ciclomático", La teoría de grafos, Courier Dover Publications, págs. 27-30, ISBN 9780486419756.

[6] Coppersmith, Don ; Vishkin, Uzi (1985), "Resolución de problemas NP-hard en 'casi árboles': cobertura de vértices", Discrete Applied Mathematics , 10 (1): 27–45, doi : 10.1016/0166-218X(85)90057-5 , Zbl 0573.68017 .

[7] Fiala, Jiří; Kloks, tonelada; Kratochvíl, Jan (2001), "Complejidad de parámetros fijos de etiquetas λ", Matemáticas aplicadas discretas , 113 (1): 59–72, doi : 10.1016/S0166-218X(00)00387-5 , Zbl 0982.05085.

[8] Oxley, James G. (2006), Teoría de matroides , Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pág. 81, ISBN 9780199202508.

[9] Lindström, B. (1988), "Matroides algebraicas y no algebraicas", Combinatoria algebraica, extremal y métrica, 1986 (Montreal, PQ, 1986) , London Math. Soc. Lecture Note Ser., vol. 131, Cambridge: Cambridge Univ. Press, págs. 166-174, MR 1052666.

[10] Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (27 de julio de 2020). "Mecanismos justos y veraces para valoraciones dicotómicas". arXiv : 2002.10704 [cs.GT].

[11] Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). Encontrar asignaciones justas y eficientes cuando las valoraciones no cuadran . Apuntes de clase en informática. Vol. 12283. págs. 32–46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN . 978-3-030-57979-1. Número de identificación del sujeto 208328700.