Source-linked AI summary
Boxicity and Threshold Dimension of Zero Divisor Graphs
Marco Caoduro, Meike Neuwohner
TL;DR
The paper addresses incomplete characterizations of boxicity and threshold dimension for zero divisor graphs of reduced rings and finite PID quotients. It uses reduced graphs, disjointness graphs, and integral covering graphs to analyze these parameters, obtaining classifications for both ring families and answering two questions posed by Chandran and Sahoo. The results also identify a prior attempted lower-bound proof for reduced rings as incorrect and replace it with the new framework.
Problem
The paper addresses the question of determining boxicity and threshold dimension for zero divisor graphs of reduced rings and finite quotients of principal ideal domains, including whether the reduced-ring lower bound n −1 is tight.
Method
The paper develops reduced zero divisor graphs and integral covering graphs, relating them to disjointness graphs to analyze boxicity and threshold dimension across both ring families.
Results
The paper characterizes boxicity and threshold dimension for reduced rings and finite PID quotients, with reduced-ring cases determined by minimal-prime loneliness and quotient cases by prime-factorization data.
Takeaways & Limitations
The integral covering graph framework captures a common structure of the two ring families, generalizes disjointness graphs, and answers two questions posed by Chandran and Sahoo.
Takeaways & Limitations
A prior attempted lower-bound proof for reduced zero divisor graphs was incorrect, as identified by Chandran and Sahoo.
Abstract
from arXiv · showhide
The zero divisor graph $Γ(R)$ of a finite commutative ring $R$ has as vertices the non-zero zero divisors of $R$, with an edge between two elements exactly when their product is zero. We determine the boxicity and threshold dimension of $Γ(R)$ for two classes of finite commutative rings: reduced rings and quotients of principal ideal domains. Our proofs use a new combinatorial gadget, the integral covering graph, that captures the structure shared by both ring families and generalizes the disjointness graph on subsets of $[n]$, where two subsets are adjacent if and only if they are disjoint. In doing so, we answer two questions recently posed by L.~Sunil Chandran and Suraj Kumar Sahoo in Boxicity of Zero Divisor Graphs, Discrete Applied Mathematics 391 (2026).
1 Introduction
The paper studies boxicity and threshold dimension for zero divisor graphs, focusing on reduced rings and finite quotient rings of principal ideal domains. It introduces combinatorial connections through reduced graphs, disjointness graphs, and integral covering graphs to characterize these parameters and address prior questions.
- 1 Introduction: Boxicity is the minimum dimension of an axis-parallel box representation, equivalently the minimum number of interval-graph supergraphs whose edge-wise intersection is the target graph.Threshold dimension analogously uses threshold graphs; because threshold graphs are interval graphs, box(G) ≤ dimTH(G).
- 1 Introduction: The zero divisor graph Γ(R) has nonzero zero divisors as vertices, with adjacency exactly when the product of two vertices is zero.The paper considers finite commutative rings with nonzero identity, including reduced rings and finite quotient rings of PIDs.
- 1.1 Reduced rings: For reduced rings with n minimal prime ideals, the paper answers whether the lower bound n −1 is tight by characterizing boxicity and threshold dimension according to minimal-prime structure.The characterization distinguishes cases involving lonely minimal prime ideals; when n = 1 both parameters are 0, while the n ≥ 3 pattern is expressed through the reduced-graph analysis and disjointness graphs.
- 1.1 Reduced rings: Minimal prime ideals are called lonely when the intersection of all other minimal primes, after removing the given prime, is a singleton; otherwise they are non-lonely.In Z/30Z, the prime ideal generated by 2 is lonely, whereas the one generated by 3 is not because the corresponding set contains 10 and 20.
- 1.1 Reduced rings: The reduced graph identifies vertices with identical neighborhoods, and reduced zero divisor graphs of finite reduced rings correspond to disjointness graphs Dn on nonempty proper subsets of [n].The paper proves box(Dn) = dimTH(Dn) = 0 for n ∈ {1,2}, and n −1 for n ≥ 3.
- 1.2 Quotients of principal ideal domains: For finite quotient rings of PIDs, boxicity and threshold dimension are characterized from the prime factorization of the defining ideal, including exponents and the number of residue fields of size 2.The PID result generalizes and extends results for rings Z/MZ, while integral covering graphs provide a common combinatorial framework.
2 Preliminaries
The preliminaries define the graph, ring, zero divisor, zero divisor graph, boxicity, threshold dimension, and reduced-graph notions used throughout. They also establish structural tools, including forbidden-subgraph characterizations, partial joins, and invariance of boxicity under reduction.
- Rings and zero divisor graphs: A zero divisor graph has vertices Z(R)\{0}, with two vertices adjacent exactly when their product is zero.
- Rings and zero divisor graphs: In a reduced ring, the zero divisors are precisely the union of the minimal prime ideals.
- Boxicity and threshold dimension: A threshold graph is characterized by having no induced C4, P4, or 2K2.
- Structural tools: For a partial join, each constituent graph appears as an induced subgraph and cross-part non-edges form matchings; this yields a lower bound on threshold dimension.
- Reduced graphs: The reduced graph identifies vertices with identical neighborhoods, and its boxicity equals that of the graph before reduction.
3 Integral covering graphs
Integral covering graphs encode vertices by coordinate-bounded vectors, with adjacency determined coordinatewise, and generalize disjointness graphs. Their boxicity and threshold dimension are characterized through matching lower and upper bounds.
- Definition: Integral covering graphs use vectors with bounded coordinates, excluding the all-zero and all-maximum vectors, and join vertices when every coordinate sum reaches its bound.This coordinatewise definition captures the graph family studied in the section.
- Lower bounds: For every admissible m, box(D(m)) and threshold dimension are at least those of D(1^n), giving a general lower-bound transfer.The lower bound follows from the induced disjointness-graph structure.
- Upper bounds: The graph D(m) is the intersection of n threshold graphs, supplying an n-dimensional upper bound for both parameters.This establishes the basic upper-bound side of the characterization.
- Relation to disjointness graphs: The disjointness graph D_n is isomorphic to D(1^n), identifying nonempty proper subsets of [n] with binary vectors.Thus integral covering graphs extend the disjointness-graph framework.
- Corner cases: The corner cases include box(D(1,1)) = dimTH(D(1,1)) = 0 and values 0 or 1 for one-dimensional D(m), depending on whether m ≤3 or m ≥4.For m ≥4, the graph has two non-adjacent vertices; for m ≤3 it is a clique or empty.
- Characterization: For the remaining cases, both parameters are at least n −1, and the classification distinguishes when they equal n from when they equal n −1.The complete characterization also records the exceptional zero-dimensional case m = 1^2.
- Proof of lower bounds: The lower bound for the disjointness graph is proved by showing an interval graph can touch at most n −1 relevant pairs, forcing at least n −1 interval graphs.An interval graph cannot touch two disjoint pairs, which yields the counting restriction.
- Characterization: If some coordinate satisfies m_i ≥4, or one coordinate equals 3 while another is at least 2, then both parameters equal n.When exactly one coordinate equals 3 and all others equal 1, boxicity is n −1; for m ∈{1,2}^n other than the listed exceptions, the same lower value applies.
4 Zero divisor graphs of reduced rings
For reduced rings, minimal-prime membership vectors encode zero divisors and their adjacency, identifying the reduced graph with a disjointness graph. This representation yields exact boxicity and threshold-dimension values governed by the number and loneliness of minimal primes.
- Combinatorial representation: The map μ records which minimal prime ideals contain each nonzero zero divisor.Its coordinates are 1 for containing minimal primes and 0 otherwise.
- Combinatorial representation: Two nonzero zero divisors are adjacent exactly when their membership vectors satisfy μ(r) + μ(s) ≥ 1 coordinatewise.This follows from primality of the minimal ideals and their intersection being zero.
- Combinatorial representation: Every nonzero proper binary vector occurs as μ(r), so μ induces an isomorphism between ΓE(R) and D(1^n).Equal vectors give equivalent neighborhoods, while distinct vectors can be separated by an adjacent witness.
- Exact parameters: A minimal-prime index is lonely when exactly one ring element has zero membership there and one membership at every other index.Loneliness is the structural condition used to distinguish the parameter values.
- Exact parameters: For n = 1, both parameters are 0; for n = 2, they are 0, 1, or 1 according as both, exactly one, or neither minimal prime is lonely.The n = 2 cases are stated in the theorem’s classification.
- Exact parameters: For n ≥ 3, both parameters equal n − 1 when some minimal-prime index is lonely, and equal n otherwise.The lower bound in the non-lonely case comes from an induced n-fold join of K2.
5 Quotient rings of principal ideal domains
For finite quotients of principal ideal domains, prime-factor exponents provide a coordinate representation of zero-product adjacency. The resulting graphs are intersections of threshold graphs, while reduced graphs are integral covering graphs whose parameters admit exact case classifications.
- Exponent representation: A principal ideal domain supports unique prime factorizations up to units and association, enabling exponent-based coordinates for quotient-ring elements.The quotient is written R/I with I = gR, where the prime exponents of g determine the coordinate bounds.
- Exponent representation: For each prime coordinate, a_i(r) is the largest exponent of p_i dividing r, and α_i(q) = min{a_i(r), m_i} is well-defined on quotient classes.Well-definedness follows because equivalent representatives have identical truncated exponents.
- Threshold representation: Two quotient elements multiply to zero exactly when a_i(r) + a_i(s) ≥ m_i for every coordinate.This converts divisibility by the quotient ideal into coordinatewise threshold conditions.
- Threshold representation: Γ(Q) is the intersection of n threshold graphs T(α_i restricted to Z(Q)\{0}, m_i).The coordinate functions are restricted to the nonzero zero divisors.
- Exact parameters: If some m_i ≥ 3, then boxicity and threshold dimension both equal n; several binary-exponent cases instead yield n − 1 or lower exceptional values.For all m_i = 1, the classification depends on n and the residue-field sizes |R/p_iR|.
- Exact parameters: When some m_i ≥ 2, the threshold dimension of Γ(R/aR) equals n.This completes the corresponding theorem together with the all-m_i = 1 case.