Noll-divisor graf

Nolldelargrafen för ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{4}} ,$ den enda möjliga nolldelargrafen som är ett träd men inte en stjärna

I matematik, och mer specifikt i kombinatorisk kommutativ algebra , är en noll-divisorgraf en oriktad graf som representerar nolldivisorerna i en kommutativ ring . Den har element av ringen som sina hörn och par av element vars produkt är noll som dess kanter .

Definition

Det finns två varianter av nolldelargrafen som vanligtvis används. I den ursprungliga definitionen av Beck (1988) representerar hörnen alla element i ringen. I en senare variant som studerats av Anderson & Livingston (1999), representerar hörnen endast nolldelaren för den givna ringen.

Exempel

Om $n$ är ett halvprimtal (produkten av två primtal ) så är nolldivisorgrafen för ringen av heltal modulo $n$ (med endast nolldivisorerna som sina hörn) antingen en komplett graf eller en komplett tvådelad graf . Det är en komplett graf $K_{p-1}$ i fallet att $n=p^{2}$ för något primtal $p$ . I det här fallet är hörnen alla multiplar som inte är noll av $p$ , och produkten av två av dessa tal är 0 modulo $p^{2}$ .

Det är en komplett tvådelad graf $K_{p-1,q-1}$ i fallet att $n=pq$ för två distinkta primtal ${ \displaystyle p}$ och $q$ . De två sidorna av bipartitionen är $p-1$ icke-nollmultiplar av $q$ respektive $q-1$ icke-nollmultiplar av $p$ . . Två tal (som inte själva är noll modulo $n$ ) multiplicerar till noll modulo $n$ om och endast om det ena är en multipel av $p$ och det andra är en multipel av ${ \displaystyle q}$ , så denna graf har en kant mellan varje par av hörn på motsatta sidor av bipartitionen, och inga andra kanter. Mer generellt är nolldelargrafen en komplett tvådelad graf för vilken ring som helst som är en produkt av två integrerade domäner .

De enda cykelgraferna som kan realiseras som nollproduktsgrafer (med nolldelare som hörn) är cyklerna med längd 3 eller 4. De enda träd som kan realiseras som nolldelargrafer är stjärnorna ( kompletta tvådelade grafer som är träd) och trädet med fem vertex som bildas som nolldelargrafen för $\mathbb {Z} _{2}\times \mathbb {Z} _{4}$ .

Egenskaper

I den version av grafen som inkluderar alla element är 0 en universell vertex , och nolldivisorerna kan identifieras som de hörn som har en annan granne än 0. Eftersom den har en universell vertex är grafen för alla ringelement alltid ansluten och har högst två diameter. Grafen över alla nolldelare är inte tom för varje ring som inte är en integral domän . Den förblir ansluten, har högst tre diameter och (om den innehåller en cykel) har omkretsen högst fyra.

Nolldelargrafen för en ring som inte är en integraldomän är finit om och endast om ringen är finit. Mer konkret, om grafen har maximal grad $d$ , har ringen högst $(d^{2}-2d+2)^{2}$ element. Om ringen och grafen är oändliga har varje kant en ändpunkt med oändligt många grannar.

Beck (1988) förmodade att (liksom de perfekta graferna ) nolldelargrafer alltid har lika klicktal och kromatiskt tal . Detta är dock inte sant; ett motexempel upptäcktes av Anderson & Naseer (1993) .