İmzalı küme - Signed set

Matematikte bir imzalı set bir Ayarlamak bir atama ile birlikte öğelerin işaret (pozitif veya negatif) kümenin her bir öğesine.

Temsil

İmzalanmış kümeler matematiksel olarak bir sıralı çift nın-nin ayrık kümeler biri olumlu unsurları, diğeri olumsuz unsurları için.^[1] Alternatif olarak, bir Boole işlevi, etki alanı temelde yatan işaretsiz küme (muhtemelen temsilin ayrı bir parçası olarak açıkça belirtilir) ve aralığı, işaretleri temsil eden iki öğeli bir küme olan bir işlev.^[2][3]

İmzalı setler de çağrılabilir ${ displaystyle mathbb {Z} _ {2}}$-dereceli setler.^[2]

Uygulama

İmzalı kümeler, yönelimli matroidler.^[1]

Tanımlamak için de kullanılabilirler. yüzler bir hiperküp. Hiper küp içindeki tüm noktalardan oluşuyorsa Öklid uzayı belirli bir boyutun Kartezyen koordinatları aralıkta ${ displaystyle [-1, + 1]}$, ardından koordinat eksenlerinin işaretli bir alt kümesi, alt küme içindeki koordinatları olan noktaları belirtmek için kullanılabilir. ${ displaystyle -1}$ veya ${ displaystyle +1}$ (işaretli alt kümedeki işarete göre) ve diğer koordinatları aralıkta herhangi bir yerde olabilir ${ displaystyle [-1, + 1]}$. Bu nokta alt kümesi bir yüz oluşturur. eş boyut ... kardinalite imzalı alt kümenin.^[4]

Kombinatorik

Numaralandırma

Bir verinin imzalı alt kümelerinin sayısı Sınırlı set nın-nin ${ displaystyle n}$ öğeler ${ displaystyle 3 ^ {n}}$, bir üçün gücü, çünkü her öğe için üç seçenek vardır: alt kümede bulunmayabilir, pozitif işaret ile mevcut olabilir veya negatif işaret ile mevcut olabilir.^[5] Aynı nedenden ötürü, imzalı kardinalite alt kümelerinin sayısı ${ displaystyle r}$ dır-dir

${ displaystyle 2 ^ {r} { binom {n} {r}},}$

ve bunların toplanması, Binom teoremi,

${ displaystyle sum _ {r} 2 ^ {r} { binom {n} {r}} = 3 ^ {n}.}$

Kesişen aileler

Bir analogu Erdős – Ko – Rado teoremi kesişen set aileleri üzerinde imzalı setler için de geçerlidir. İki işaretli kümenin kesişimi, her ikisine de ait olan ve her ikisinde de aynı işarete sahip olan işaretli öğeler kümesi olarak tanımlanır. Bu teoreme göre, herhangi bir imzalı alt kümeler koleksiyonu için ${ displaystyle n}$-element seti, hepsi kardinaliteye sahip ${ displaystyle r}$ ve boş olmayan bir kesişme noktasına sahip tüm çiftler, koleksiyondaki imzalı alt kümelerin sayısı en fazla

${ displaystyle 2 ^ {r-1} { binom {n-1} {r-1}}.}$

Örneğin, bu büyüklükte kesişen bir aile, tek bir sabit elemanın işaretini seçerek ve aileyi, kardinalliğin tüm imzalı alt kümeleri olarak alarak elde edilebilir. ${ displaystyle r}$ Bu işareti içeren bu öğe. İçin ${ displaystyle r leq n / 2}$ Bu teorem, alt kümelerin imzasız versiyonları kesişen bir aile oluşturduğundan ve her işaretsiz küme en fazla karşılık gelebildiğinden, işaretsiz Erdős-Ko-Rado teoremini hemen takip eder. ${ displaystyle 2 ^ {r-1}}$ imzalı setler. Ancak, daha büyük değerler için ${ displaystyle r}$ farklı bir kanıta ihtiyaç vardır.^[3]

Referanslar