logo

アンダーソン-リビングストン定理の証明 📂グラフ理論

アンダーソン-リビングストン定理の証明

要旨 1

$R$ この可換環単位元$1$を持ち、その零因子の集合を$Z(R)$とするなら、その零因子グラフ$\Gamma (R)$は連結グラフであり、$\text{diam}(\Gamma (R)) \le 3$


説明

アンダーソンリビングストンは、零因子グラフの研究における重要な功績を残しており、特にグラフの連結性と直径の上限値を特定するこの定理を、アンダーソン・リビングストン定理と呼ぶこともある。

証明

$x,y \in Z(R) (x \ne y)$とする。

  • ケース1. $xy=0$
    当然、$d(x,y)=1$である。
  • ケース2. $xy \ne 0$
    • ケース2-1. $x^2 = y^2 = 0$
      1.png したがって、$d(x,y)=2$
    • ケース2-2. $x^2 = 0, y^2 \ne 0$
      $by=0$となる$b \in Z(R)$が存在する。
      • ケース2-2-1. $bx=0$
        2.png したがって、$d(x,y)=2$
      • ケース2-2-2. $bx \ne 0$
        3.png したがって、$d(x,y)=2$
    • ケース2-3. $x^2 \ne 0, y^2 = 0$
      ケース2-2と似ている。
    • ケース2-4. $x^2 \ne 0, y^2 \ne 0$
      $ax=0=by$となる$a, b \in Z(R)$が存在する。
      • ケース2-4-1. $a=b$
        4.png $ax=0=ay$なので、$d(x,y)=2$
      • ケース2-4-2. $a \ne b$
        • ケース2-4-2-1. $ab=0$
          5.png したがって、$d(x,y)=3$
        • ケース2-4-2-2. $ab \ne 0$
          6.png したがって、$d(x,y)=2$


  1. Anderson, Livingston. (1999). The Zero-Divisor Graph of a Commutative Ring ↩︎