サイン入りセット

数学において、符号付き集合とは、集合の各要素に 符号（正または負）が割り当てられた要素の集合です。

表現

符号付き集合は、数学的には互いに素な集合の順序付きペアとして表現され、一方の集合は正の要素、もう一方の集合は負の要素を表す。^{[1]あるいは、符号付き集合は}ブール関数として表現される。ブール関数とは、基になる符号なし集合（表現の別の部分として明示的に指定される場合もある）を定義域とし、値域は符号を表す2要素集合である関数である。^{[2] [3]}

符号付きセットは段階的セットとも呼ばれる。^[2]${\displaystyle \mathbb {Z} _{2}}$

応用

符号付き集合は有向マトロイドの定義の基本となる。^[1]

これらは超立方体の面を定義するためにも用いられる。超立方体が、与えられた次元のユークリッド空間において、その直交座標が区間 に含まれるすべての点から構成される場合、座標軸の符号付き部分集合を用いて、その部分集合内の座標がまたは（符号付き部分集合の符号に従って）であり、かつ他の座標が区間 内の任意の位置にある点を特定することができる。この点の部分集合は面を形成し、その余次元は符号付き部分集合の濃度となる。 ^[4]${\displaystyle [-1,+1]}$ ${\displaystyle -1}$ ${\displaystyle +1}$ ${\displaystyle [-1,+1]}$

組合せ論

列挙

与えられた有限要素集合の符号付き部分集合の数はで、3のべき乗である。これは、各要素が部分集合に存在しないか、正の符号で存在するか、負の符号で存在するかの3つの選択肢があるためである。^[5]同じ理由で、基数の符号付き部分集合の数は ${\displaystyle n}$ ${\displaystyle 3^{n}}$ ${\displaystyle r}$

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

これらを合計すると二項定理の例が得られる。

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

交差する家族

集合の交差族に関するエルデシュ・コー・ラドの定理の類似は、符号付き集合にも成り立つ。2つの符号付き集合の交差は、両方に属し、両方で同じ符号を持つ元の符号付き集合として定義される。この定理によれば、 -元集合の符号付き部分集合の任意の集合において、すべての集合が濃度を持ち、すべての組が空でない交差を持つ場合、その集合に含まれる符号付き部分集合の数は最大で ${\displaystyle n}$ ${\displaystyle r}$

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

例えば、このサイズの交差族は、単一の固定された元の符号を選択​​し、その符号を持つ元を含む、濃度の符号付き部分集合全体を族とすることで得られる。この定理は、符号なしエルデシュ＝コー＝ラドの定理から直ちに導かれる。なぜなら、部分集合の符号なしバージョンは交差族を形成し、各符号なし集合は最大で符号付き集合に対応できるからである。しかし、より大きな値の場合には、異なる証明が必要となる。^[3]${\displaystyle r}$ ${\displaystyle r\leq n/2}$ ${\displaystyle 2^{r-1}}$ ${\displaystyle r}$

参考文献

1. Las Vergnas, Michel (1980)、「有向マトロイドの凸性」、Journal of Combinatorial Theory、シリーズB、29 (2): 231– 243、doi : 10.1016/0095-8956(80)90082-9、MR  0586435
2. Brini, A. (2005 年 7 月)、「組合せ論、超代数、不変理論および表現理論」、Séminaire Lotharingien de Combinatoire、55、Art. B55g、MR  2373407特にセクション3.4、p.15を参照
3. Bollobás, B. ; Leader, I. (1997)、「符号付き集合に対するエルデシュ・コー・ラド定理」、Computers and Mathematics with Applications、34 (11): 9– 13、doi : 10.1016/S0898-1221(97)00215-0、MR  1486880
4. メトロポリス、N. ;ロータ、ジャン＝カルロ(1978)、「-立方体の面の格子について」、アメリカ数学会誌、84 (2): 284– 286、doi : 10.1090/S0002-9904-1978-14477-2、MR  0462997${\displaystyle n}$
5. この符号付き部分集合の数と超立方体の面の数に関する式は、ハンナー多面体の面の数にも一般化されます。Kalai , Gil (1989)「中心対称多面体の面の数」、Graphs and Combinatorics、5 (1): 389– 391、doi :10.1007/BF01788696、MR  1554357を参照してください。