The edge code of hypergraphs

DOI10.1142/S0219498825410038MaRDI QIDQ6876079zbMATH OpenFDO

Publication date 13 January 2026

Published in Journal of Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0219498825410038

affine torus degree edge codes finite field footprint hypergraphs next-to-minimal weights squarefree evaluation codes toric codes

Mathematics Subject Classification ID

Hypergraphs (05C65) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Applications to coding theory and cryptography of arithmetic geometry (14G50) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Review text

The author introduces a new family of evaluation codes utilizing the approach proposed by \textit{D. Jaramillo} et al. [Des. Codes Cryptography 89, No. 2, 269--300 (2021; Zbl 1456.14034)]. Notable examples of evaluation codes include affine Cartesian codes, monomial Cartesian codes, and toric codes.\N\NConsider the polynomial ring \(\mathbb{F}_q[t_1, \ldots, t_s]\), where \(\mathbb{F}_q\) is a finite field with \(q\) elements. Let \(\{e_1, \dots, e_n\}\) represent the set of edges of a hypergraph \(H\) with \(s\) vertices. We denote by \(E(H)\) the set of monomials determined by its edges; that is,\N\[\NE(H) = \{f_1, \dots, f_n\},\N\]\Nwhere \(f_i := \prod_{j \in e_i} t_j\) is the product of variables indexed by \(j\) in the edge \(e_i\). The author then defines the \textit{edge toric code} \(\mathcal{C}_H\) of \(H\) as the image \(\text{ev}(\mathbb{F}_q E(H))\) of the \(\mathbb{F}_q\)-linear space generated by the monomials in \(E(H)\) under an evaluation map \(\text{ev}\) at the points of an affine torus. These codes constitute the novel family introduced in the paper.\N\NA \textit{clutter} \(C\) is a hypergraph in which no edges are contained within other edges. \(C\) is \textit{\(d\)-uniform} if every edge has size \(d\).\N\NThe goal of the paper is to prove the following three results:\N\N\begin{itemize}\N\item[1.] Let \(C\) be a \(d\)-uniform clutter and \(q \geq 3\). The minimum distance of \(\mathcal{C}_{C}\), denoted by \(\delta(\mathcal{C}_{C})\), is given by:\N\[\N\delta(\mathcal{C}_{C}) = \begin{cases} (q - 2)^d (q - 1)^{s-d} & \text{if } d \leq s/2 \text{ and } C \text{ contains a suitable clutter,} \\\N(q - 2)^{s-d} (q - 1)^d & \text{if } s/2 < d < s \text{ and } C^* \text{ contains a suitable clutter,} \end{cases}\N\]\Nwhere \(C^*\) is the edge removed hypergraph of \(C\). This result corresponds to Theorem 3.7 in the paper.\N\N\item[2.] Let \(1 \leq d_2 \leq d_1\) be integers and \(q \geq 3\). If \(H\) contains all edges of size \(r\) such that \(d_2 \leq r \leq d_1\), then:\N\[\N\delta(\mathcal{C}_{H}) = \begin{cases} (q - 2)^{d_1} (q - 1)^{s-d_1} & \text{if } d_1 + d_2 \leq s \\\N(q - 2)^{s-d_2} (q - 1)^{d_2} & \text{if } d_1 + d_2 > s. \end{cases}\N\]\NThis result corresponds to Theorem 3.9 in the paper.\N\N\item[3.] Let \(\mathcal{C}_G\) be the edge code of a connected tree \(G\). For \(1 \leq t \leq (s - 1)/2\), the \(t\)-th Hamming weight of \(\mathcal{C}_G\) is:\N\[\N(q - 1)^s - (q - 1)^{s-1} + (q - 1)^{s-2} + \dots + (-1)^{2t+1}(q - 1)^{s-(2t-1)}.\N\]\NThis result corresponds to Theorem 3.15 in the paper.\N\end{itemize}

Cites work

This page was built for publication: The edge code of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6876079)