Ruzsa uchburchagi tengsizligi - Ruzsa triangle inequality - Wikipedia

Yilda qo'shimchalar kombinatorikasi, Ruzsa uchburchagi tengsizligi, deb ham tanilgan Ruzsa farqi uchburchagi tengsizligi uni ba'zi bir variantlaridan farqlash uchun, ikkala to'plamning farq miqdorini ikkala farqning o'lchamlari bo'yicha uchinchi to'plam bilan chegaralaydi. Bu tomonidan isbotlangan Imre Ruzsa (1996),[1] ga o'xshashligi uchun shunday nomlangan uchburchak tengsizligi. Bu isbotlashda muhim lemma Plyunnke-Ruzsa tengsizligi.

Bayonot

Agar va ning kichik to'plamlari abeliy guruhi, keyin sumset yozuv belgilash uchun ishlatiladi . Xuddi shunday, bildiradi . Keyin, Ruzsa uchburchagi tengsizligi quyidagilarni bildiradi.

Teorema (Ruzsa uchburchagi tengsizligi) — Agar , va abeliya guruhining cheklangan kichik to'plamlari, keyin

Muqobil formulalar tarkibiga tushunchasi kiradi Ruzsa masofasi.[2]

Ta'rif. Agar va abeliya guruhining cheklangan kichik to'plamlari, keyin Ruzsa masofasi ushbu ikki to'plam o'rtasida belgilanadi , deb belgilanadi

Keyinchalik, Ruzsa uchburchagi tengsizligi quyidagi ekvivalent formulaga ega:

Teorema (Ruzsa uchburchagi tengsizligi) — Agar , va abeliya guruhining cheklangan kichik to'plamlari, keyin

Ushbu formulalar a uchun uchburchak tengsizligiga o'xshaydi metrik bo'shliq; ammo, Ruzsa masofasi metrik bo'shliqni aniqlamaydi har doim ham nolga teng emas.

Isbot

Gapni isbotlash uchun to'plamdan in'ektsiya qurish kifoya to'plamga . Funktsiyani aniqlang quyidagicha. Har biriga tanlang a va a shu kabi . Ta'rifi bo'yicha , buni har doim qilish mumkin. Ruxsat bering yuboradigan funktsiya bo'lishi ga . Har bir nuqta uchun to'plamda , shunday bo'lishi kerak va . Shuning uchun, har bir nuqtani xaritada aks ettiradi aniq bir nuqtaga va shu bilan in'ektsiya. Xususan, unda kamida shuncha nuqta bo'lishi kerak kabi . Shuning uchun,

dalilni to'ldirish.

Ruzsa uchburchagi tengsizligining variantlari

The Ruzsa sum uchburchagi tengsizligi Plyunekke-Ruzsa tengsizligining xulosasi (bu o'z navbatida oddiy Ruzsa uchburchagi tengsizligi yordamida isbotlangan).

Teorema (Ruzsa yig'indisi uchburchagi tengsizligi) — Agar , va abeliya guruhining cheklangan kichik to'plamlari, keyin

Isbot. Dalilda quyidagi lemma ishlatiladi Plunnecke-Ruzsa tengsizligining isboti.

Lemma. Ruxsat bering va abeliya guruhining cheklangan kichik to'plamlari . Agar qiymatini minimallashtiradigan bo'sh bo'lmagan to'plamdir , keyin barcha cheklangan pastki to'plamlar uchun

Agar bo'sh to'plam, keyin tengsizlikning chap tomoni bo'ladi , shuning uchun tengsizlik haqiqatdir. Aks holda, ruxsat bering ning pastki qismi bo'lishi bu minimallashtiradi . Ruxsat bering . Ning ta'rifi shuni anglatadiki Chunki , yuqorida keltirilgan lemmani beradi

Qayta tartibga solish Ruzsa yig'indisi uchburchagi tengsizligini beradi.


O'zgartirish bilan va Ruzsa uchburchagi tengsizligida va Ruzsa summasi uchburchagi tengsizligi bilan va kerak bo'lganda, umumiyroq natijaga erishish mumkin: Agar , va u holda abeliya guruhining cheklangan kichik to'plamlari

bu erda barcha sakkizta konfiguratsiya belgilari mavjud. Ushbu natijalar ba'zida umumiy sifatida tanilgan Ruzsa uchburchagi tengsizliklari.

Adabiyotlar

  1. ^ Ruzsa, I. (1996). "Sonli to'plamlar yig'indisi". Raqamlar nazariyasi: Nyu-York seminari 1991-1995.
  2. ^ Tao T .; Vu, V. (2006). Qo'shimchalar kombinatorikasi. Kembrij: Kembrij universiteti matbuoti. ISBN  978-0-521-85386-6.