Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/100147
Título: | General non-realizability certificates for spheres with linear programming | Autor: | Gouveia, João Macchia, Antonio Wiebe, Amy |
Palavras-chave: | Final polynomials; Linear programming; Non-realizability certificates; Slack matrices | Data: | 2023 | Editora: | Elsevier | Projeto: | UIDB/00324/2020 | Título da revista, periódico, livro ou evento: | Journal of Symbolic Computation | Volume: | 114 | Resumo: | In this paper we present a simple technique to derive certificates of non-realizability for a combinatorial polytope. Our approach uses a variant of the classical algebraic certificates introduced by Bokowski and Sturmfels (1989), the final polynomials. More specifically we reduce the problem of finding a realization to that of finding a positive point in a variety and try to find a polynomial with positive coefficients in the generating ideal (a positive polynomial), showing that such point does not exist. Many, if not most, of the techniques for proving non-realizability developed in the last three decades can be seen as following this framework, using more or less elaborate ways of constructing such positive polynomials. Our proposal is more straightforward as we simply use linear programming to exhaustively search for such positive polynomials in the ideal restricted to some linear subspace. Somewhat surprisingly, this elementary strategy yields results that are competitive with more elaborate alternatives, and allows us to derive new examples of non-realizable combinatorial polytopes | URI: | https://hdl.handle.net/10316/100147 | ISSN: | 07477171 | DOI: | 10.1016/j.jsc.2022.04.013 | Direitos: | openAccess |
Aparece nas coleções: | FCTUC Matemática - Artigos em Revistas Internacionais I&D CMUC - Artigos em Revistas Internacionais |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
2109.15247.pdf | 285.59 kB | Adobe PDF | Ver/Abrir |
Citações SCOPUSTM
1
Visto em 1/mai/2023
Citações WEB OF SCIENCETM
1
Visto em 2/jun/2024
Visualizações de página
143
Visto em 2/out/2024
Downloads
89
Visto em 2/out/2024
Google ScholarTM
Verificar
Altmetric
Altmetric
Este registo está protegido por Licença Creative Commons