Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 31 min ago
PreprintarXiv licenceHAL

Sum-of-Squares Certificates for Copositive Matrices via Recursive Identities: The de Klerk-Pasechnik Conjecture and Hoffman-Pereira Matrices

  • Jineon Baek
  • Luis Felipe Vargas
Open at sourcePDFDOICite

Abstract

We establish the conjecture by de Klerk and Pasechnik (2002), claiming that the semidefinite bounds ϑ(r)(G)(r≥ 0) for the stability number α(G) are exact at r=α(G)−1, by exhibiting an explicit sum-of-squares certificate. This certificate allows us to recover a known characterization of the minimizers of the Motzkin-Straus formulation for 1/α(G). Additionally, we give sum-of-squares copositivity certificates for the matrices satisfying the Hoffman-Pereira sign condition, a crucial condition for characterizing copositive matrices with {−1,0,1} entries.

Related

  1. Recursive overlap Bernoulli distributions and an entropy concavity conjecture
    Jörg Neunhäuserer
    arXivPreprintarXiv licenceFull textDynamical systemsarXiv
  2. Optimizing Explicit Unit-Distance Lower-Bound Certificates
    Michael T. M. Emmerich
    arXiv (Cornell University)PreprintLicence not statedFull text9 citedCombinatorics & discrete mathematicsOpenAlex
  3. Unique Normal Forms: Proof-Graph Counterexamples, Infinite-Carrier Certificates, and Confluence Repair
    Moses Rahnama
    HALPreprintLicence not statedLogic & foundationsHAL
  4. Task-aware Kernel Stein certificates for Rényi differential privacy
    Leoni Carla Wirth, Tara Trauthwein, Gesine Reinert
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  5. Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks
    Sepehr Akbari, Shahrzad Jamshidi
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{baek2026sumofsquares,
  title = {{Sum-of-Squares Certificates for Copositive Matrices via Recursive Identities: The de Klerk-Pasechnik Conjecture and Hoffman-Pereira Matrices}},
  author = {Jineon Baek and Luis Felipe Vargas},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.01010},
  eprint = {2609.01010},
  archivePrefix = {arXiv},
  url = {https://laas.hal.science/hal-05834954v1},
}
RIS
TY  - UNPB
TI  - Sum-of-Squares Certificates for Copositive Matrices via Recursive Identities: The de Klerk-Pasechnik Conjecture and Hoffman-Pereira Matrices
AU  - Jineon Baek
AU  - Luis Felipe Vargas
PY  - 2026
DA  - 2026/10/19
PB  - HAL
DO  - 10.48550/arxiv.2609.01010
UR  - https://laas.hal.science/hal-05834954v1
AB  - We establish the conjecture by de Klerk and Pasechnik (2002), claiming that the semidefinite bounds ϑ^(r)(G)(r≥ 0) for the stability number α(G) are exact at r=α(G)−1, by exhibiting an explicit sum-of-squares certificate. This certificate allows us to recover a known characterization of the minimizers of the Motzkin-Straus formulation for 1/α(G). Additionally, we give sum-of-squares copositivity certificates for the matrices satisfying the Hoffman-Pereira sign condition, a crucial condition for characterizing copositive matrices with {−1,0,1} entries.
ER  -