Registro completo de metadatos
Campo DC Valor Lengua/Idioma
dc.creatorRaggi, Miguel-
dc.date.accessioned2024-03-23T01:00:38Z-
dc.date.available2024-03-23T01:00:38Z-
dc.date.issued2015-01-24-
dc.identifier.issnISSN electrónico: 1855-3974-
dc.identifier.urihttps://repositorioccm.matmor.unam.mx/handle/123456789/186-
dc.description.abstractLet F be a (possibly non-simple) hypergraph and let forb(m; F) denote the maximum number of edges a simple hypergraph with m vertices can have if it doesn't contain F as a subhypergraph. A conjecture of Anstee and Sali predicts the asymptotic behaviour of forb(m; F) for fixed F. In this paper we prove that even finding this predicted asymptotic behaviour is an NP-hard problem, meaning that if the Anstee-Sali conjecture were true, finding the asymptotics of forb(m; F) would be NP-hard.-
dc.description.sponsorshipResearch supported by DGAPA Postdoctoral scholarship, UNAM.-
dc.languageeng-
dc.publisherUniversity of Primorska-
dc.publisherSlovenian Society of Discrete and Applied Mathematics-
dc.publisherSociety of Mathematicians, Physicists and Astronomers of Slovenia-
dc.publisherInstitute of Mathematics, Physics and Mechanics-
dc.rightsEl uso de este contenido digital se rige por una licencia Creative Commons BY 3.0 Internacional, https://creativecommons.org/licenses/by/3.0/legalcode.en/, fecha de asignación de la licencia 2015-01-24.-
dc.subjectCombinatorics-
dc.subjectExtremal combinatorics-
dc.subjectExtremal set theory-
dc.subject.classificationCiencias Físico-Matemáticas y de las Ingenierías-
dc.titleForbidden configurations: finding the number predicted by the Anstee-Sali conjecture is NP-hard-
dc.typeArtículo de investigación-
dcterms.audienceInvestigadores-
dcterms.provenanceUniversidad Nacional Autónoma de México. Centro de Ciencias Matemáticas-
dcterms.provenanceArs Mathematica Contemporanea; https://amc-journal.eu/index.php/amc/article/view/438-
dc.identifier.urlhttps://amc-journal.eu/index.php/amc/article/view/438-
dc.rights.accessrightsAcceso abierto-
dc.description.repositoryRepositorio Universitario del Centro de Ciencias Matemáticas, https://repositorioccm.matmor.unam.mx/-
dc.identifier.bibliographiccitationM. Raggi, Forbidden configurations: finding the number predicted by the Anstee-Sali conjecture is NP-hard, Ars Mathematica Contemporanea, vol. 10 (2015), 1-8, https://repositorioccm.matmor.unam.mx/handle/123456789/186-
dc.identifier.doihttps://doi.org/10.26493/1855-3974.438.300-
dc.relation.ispartofjournalArs Mathematica Contemporanea, vol. 10 (2016), 1-8. ISSN electrónico: 18553974. En: https://amc-journal.eu/index.php/amc/issue/view/25-
Aparece en las colecciones: Artículos de Investigación

Mostrar el registro sencillo del ítem EstadÍsticas


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.