Ingletonova nerovnost - Ingletons inequality - Wikipedia

V matematice Ingletonova nerovnost je nerovnost který je uspokojen hodnost funkce libovolného reprezentativní matroid. V tomto smyslu je to nezbytná podmínka pro zastupitelnost a matroid přes konečné pole. Nechat M být matroid a nechat ρ jako její hodnostní funkce Ingletonova nerovnost uvádí, že pro všechny podmnožiny X₁, X₂, X₃ a X₄ v Podpěra, podpora z Mnerovnost

ρ(X₁)+ρ(X₂)+ρ(X₁∪X₂∪X₃)+ρ(X₁∪X₂∪X₄)+ρ(X₃∪X₄) ≤ ρ(X₁∪X₂)+ρ(X₁∪X₃)+ρ(X₁∪X₄)+ρ(X₂∪X₃)+ρ(X₂∪X₄) je spokojen.

Aubrey William Ingleton, anglický matematik, napsal důležitou práci v roce 1969^[1] ve kterém zkoumal problém reprezentability u matroidů. I když je článek převážně výkladový, v tomto článku Ingleton uvedl a prokázal Ingletonovu nerovnost, která našla zajímavé aplikace v teorie informace, teorie matroidů, a síťové kódování.^[2]

Důležitost nerovnosti

Mezi nimi jsou zajímavá spojení matroidy, entropická oblast a teorie skupin. Některá z těchto spojení jsou odhalena Ingletonovou nerovností.

Možná zajímavější aplikace Ingletonovy nerovnosti se týká výpočtu síťové kódování kapacity. Řešení lineárního kódování jsou omezeni nerovností a má to důležitý důsledek:

Oblast dosažitelných sazeb za použití lineární kódování sítě může být v některých případech striktně menší než oblast dosažitelných sazeb pomocí obecného síťového kódování.^[3]^[4]^[5]

Definice viz např.^[6]

Důkaz

Teorém (Ingletonova nerovnost):^[7] Nechat M být reprezentativní matroid s hodnostní funkcí ρ a nechte X₁, X₂, X₃ a X₄ být podmnožinami sady podpory z M, označený symbolem E(M). Pak:

ρ(X₁)+ρ(X₂)+ρ(X₁∪X₂∪X₃)+ρ(X₁∪X₂∪X₄)+ρ(X₃∪X₄) ≤ ρ(X₁∪X₂)+ρ(X₁∪X₃)+ρ(X₁∪X₄)+ρ(X₂∪X₃)+ρ(X₂∪X₄).

Abychom dokázali nerovnost, musíme ukázat následující výsledek:

Tvrzení: Nechte PROTI₁,PROTI₂, PROTI₃ a PROTI₄ být podprostory a vektorový prostor PROTI, pak

ztlumit(PROTI₁∩PROTI₂∩PROTI₃) ≥ ztlumit (PROTI₁∩PROTI₂) + ztlumit (PROTI₃) - ztlumit (PROTI₁+PROTI₃) - ztlumit (PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₂+PROTI₃)
ztlumit(PROTI₁∩PROTI₂∩PROTI₃∩PROTI₄) ≥ ztlumit (PROTI₁∩PROTI₂∩PROTI₃) + ztlumit (PROTI₁∩PROTI₂∩PROTI₄) - ztlumit (PROTI₁∩PROTI₂)
ztlumit(PROTI₁∩PROTI₂∩PROTI₃∩PROTI₄) ≥ ztlumit (PROTI₁∩PROTI₂) + ztlumit (PROTI₃) + ztlumit (PROTI₄) - ztlumit (PROTI₁+PROTI₃) - ztlumit (PROTI₂+PROTI₃) - ztlumit (PROTI₁+PROTI₄) - ztlumit (PROTI₂+PROTI₄) - ztlumit (PROTI₁+PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₂+PROTI₄)
ztlumit (PROTI₁) + ztlumit (PROTI₂) + ztlumit (PROTI₁+PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₂+PROTI₄) + ztlumit (PROTI₃+PROTI₄) ≤ dim (PROTI₁+PROTI₂) + ztlumit (PROTI₁+PROTI₃) + ztlumit (PROTI₁+PROTI₄) + ztlumit (PROTI₂+PROTI₃) + ztlumit (PROTI₂+PROTI₄)

Kde PROTI_i+PROTI_j představují přímý součet dvou podprostorů.

Důkaz (návrh): Často budeme používat standardní identitu vektorového prostoru: dim (U) + ztlumit (Ž) = dim (U+Ž) + ztlumit (U∩Ž).

1. Je jasné, že (PROTI₁∩PROTI₂) + PROTI₃ ⊆ (PROTI₁+ PROTI₃) ∩ (PROTI₂+PROTI₃), pak

ztlumit((PROTI₁∩PROTI₂)+PROTI₃)

≤

ztlumit((PROTI₁+PROTI₂)∩(PROTI₂+PROTI₃)),

proto

ztlumit(PROTI₁∩PROTI₂∩PROTI₃)	=	ztlumit(PROTI₁∩PROTI₂) + ztlumit (PROTI₃) - dim ((PROTI₁∩PROTI₂)+PROTI₃)
	≥	ztlumit(PROTI₁∩PROTI₂) + ztlumit (PROTI₃) - dim ((PROTI₁+PROTI₃)∩(PROTI₂+PROTI₃))
	=	ztlumit(PROTI₁∩PROTI₂) + ztlumit (PROTI₃) - {dim (PROTI₁+PROTI₃) + ztlumit (PROTI₂+PROTI₃) - ztlumit (PROTI₁+PROTI₂+PROTI₃)}
	=	ztlumit(PROTI₁∩PROTI₂) + ztlumit (PROTI₃) - ztlumit (PROTI₁+PROTI₃) - ztlumit (PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₂+PROTI₃)

2. Je jasné, že (PROTI₁∩PROTI₂∩PROTI₃) + (PROTI₁∩PROTI₂∩PROTI₄) ⊆ (PROTI₁∩PROTI₂), pak

ztlumit{(PROTI₁∩PROTI₂∩PROTI₃)+(PROTI₁∩PROTI₂∩PROTI₄)}

≤

ztlumit(PROTI₁∩PROTI₂),

proto

ztlumit(PROTI₁∩PROTI₂∩PROTI₃∩PROTI₄)	=	ztlumit(PROTI₁∩PROTI₂∩PROTI₃) + ztlumit (PROTI₁∩PROTI₂∩PROTI₄) - dim {(PROTI₁∩PROTI₂∩PROTI₃) + (PROTI₁∩PROTI₂∩PROTI₄)}
	≥	ztlumit(PROTI₁∩PROTI₂∩PROTI₃) + ztlumit (PROTI₁∩PROTI₂∩PROTI₄) - ztlumit (PROTI₁∩PROTI₂)

3. Z (1) a (2) máme:

ztlumit(PROTI₁∩PROTI₂∩PROTI₃∩PROTI₄)	≥	ztlumit(PROTI₁∩PROTI₂∩PROTI₃) + ztlumit (PROTI₁∩PROTI₂∩PROTI₄) - ztlumit (PROTI₁∩PROTI₂)
	≥	ztlumit(PROTI₁∩PROTI₂) + ztlumit (PROTI₃) - ztlumit (PROTI₁+PROTI₃) - ztlumit (PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₂+PROTI₃) + ztlumit (PROTI₁∩PROTI₂) + ztlumit (PROTI₄) - ztlumit (PROTI₁+PROTI₄) - ztlumit (PROTI₂+PROTI₄) + ztlumit (PROTI₁+PROTI₂+PROTI₄) - ztlumit (PROTI₁∩PROTI₂)
	=	ztlumit(PROTI₁∩PROTI₂) + ztlumit (PROTI₃) + ztlumit (PROTI₄) - ztlumit (PROTI₁+PROTI₃) - ztlumit (PROTI₂+PROTI₃) - ztlumit (PROTI₁+PROTI₄) - ztlumit (PROTI₂+PROTI₄) + ztlumit (PROTI₁+PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₂+PROTI₃)

4. Od (3) máme

ztlumit(PROTI₁+PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₂+PROTI₄)

≤

ztlumit(PROTI₁∩PROTI₂∩PROTI₃∩PROTI₄) - ztlumit (PROTI₁∩PROTI₂) - ztlumit (PROTI₃) - ztlumit (PROTI₄) + ztlumit (PROTI₁+PROTI₃) + ztlumit (PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₄) + ztlumit (PROTI₂+PROTI₄)

Pokud přidáme (dim (PROTI₁) + ztlumit (PROTI₂) + ztlumit (PROTI₃+PROTI₄)) na obou stranách poslední nerovnosti dostaneme

ztlumit(PROTI₁) + ztlumit (PROTI₂) + ztlumit (PROTI₁+PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₂+PROTI₄) + ztlumit (PROTI₃+PROTI₄)

≤

ztlumit(PROTI₁∩PROTI₂∩PROTI₃∩PROTI₄) - ztlumit (PROTI₁∩PROTI₂) + ztlumit (PROTI₁+ ztlumit (PROTI₂) + ztlumit (PROTI₃+PROTI₄) - ztlumit (PROTI₃) - ztlumit (PROTI₄) + ztlumit (PROTI₁+PROTI₃) + ztlumit (PROTI₂+PROTI₃) + ztlumit (PROTI₁+PROTI₄) + ztlumit (PROTI₂+PROTI₄)

Vzhledem k tomu, že nerovnost stmívá (PROTI₁∩PROTI₂∩PROTI₃∩PROTI₄) ≤ dim (PROTI₃∩PROTI₄) drží, s důkazem jsme skončili. ♣

Důkaz (Ingletonova nerovnost): Předpokládejme to M je reprezentativní matroid a nechte A = [proti₁ proti₂ … proti_n] být taková matice, že M = M(A).Pro X, Y ⊆ E (M) = {1,2,…, n}, definovat U = <{PROTI_i : i ∈ X }> jako rozpětí vektorů v PROTI_ia definujeme Ž = <{PROTI_j : j ∈ Y}> odpovídajícím způsobem.

Pokud to předpokládáme U = <{u₁, u₂, … ,u_m}> a Ž = <{w₁, w₂, … ,w_r}> pak jasně máme <{u₁, u₂, …, u_m, w₁, w₂, …, w_r }> = U + Ž.

Proto:r(X∪Y) = ztlumit <{proti_i : i ∈ X } ∪ {proti_j : j ∈ Y }> = ztlumit (PROTI + Ž).

Nakonec, pokud definujeme PROTI_i = {proti_r : r ∈ X_i } pro i = 1,2,3,4, pak podle poslední nerovnosti a položky (4) výše uvedené věty získáme výsledek.

Reference

^ Ingleton, A.W. (1971). "Zastoupení matroidů". Ve velštině, D.J.A. (vyd.). Kombinatorická matematika a její aplikace. Proceedings, Oxford, 1969. Akademický tisk. str. 149–167. ISBN 0-12-743350-3. Zbl 0222.05025.
^ Ahlswede, Rudolf; N. Cai; Shuo-Yen Robert Li; Raymond Wai-Ho Yeung (2000). "Tok informací v síti". Transakce IEEE na teorii informací. 46 (4): 1204–1216. doi:10.1109/18.850663.
^ Dougherty, R .; C. Freiling; K. Zeger (2005). "Nedostatečnost kódů lineární sítě". IEEE International Symposium on Information Theory Adelaide, Australia: 264–267.
^ Dougherty, R .; C. Freiling; K. Zeger (2007). "Sítě, matroidy a non-Shannonovy informační nerovnosti". Transakce IEEE na teorii informací. 53 (6): 1949–1969. doi:10.1109 / TIT.2007.896862.
^ Li, S.-Y.R .; Yeung, R.W .; Ning Cai (2003). "Lineární síťové kódování" (PDF). Transakce IEEE na teorii informací. 49 (2): 371. doi:10.1109 / TIT.2002.807285.
^ Bassoli, Riccardo; Marques, Hugo; Rodriguez, Jonathan; Shum, Kenneth W .; Tafazolli, Rahim (2013). „Teorie kódování sítě: průzkum“. Průzkumy a návody pro komunikaci IEEE. 15 (4): 1950. doi:10.1109 / SURV.2013.013013.00104.
^ Oxley, James (1992), Matroid Theory, Oxford: Oxford University Press, ISBN 0-19-853563-5, PAN 1207587, Zbl 0784.05002.

externí odkazy

„Přenosová rychlost kanálu“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]

[Ing71-1] Ingleton, A.W. (1971). "Zastoupení matroidů". Ve velštině, D.J.A. (vyd.). Kombinatorická matematika a její aplikace. Proceedings, Oxford, 1969. Akademický tisk. str. 149–167. ISBN 0-12-743350-3. Zbl 0222.05025.

[Ahlswede2000-2] Ahlswede, Rudolf; N. Cai; Shuo-Yen Robert Li; Raymond Wai-Ho Yeung (2000). "Tok informací v síti". Transakce IEEE na teorii informací. 46 (4): 1204–1216. doi:10.1109/18.850663.

[Dougherty2005-3] Dougherty, R .; C. Freiling; K. Zeger (2005). "Nedostatečnost kódů lineární sítě". IEEE International Symposium on Information Theory Adelaide, Australia: 264–267.

[Dougherty2007-4] Dougherty, R .; C. Freiling; K. Zeger (2007). "Sítě, matroidy a non-Shannonovy informační nerovnosti". Transakce IEEE na teorii informací. 53 (6): 1949–1969. doi:10.1109 / TIT.2007.896862.

[5] Li, S.-Y.R .; Yeung, R.W .; Ning Cai (2003). "Lineární síťové kódování" (PDF). Transakce IEEE na teorii informací. 49 (2): 371. doi:10.1109 / TIT.2002.807285.

[6] Bassoli, Riccardo; Marques, Hugo; Rodriguez, Jonathan; Shum, Kenneth W .; Tafazolli, Rahim (2013). „Teorie kódování sítě: průzkum“. Průzkumy a návody pro komunikaci IEEE. 15 (4): 1950. doi:10.1109 / SURV.2013.013013.00104.

[7] Oxley, James (1992), Matroid Theory, Oxford: Oxford University Press, ISBN 0-19-853563-5, PAN 1207587, Zbl 0784.05002.

[1]

[2]

[3]

[4]

[5]

[6]

[7]