CS Paper Radar

Boxicity of Power Graphs of Finite Nilpotent Groups

L. Sunil Chandran, Jinia Ghosh, Suraj Kumar Sahoo

cs.DM math.COmath.GR ·submitted 2026-11-04 17:30 UTC · v1
theory

Abstract

The \textit{boxicity} of an undirected graph $Γ$, denoted as $\operatorname{box}(Γ)$, is the smallest non-negative integer $d$ such that $Γ$ can be represented as the intersection graph of axis-parallel rectangular boxes in $\mathbb{R}^d$. The \emph{power graph} of a group $G$, denoted as $\operatorname{Pow}(G)$, is an undirected graph whose vertex set is the group itself, with two elements being adjacent if one is a power of the other. We determine the exact boxicity of power graphs of finite nilpotent groups. For a cyclic group of order $n=\prod_{i=1}^{r}p_i^{e_i}>1$, where the $p_i$ are distinct primes, we prove that its power graph has boxicity $\sum_{i=1}^{r}e_i-\max_i e_i$. For a finite nilpotent group $G$, let the number of noncyclic odd Sylow subgroups be denoted by $t(G)$. If $G$ has odd order or if $G$ has a cyclic Sylow $2$-subgroup, then $\operatorname{box}(\operatorname{Pow}(G))=\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_{\operatorname{exp}(G)}))+t(G)$, where $\operatorname{exp}(G)$ denotes the \emph{exponent} of a group $G$. When the Sylow $2$-subgroup is noncyclic, and the odd part is nontrivial, the boxicity equals this value or one more, and we characterise precisely when each of these values is attained. The boxicity of power graphs of arbitrary finite groups and the exact boxicity of the comparability graph of the Boolean lattice were posed as open questions in Discrete Mathematics, 349(7):115017, 2026. As a consequence of our results, we answer the latter question completely and the former question partially, by computing the exact boxicity of the power graphs of nilpotent groups.

Comment
28 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Word Length and Diameter in Permutation Groups

cs.CC math.GR ·2026-09-22 ·Markus Lohrey, Alexander Thumm
similarity 0.59
Abstract

In the binary diameter problem, the input consists of explicitly given permutations generating a finite group $G$ and a binary-encoded number $k$, and the question is whether every element of $G$ is a product of at most $k$ of the given generators. In the binary length problem, the input additionally contains a permutation $g \in G$, and the question is whether $g$ is such a product. We show that the binary diameter problem is PSPACE-complete, thereby confirming a conjecture of Lohrey and Rosowski (2023). Moreover, we show that PSPACE-hardness already holds for solvable groups of derived length at most 3, whereas the problem is $Π_2^{\mathrm{P}}$-complete for 2-step nilpotent groups. For the binary length problem, we establish a sharp complexity threshold: the problem is NP-complete for 2-step nilpotent groups, which extends a result of Lohrey and Rosowski for abelian groups, and PSPACE-complete for groups that are simultaneously 3-step nilpotent and metabelian, which strengthens the main result of Jerrum (1985). Finally, we show that the unary diameter problem, where $k$ is encoded in unary, is $Π_2^{\mathrm{P}}$-complete for generating sets of the full symmetric group, confirming another conjecture of Lohrey and Rosowski.

0.28

Logarithmic basis number of graphs and regular matroids

cs.DM math.CO ·2026-09-02 ·Kolja Knauer
theory similarity 0.58
Abstract · 13 pages

The basis number $bn(G)$ of a graph $G$ is the minimum edge-congestion of a basis of its cycle space. We prove that every finite $n$-vertex multigraph satisfies $bn(G)=O(\log n)$, resolving, for simple graphs, a question of Bazargani, Biedl, Bose, Maheshwari and Miraftab, subsequently stated as a conjecture by Miraftab, Morin and Yuditsky. The argument also yields the cycle-rank refinement $bn(G)=O(\log β(G))$, where $β(G)$ is the dimension of the cycle space, and a reduction of Lehner and Miraftab, based on a theorem of Richter and Shank, then gives $bn(G)=O(\log g)$ for graphs of Euler genus $g$. For regular matroids we prove the ground-set bound $bn(M)=O(\log m)$, where $m=|E(M)|$, and logarithmic bounds in both the rank $r(M)$ and the cycle-space dimension $d$. All these orders are best possible.

0.51

Boxicity and Threshold Dimension of Zero Divisor Graphs

cs.DM math.COmath.AC ·2026-08-27 ·Marco Caoduro, Meike Neuwohner
similarity 0.58
Abstract · 25 pages 5 figures

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).

0.40

A Counterexample to the Gyarmati-Matolcsi-Ruzsa Conjecture

cs.IT math.CO ·2026-10-30 ·Chandra Nair, Aref Namayandeh, Zhaobang Zhu
similarity 0.57
Abstract · 12 pages

We provide a counterexample to the non-abelian Gyarmati-Matolcsi-Ruzsa conjecture. The construction comes from an equivalent maximal-coupling entropy inequality, for which a counterexample can be found in a lower-dimensional group. We give an explicit cardinality counterexample in $D_4^{14}$, the fourteenth direct power of the dihedral group of order $8$.

0.48

Integral saturation of adjacency-degree lattices

cs.DM math.CO ·2026-11-01 ·Zhipeng Lu
theory similarity 0.57
Abstract

Let $A$ be the adjacency matrix of $G\sim G(n,1/2)$, let $D=\operatorname{diag}(A\mathbf{1})$, and let $Λ_G=\mathbb{Z}\langle A,D\rangle\mathbf{1}$. We prove $\Pr[Λ_G\ne\mathbb{Z}^n]\le n^{-3/20+o(1)}$. Thus two dependent graph operators generate the entire vertex lattice from the constant vector, simultaneously over every prime field. Adjacency alone has a modulo-two rank obstruction for every simple graph of order greater than one, even though its rational word span is typically full. The proof first constructs words containing at most two adjacency operations whose integer span contains $Δ_G^3\mathbb{Z}^n$, where $Δ_G$ is the product of the pairwise differences between distinct degree values. This confines all possible arithmetic obstructions to a finite prime range on a single event. We then remove the remaining obstructions using conditional alternating forms, symmetric random-matrix code estimates, and uniform counts of degree-graded invariant subspaces. We connect the integer lattice to graph reconstruction through pointed moments. Saturation forces every pointed orthogonal AD intertwiner to be a vertex permutation. The short-word construction also shows that a fixed polynomial-size family of ordinary caterpillars, of diameter at most seven and order $O(\sqrt{n\log n})$, identifies almost every graph among all finite simple graphs. For nonsaturated full-rank lattices, we give an exact description of the moment fibre by admissible unimodular overlattices; at index two, the only possible ambiguity is a specified four-vertex Godsil--McKay switch.

0.28

Structural Characterizations and Algebraic Realizations of a Family of Regular Integral Graphs

cs.DM math.COmath.GR ·2026-09-22 ·Tapa Manna, Supriyo Dutta, Baby Bhattacharya
theory similarity 0.56
Abstract · Comments are welcome!

All the eigenvalues of an integral graphs are integers. Integral graphs are extremely rare. They form an asymptotically vanishing fraction $2^{-Ω(n)}$ among all graphs on $n$ vertices. It makes the construction of a new family of integral graphs a challenging task. Also, most of the known infinite family of integral graphs rely on Cayley graphs over Abelian groups. In this article, we introduce a new family of integral graphs obtained from the groups. The construction of our graphs from groups is different from the construction of Cayley graphs. A spectral uniqueness theorem is established, which shows that each member of the infinite family is determined by its adjacency spectrum among all finite simple graphs. We also present recursive constructions that generates larger members of the family from smaller ones, providing a scalable class of integral graphs. Finally, we investigate algebraic realizations of these graphs as complements of Proper Prime Order Element Graphs of finite $2$-groups and obtain conditions characterizing such realizations. We also observe that the graphs obtained from different non-isomorphic groups have cospectral graphs.

0.18

The boxicity of the compressed zero divisor graph of the ring of integers modulo N

cs.DM math.CO ·2026-08-24 ·L. Sunil Chandran, Suraj Kumar Sahoo
unusual similarity 0.56
Abstract

The boxicity of a graph $G$, denoted by $box(G)$, is the minimum integer $d\geq 0$ such that $G$ is the intersection graph of axis-parallel boxes in $\mathbb{R}^d$. The class of zero divisor graphs introduced by Beck (1988) is a popular class of graphs and has been studied extensively by several researchers. Suppose $Z(R)$ is the set of zero divisors of a ring $R$. The zero divisor graph $Γ(R)$ for a ring $R $ is defined as the graph with the vertex set $V(Γ(R))=Z(R)$ and $E(Γ(R))=\{\{x,y\}\colon x,y\in Z(R)\text{ with }x\neq y\text{ and }x y=0\}$. One can define an equivalence relation $\sim$ on $V(Γ(R))$ such that for vertices $x$ and $y$, one has $x\sim y$ if and only if $x$ and $y$ have the same annihilator, i.e., $Ann(x)=Ann(y)$. The compressed zero divisor graph $Γ_E(R)$ for a ring $R$ is the simple graph obtained from $Γ(R)$ by retaining exactly one vertex from each equivalence class induced by $\sim$. In this paper, we completely answer two open questions posed in Discrete Applied Mathematics 391 (2026), pp. 127-136. Let $N=\prod_{i=1}^a p_i^{n_i}$ be the prime factorization of a positive integer $N$ and let $\mathbb{Z}_N$ be the ring of integers modulo $N$. We determine the exact boxicity of the compressed zero divisor graph $Γ_E(\mathbb{Z}_N)$. We show that when $a\geq 2$, $box(Γ_E(\mathbb{Z}_N))= a-1$ if and only if one of the following is true: $(i)$ $a\geq 2$ and $N$ is the product of two coprime integers $x$ and $y$ such that $x$ is a square-free integer and $y$ is the cube of a prime number; $(ii)$ $a\geq 3$ and $N$ is square-free; $(iii)$ $a\geq 2$, $N$ is cube-free, not square-free, and contains at least one prime divisor $p_i$ such that $n_i=1$. If $a=2$ and $n_1=n_2=1$, then $Γ_{E}(\mathbb{Z}_N)$ is a clique, and so, $box(Γ_{E}(\mathbb{Z}_N))=0$. In all other cases, $box(Γ_{E}(\mathbb{Z}_N))=a$.

0.57

The weight enumerators of irreducible cyclic codes of length $2^\ell$

cs.IT math.CO ·2026-10-08 ·Ricardo A. Podestá, Denis E. Videla
similarity 0.55
Abstract · 19 pages, 3 tables

Using the spectral relation between irreducible cyclic codes (ICC) and generalized Paley (GP) graphs recently found by the authors, we study the weight distribution of irreducible cyclic codes of length $2^\ell$, $\ell \in \mathbb{N}$. These codes were previously studied by Sharma, Bakshi and Raka, who divided them into two families (each having two cases). First we characterize the GP-graphs spectrally related to these families of ICCs: they are complete, semiprimitive, Hamming, or Cartesian products of semiprimitive GP-graphs. We then compute the spectrum of these graphs and hence, by the mentioned spectral relation we finally obtain neat explicit expressions for the weight enumerators of all the irreducible cyclic codes of length $2^\ell$ with $\ell \in \mathbb{N}$.

0.11