Forbidden configurations - Raggi, Miguel (Ars mathematica contemporanea, 2016)
Let ?$F$? be a (possibly non-simple) hypergraph and let ?$\text{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 ?$\text{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 ?$\text{forb}(m, F)$? would be NP-hard.
Keywords: Anstee-Sali conjecture; Anstee-Sali domneva; forbidden configuration; hipergraf; hypergraph; NP-complete; NP-hard; NP-poln; NP-težek; prepovedana konfiguracija; sled; trace