stringtranslate.com

Desigualdad de Ingleton

En matemáticas, la desigualdad de Ingleton es una desigualdad que se satisface por la función de rango de cualquier matroide representable . En este sentido, es una condición necesaria para la representabilidad de un matroide sobre un cuerpo finito. Sea M un matroide y ρ su función de rango, la desigualdad de Ingleton establece que para cualesquiera subconjuntos X 1 , X 2 , X 3 y X 4 en el soporte de M , la desigualdad

ρ ( X 1 )+ ρ ( X 2 )+ ρ ( X 1 ∪ X 2 ∪ X 3 )+ ρ ( X 1 ∪ X 2 ∪ X 4 )+ ρ ( X 3 ∪ X 4 ) ≤ ρ ( X 1 ∪ X 2 )+ ρ ( X 1 ∪ X 3 )+ ρ ( X 1 ∪ X 4 )+ ρ ( X 2 ∪ X 3 )+ ρ ( X 2 ∪ X 4 ) se cumple.

Aubrey William Ingleton , un matemático inglés, escribió un importante artículo en 1969 [1] en el que examinó el problema de representabilidad en matroides. Aunque el artículo es principalmente expositivo, en este artículo Ingleton enunció y demostró la desigualdad de Ingleton, que ha encontrado aplicaciones interesantes en la teoría de la información , la teoría de matroides y la codificación de redes . [2]

Importancia de la desigualdad

Existen conexiones interesantes entre los matroides , la región de entropía y la teoría de grupos . Algunas de esas conexiones se revelan en la desigualdad de Ingleton.

Tal vez la aplicación más interesante de la desigualdad de Ingleton se refiere al cálculo de las capacidades de codificación de redes . Las soluciones de codificación lineal están limitadas por la desigualdad y esto tiene una consecuencia importante:

La región de tasas alcanzables utilizando codificación de red lineal podría ser, en algunos casos, estrictamente más pequeña que la región de tasas alcanzables utilizando codificación de red general. [3] [4] [5]

Para definiciones, véase, por ejemplo, [6].

Prueba

Teorema (desigualdad de Ingleton): [7] Sea M un matroide representable con función de rango ρ y sean X 1 , X 2 , X 3 y X 4 subconjuntos del conjunto de soporte de M , denotado por el símbolo E ( M ). Entonces:

ρ ( X 1 )+ ρ ( X 2 )+ ρ ( X 1 ∪ X 2 ∪ X 3 )+ ρ ( X 1 ∪ X 2 ∪ X 4 )+ ρ ( X 3 ∪ X 4 ) ≤ ρ ( X 1 ∪ X 2 )+ ρ ( X 1 ∪ X 3 )+ ρ ( X 1 ∪ X 4 )+ ρ ( X 2 ∪ X 3 )+ ρ ( X 2 ∪ X 4 ).

Para demostrar la desigualdad tenemos que mostrar el siguiente resultado:

Proposición : Sean V 1 , V 2 , V 3 y V 4 subespacios de un espacio vectorial V , entonces

  1. tenue( V 1 ∩ V 2 ∩ V 3 ) ≥ tenue( V 1 ∩ V 2 ) + tenue( V 3 ) − tenue( V 1 + V 3 ) − tenue( V 2 + V 3 ) + tenue( V 1 + V 2 + V 3 )
  2. tenue ( V 1 ∩ V 2 ∩ V 3 ∩ V 4 ) ≥ tenue ( V 1 ∩ V 2 ∩ V 3 ) + tenue ( V 1 ∩ V 2 ∩ V 4 ) − tenue ( V 1 ∩ V 2 )
  3. tenue( V 1 ∩ V 2 ∩ V 3 ∩ V 4 ) ≥ tenue( V 1 ∩ V 2 ) + tenue( V 3 ) + tenue( V 4 ) − tenue( V 1 + V 3 ) − tenue( V 2 + V 3 ) - tenue ( V 1 + V 4 ) - tenue ( V 2 + V 4 ) - tenue( V 1 + V 2 + V 3 ) + tenue ( V 1 + V 2 + V 4 )
  4. tenue ( V 1 ) + tenue ( V 2 ) + tenue ( V 1 + V 2 + V 3 ) + tenue ( V 1 + V 2 + V 4 ) + tenue ( V 3 + V 4 ) ≤ tenue ( V 1 + V 2 ) + tenue ( V 1 + V 3 ) + tenue ( V 1 + V 4 ) + tenue ( V 2 + V 3 ) + tenue( V 2 + V 4 )

Donde V i + V j representa la suma directa de los dos subespacios.

Prueba (proposición) : Utilizaremos frecuentemente la identidad estándar del espacio vectorial: dim( U ) + dim( W ) = dim( U + W ) + dim( U ∩ W ).

1. Es claro que ( V 1 ∩ V 2 ) + V 3 ⊆ ( V 1 + V 3 ) ∩ ( V 2 + V 3 ), entonces

2. Es claro que ( V 1 ∩ V 2 ∩ V 3 ) + ( V 1 ∩ V 2 ∩ V 4 ) ⊆ ( V 1 ∩ V 2 ), entonces

3. De (1) y (2) tenemos:

4. De (3) tenemos

Si sumamos (dim( V 1 )+dim( V 2 )+dim( V 3 + V 4 )) en ambos lados de la última desigualdad, obtenemos

Dado que la desigualdad dim( V 1 ∩ V 2 ∩ V 3 ∩ V 4 ) ≤ dim( V 3 ∩ V 4 ) se cumple, hemos terminado con la demostración.♣

Demostración (desigualdad de Ingleton) : Supóngase que M es un matroide representable y sea A = [ v 1 v 2 … v n ] una matriz tal que M = M ( A ). Para X , Y ⊆ E( M ) = {1,2, … ,n}, definamos U = <{ V i  : i ∈ X }>, como el espacio de los vectores en V i , y definimos W = <{ V j  : j ∈ Y }> en consecuencia.

Si suponemos que U = <{ u 1 , u 2 , … , u m }> y W = <{ w 1 , w 2 , … , w r }> entonces claramente tenemos <{ u 1 , u 2 , …, u m , w 1 , w 2 , …, w r }> = U + W .

Por lo tanto: r ( X ∪ Y ) = dim <{ v i  : i ∈ X } ∪ { v j  : j ∈ Y }> = dim( V + W ).

Finalmente, si definimos V i = { v r  : r ∈ X i } para i = 1,2,3,4, entonces por la última desigualdad y el ítem (4) de la proposición anterior, obtenemos el resultado.

Referencias

  1. ^ Ingleton, AW (1971). "Representación de matroides". En galés, DJA (ed.). Matemáticas combinatorias y sus aplicaciones. Actas, Oxford, 1969. Academic Press. págs. 149–167. ISBN 0-12-743350-3.Zbl 0222.05025  .
  2. ^ Ahlswede, Rudolf ; N. Cai; Shuo-Yen Robert Li; Raymond Wai-Ho Yeung (2000). "Flujo de información en red". IEEE Transactions on Information Theory . 46 (4): 1204–1216. doi :10.1109/18.850663.
  3. ^ Dougherty, R.; C. Freiling ; K. Zeger (2005). "Insuficiencia de códigos de redes lineales". Simposio internacional IEEE sobre teoría de la información, Adelaida, Australia : 264–267.
  4. ^ Dougherty, R.; C. Freiling ; K. Zeger (2007). "Redes, matroides y desigualdades de información no relacionadas con Shannon". IEEE Transactions on Information Theory . 53 (6): 1949–1969. CiteSeerX 10.1.1.218.3066 . doi :10.1109/TIT.2007.896862. S2CID  27096. 
  5. ^ Li, S.-YR; Yeung, RW; Ning Cai (2003). "Codificación de red lineal". IEEE Transactions on Information Theory . 49 (2): 371. doi :10.1109/TIT.2002.807285.
  6. ^ Bassoli, Riccardo; Marques, Hugo; Rodríguez, Jonathan; Shum, Kenneth W.; Tafazolli, Rahim (2013). "Teoría de la codificación de redes: una encuesta". IEEE Communications Surveys & Tutorials . 15 (4): 1950. doi :10.1109/SURV.2013.013013.00104. S2CID  691027.
  7. ^ Oxley, James (1992), Teoría de matroides, Oxford: Oxford University Press, ISBN 0-19-853563-5 , MR 1207587, Zbl 0784.05002. 

Enlaces externos