Fixed vertex activities and extremal independent-set counts: Exact optimization and quadratic square-free codes
For fixed positive vertex activities, we maximize the independent-set partition function over labelled graphs with a prescribed number of edges. After ordering the activities, a weighted Kelmans identity reduces the optimization to graphs obtained by deleting a smallest universal vertex or a largest isolated vertex. An interval dynamic program computes the optimum for every edge budget using O(m^4) arithmetic operations on m vertices. Exact equality conditions for each compression and maximizing paths in the dynamic program give a polynomial criterion recognizing every optimal graph. The result determines the complete generalized Hamming weight hierarchy of homogeneous square-free quadratic evaluation codes on Cartesian sets containing zero with two alphabet sizes, and characterizes all optimal monomial subspaces.
Authors
- Zihuan Xu
Institutions
- Capital Normal University (CN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-15
- DOI
- https://doi.org/10.5281/zenodo.24244838
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint