Source-linked AI summary
Edge codes constructed from unicyclic graphs
Sara Asensio, Giulia Gaggero, Naveena Ragunathan, Abhilash Saha, Adam Van Tuyl
TL;DR
The paper addresses how to compute parameters of edge codes for unicyclic graphs, extending known tree results. It uses torus zero counting and leaf-removal reductions, showing that induced-cycle parity governs whether coefficients affect weight distributions. The main scope boundary is that certain parameter behavior depends on the cycle and field conditions.
Problem
Existing edge-code results covered trees, while minimum distances and weight distributions for unicyclic graphs required determination.
Method
The paper combines torus zero counting, leaf-removal techniques, and cycle-specific analyses to derive unicyclic-graph code parameters.
Results
Odd induced cycles yield zero counts determined by term counts, whereas even induced cycles yield counts determined by term counts and coefficients.
Takeaways & Limitations
The full weight distribution for edge codes of unicyclic graphs is obtainable, but even-cycle cases require distinguishing polynomial families by coefficient conditions.
Takeaways & Limitations
The analysis assumes q>2 and excludes degenerate cases; even-cycle parameters depend on cycle length and the base-field size.
Abstract
from arXiv · showhide
Jaramillo-Velez recently introduced edge codes, a new class of toric evaluation codes constructed from the edges of a (hyper)graph $\mathcal{H}$. In the case that $\mathcal{H}$ is a tree, Jaramillo-Velez computed both the minimum distance and the weight distribution of the associated code. In this paper, we study edge codes associated to unicyclic graphs. Our most striking result is that computing the parameters of these codes is subtle in the case that the induced cycle has an even length because these values will depend on certain conditions regarding the length of the cycle and the size of the base field.
1. Introduction
This paper extends edge toric codes from trees to unicyclic graphs and determines their minimum distances and weight distributions. The induced cycle’s parity creates a fundamental distinction: odd cycles depend on term counts, whereas even cycles also depend on coefficients.
- Edge codes arise by associating squarefree monomials to graph edges and evaluating their polynomial span on an affine torus.
- The paper studies edge codes constructed from unicyclic graphs, which have exactly one induced cycle.
- The authors extend earlier tree results by computing the minimum distance and full weight distribution for unicyclic-graph edge codes.
- Odd induced cycles make zero counts depend only on the number of terms in a polynomial, not its coefficients.
- Even induced cycles make zero counts depend on both the number of terms and their coefficients, creating parameter sensitivity.
2. Background
The background defines edge toric codes through polynomial evaluation on an affine torus and reduces their parameters to counting polynomial zeros. Tree formulas provide the foundation for extending minimum-distance results to broader graph families.
- For a graph G on s vertices, the edge code has length (q−1)^s and dimension |E|.
- The Hamming weight of the codeword from f is (q−1)^s−|V_T(f)|, so minimum distance equals the length minus the largest torus zero count.
- Computing all polynomial zero counts determines the code’s weight distribution and is the paper’s central computational objective for unicyclic graphs.
- For trees, the weight distribution is organized by the number r of non-zero polynomial terms, with remaining weight multiplicities equal to zero.
- The tree minimum distance is (q−1)^(s−1)(q−2), achieved by polynomials with two non-zero terms.
- The paper extends earlier minimum-distance results for graphs containing 4-cycles toward the family of unicyclic graphs.
3. Edge codes of graphs with a leaf
The leaf analysis relates an edge code to the code obtained by deleting a leaf, enabling recursive removal of attached trees. This reduction supports zero-count and weight-distribution results for larger graphs built from smaller cores.
- Deleting a leaf t produces G′ by removing t and its incident edge, reducing edge-code analysis to a smaller graph.
- Theorem 3.2 transfers nonzero weight multiplicities between CG′ and CG through factors of q−1 and complementary weights.
- If a minimum-weight polynomial omits the leaf term, then δ(CG)=(q−1)δ(CG′).
- The first inequality in the leaf corollary always holds when |T|−δ(CG)≤δ(CG).
- For a graph with trees attached to core vertices, repeated leaf removal relates zero counts on the expanded graph H to polynomials on the core G.
- Theorem 3.5 tracks the number r of non-zero terms contributed by attached trees while reducing their effect on torus zero counts.
- The tree case is recovered as a corollary: zero counts depend on the number of non-zero terms for tree-associated polynomials.
4. Edge codes of cycles
The paper determines weight distributions for edge codes of cycles, using recursive zero-counting arguments. Odd and even cycle lengths behave differently: odd cycles are coefficient-independent, whereas even cycles require coefficient conditions and depend on cycle and field parameters.
- Recursive method: The recursive zero-counting method reduces cycle calculations by separating cases according to whether a linear factor vanishes.In one case, the count reduces to zeroes for a cycle of length s −2; in the other, one variable is determined by the remaining variables.
- Odd cycles: The weight distribution of an edge code for an odd cycle is determined by the number of non-zero terms, independent of polynomial coefficients.This follows from explicit zero-counting formulas for polynomials associated with all edges of an odd cycle.
- Odd cycles: For odd cycles, the minimum distance is achieved by polynomials with two non-zero terms.The minimum-distance case corresponds to r = 2.
- Even cycles: For even cycles, polynomials split into two families whose zero counts depend on a condition involving their coefficients.The four-cycle illustrates the two cases, with zero counts (q −1)^3, (q −1)^2(q −2), or (q −1)^2(q −3) depending on the coefficient relation.
- Even cycles: Theorem 4.7 combines the even-cycle zero-counting results to give the complete weight distribution for cycles of length s = 2k ≥4.The resulting minimum-distance analysis compares the largest zero count from the coefficient-conditioned family with the count for two-term polynomials.
- Even cycles: For even cycles with s ≥10, the minimum distance is δ(Cs) = (q−1)^(s−1)(q−2) when q > 2.The stated inequality supporting this conclusion holds only for small k, and for k ≥5 it holds only for the excluded prime q = 2.
5. Edge codes of unicyclic graphs
The paper determines weight distributions and minimum distances for edge codes of unicyclic graphs by reducing leaf attachments to cycle calculations. Odd induced cycles yield uniform formulas, while even cycles require coefficient- and field-dependent cases.
- Method: Unicyclic graphs are analyzed as cycles with trees attached, using a leaf-removal theorem to relate their polynomial zeroes and code parameters.The main tool applies because unicyclic graphs can be obtained by successively adding leaves to a cycle.
- Odd induced cycles: For an odd induced cycle, the zero count for a polynomial depends only on its number of non-zero terms, not its coefficients.The resulting weight distribution and minimum distance are therefore determined uniformly by the term count.
- Minimum distance: For odd-cycle unicyclic graphs, the minimum distance is achieved by all polynomials with two non-zero terms.The supplied passages state this characterization but do not expose the displayed numerical formula.
- Odd induced cycles: The odd-cycle result is proved by induction on the number of vertices, removing one leaf at a time and applying the leaf-removal relationship.The base case is an odd cycle; the induction step expresses the polynomial as f′ plus a leaf term.
- Even induced cycles: For an even induced cycle, the zero count splits according to whether at least one cycle coefficient is zero or all cycle coefficients are non-zero.The all-non-zero case uses the cycle zero count from Proposition 4.5, which depends on the coefficients.
- Even induced cycles: The even-cycle weight distribution is assembled from polynomials whose induced subgraphs either omit part of the cycle or contain the cycle in one of two coefficient cases.The paper gives explicit counting categories, while leaving the detailed expansion to the reader.