Forbidden configurations: Finding the number predicted by the Anstee-Sali conjecture is NP-hard

Miguel Raggi

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.

Full Text:

PDF ABSTRACTS (EN/SI)


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