Forbidden configurations: Finding the number predicted by the Anstee-Sali conjecture is NP-hard
Abstract
Let 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.
Keywords
Forbidden configuration, hypergraph, trace, NP-hard, NP-complete, Anstee-Sali conjecture.
DOI: https://doi.org/10.26493/1855-3974.438.300
ISSN: 1855-3974
Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications