Неравенство Инглтона - Ingletons inequality - Wikipedia

В математике Неравенство Инглтона является неравенство что удовлетворено классифицировать функция любого представимый матроид. В этом смысле это необходимое условие представимости матроид над конечным полем. Позволять M будь матроидом и пусть ρ - его ранговая функция, неравенство Инглтона утверждает, что для любых подмножеств Икс₁, Икс₂, Икс₃ и Икс₄ в поддерживать из M, неравенство

ρ(Икс₁)+ρ(Икс₂)+ρ(Икс₁∪Икс₂∪Икс₃)+ρ(Икс₁∪Икс₂∪Икс₄)+ρ(Икс₃∪Икс₄) ≤ ρ(Икс₁∪Икс₂)+ρ(Икс₁∪Икс₃)+ρ(Икс₁∪Икс₄)+ρ(Икс₂∪Икс₃)+ρ(Икс₂∪Икс₄) доволен.

Обри Уильям Инглтон, английский математик, написал важную статью в 1969 г.^[1] в которой он исследовал проблему представимости в матроидах. Хотя статья носит в основном пояснительный характер, в ней Инглтон сформулировал и доказал неравенство Инглтона, которое нашло интересные приложения в теория информации, теория матроидов, и сетевое кодирование.^[2]

Важность неравенства

Есть интересные связи между матроиды, то область энтропии и теория групп. Некоторые из этих связей обнаруживаются с помощью неравенства Инглтона.

Возможно, более интересное применение неравенства Инглтона касается вычисления сетевое кодирование мощности. Решения для линейного кодирования ограничены неравенством, и это имеет важное последствие:

Область достижимых ставок при использовании линейное сетевое кодирование в некоторых случаях может быть строго меньше, чем область достижимых скоростей при использовании общего сетевого кодирования.^[3][4][5]

Определения см., Например,^[6]

Доказательство

Теорема (Неравенство Инглтона):^[7] Позволять M быть представимый матроид с функцией ранга ρ и разреши Икс₁, Икс₂, Икс₃ и Икс₄ подмножества опорного множества M, обозначается символом E(M). Потом:

ρ(Икс₁)+ρ(Икс₂)+ρ(Икс₁∪Икс₂∪Икс₃)+ρ(Икс₁∪Икс₂∪Икс₄)+ρ(Икс₃∪Икс₄) ≤ ρ(Икс₁∪Икс₂)+ρ(Икс₁∪Икс₃)+ρ(Икс₁∪Икс₄)+ρ(Икс₂∪Икс₃)+ρ(Икс₂∪Икс₄).

Для доказательства неравенства нам нужно показать следующий результат:

Предложение: Позволять V₁,V₂, V₃ и V₄ быть подпространствами векторное пространство V, тогда

1. тусклый (V₁∩V₂∩V₃) ≥ dim (V₁∩V₂) + тусклый (V₃) - тусклый (V₁+V₃) - тусклый (V₂+V₃) + тусклый (V₁+V₂+V₃)
2. тусклый (V₁∩V₂∩V₃∩V₄) ≥ dim (V₁∩V₂∩V₃) + тусклый (V₁∩V₂∩V₄) - тусклый (V₁∩V₂)
3. тусклый (V₁∩V₂∩V₃∩V₄) ≥ dim (V₁∩V₂) + тусклый (V₃) + тусклый (V₄) - тусклый (V₁+V₃) - тусклый (V₂+V₃) - тусклый (V₁+V₄) - тусклый (V₂+V₄) - тусклый (V₁+V₂+V₃) + тусклый (V₁+V₂+V₄)
4. тусклый (V₁) + тусклый (V₂) + тусклый (V₁+V₂+V₃) + тусклый (V₁+V₂+V₄) + тусклый (V₃+V₄) ≤ dim (V₁+V₂) + тусклый (V₁+V₃) + тусклый (V₁+V₄) + тусклый (V₂+V₃) + тусклый (V₂+V₄)

Где V_я+V_j представляют прямая сумма двух подпространств.

Доказательство (предложение): Мы будем часто использовать стандартную идентичность векторного пространства: dim (U) + тусклый (W) = тусклый (U+W) + тусклый (U∩W).

1. Понятно, что (V₁∩V₂) + V₃ ⊆ (V₁+ V₃) ∩ (V₂+V₃), тогда

тусклый ((V1∩V2)+V3)

≤

тусклый ((V1+V2)∩(V2+V3)),

следовательно

тусклый (V1∩V2∩V3)	=	тусклый (V1∩V2) + тусклый (V3) - тусклый ((V1∩V2)+V3)
	≥	тусклый (V1∩V2) + тусклый (V3) - тусклый ((V1+V3)∩(V2+V3))
	=	тусклый (V1∩V2) + тусклый (V3) - {тусклый (V1+V3) + тусклый (V2+V3) - тусклый (V1+V2+V3)}
	=	тусклый (V1∩V2) + тусклый (V3) - тусклый (V1+V3) - тусклый (V2+V3) + тусклый (V1+V2+V3)

2. Понятно, что (V₁∩V₂∩V₃) + (V₁∩V₂∩V₄) ⊆ (V₁∩V₂), тогда

dim {(V1∩V2∩V3)+(V1∩V2∩V4)}

≤

тусклый (V1∩V2),

следовательно

тусклый (V1∩V2∩V3∩V4)	=	тусклый (V1∩V2∩V3) + тусклый (V1∩V2∩V4) - dim {(V1∩V2∩V3) + (V1∩V2∩V4)}
	≥	тусклый (V1∩V2∩V3) + тусклый (V1∩V2∩V4) - тусклый (V1∩V2)

3. Из (1) и (2) имеем:

тусклый (V1∩V2∩V3∩V4)	≥	тусклый (V1∩V2∩V3) + тусклый (V1∩V2∩V4) - тусклый (V1∩V2)
	≥	тусклый (V1∩V2) + тусклый (V3) - тусклый (V1+V3) - тусклый (V2+V3) + тусклый (V1+V2+V3) + тусклый (V1∩V2) + тусклый (V4) - тусклый (V1+V4) - тусклый (V2+V4) + тусклый (V1+V2+V4) - тусклый (V1∩V2)
	=	тусклый (V1∩V2) + тусклый (V3) + тусклый (V4) - тусклый (V1+V3) - тусклый (V2+V3) - тусклый (V1+V4) - тусклый (V2+V4) + тусклый (V1+V2+V3) + тусклый (V1+V2+V3)

4. Из (3) имеем

тусклый (V1+V2+V3) + тусклый (V1+V2+V4)

≤

тусклый (V1∩V2∩V3∩V4) - тусклый (V1∩V2) - тусклый (V3) - тусклый (V4) + тусклый (V1+V3) + тусклый (V2+V3) + тусклый (V1+V4) + тусклый (V2+V4)

Если мы добавим (dim (V₁) + тусклый (V₂) + тусклый (V₃+V₄)) по обе стороны от последнего неравенства, получаем

тусклый (V1) + тусклый (V2) + тусклый (V1+V2+V3) + тусклый (V1+V2+V4) + тусклый (V3+V4)

≤

тусклый (V1∩V2∩V3∩V4) - тусклый (V1∩V2) + тусклый (V1+ тусклый (V2) + тусклый (V3+V4) - тусклый (V3) - тусклый (V4) + тусклый (V1+V3) + тусклый (V2+V3) + тусклый (V1+V4) + тусклый (V2+V4)

Поскольку неравенство dim (V₁∩V₂∩V₃∩V₄) ≤ dim (V₃∩V₄), мы закончили доказательство. ♣

Доказательство (неравенство Инглтона): Предположим, что M представляет собой представимый матроид и пусть А = [v₁ v₂ … v_п] - матрица такая, что M = M(А).За Икс, Y ⊆ E (M) = {1,2,…, n} определим U = <{V_я : i ∈ Икс }>, поскольку промежуток векторов в V_я, и мы определяем W = <{V_j : j ∈ Y}> соответственно.

Если мы предположим, что U = <{ты₁, ты₂, … ,ты_м}> и W = <{ш₁, ш₂, … ,ш_р}> то очевидно, что <{ты₁, ты₂, …, ты_м, ш₁, ш₂, …, ш_р }> = U + W.

Следовательно:р(Икс∪Y) = dim <{v_я : i ∈ Икс } ∪ {v_j : j ∈ Y }> = dim (V + W).

Наконец, если мы определим V_я = {v_р : р ∈ Икс_я } для i = 1,2,3,4, то по последнему неравенству и пункту (4) предыдущего предложения получаем результат.

Рекомендации

1. Инглтон, А. (1971). «Изображение матроидов». На валлийском языке D.J.A. (ред.). Комбинаторная математика и ее приложения. Слушания, Оксфорд, 1969 г.. Академическая пресса. С. 149–167. ISBN  0-12-743350-3. Zbl  0222.05025.
2. Альсведе, Рудольф; Н. Цай; Шуо-Йен Роберт Ли; Раймонд Вай-Хо Йунг (2000). «Сетевой информационный поток». IEEE Transactions по теории информации. 46 (4): 1204–1216. Дои:10.1109/18.850663.
3. Dougherty, R .; К. Фрайлинг; К. Зегер (2005). «Недостаточность линейных сетевых кодов». Международный симпозиум IEEE по теории информации Аделаида, Австралия: 264–267.
4. Dougherty, R .; К. Фрейлинг; К. Зегер (2007). «Сети, матроиды и нешенноновские информационные неравенства». IEEE Transactions по теории информации. 53 (6): 1949–1969. Дои:10.1109 / TIT.2007.896862.
5. Li, S.-Y.R .; Yeung, R.W .; Нинг Кай (2003). «Линейное сетевое кодирование» (PDF). IEEE Transactions по теории информации. 49 (2): 371. Дои:10.1109 / TIT.2002.807285.
6. Бассоли, Риккардо; Маркес, Хьюго; Родригес, Джонатан; Шум, Кеннет В .; Тафазолли, Рахим (2013). «Теория сетевого кодирования: обзор». Обзоры и учебные пособия по коммуникациям IEEE. 15 (4): 1950. Дои:10.1109 / SURV.2013.013013.00104.
7. Оксли, Джеймс (1992), Теория матроидов, Оксфорд: Oxford University Press, ISBN  0-19-853563-5, МИСТЕР 1207587, Zbl 0784.05002.

внешняя ссылка

• «Скорость передачи канала», Энциклопедия математики, EMS Press, 2001 [1994]