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.