Geodesic
Forbidden configurations: Finding the number predicted by the Anstee-Sali conjecture is NP-hard
Ars Mathematica Contemporanea, Tome 10 (2016) no. 1, pp. 1-8.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.438.300
Keywords: Forbidden configuration, hypergraph, trace, NP-hard, NP-complete, Anstee-Sali conjecture. 
@article{10_26493_1855_3974_438_300,
     author = {Miguel Raggi},
     title = {Forbidden configurations: {Finding} the number predicted by the {Anstee-Sali} conjecture is {NP-hard}},
     journal = {Ars Mathematica Contemporanea},
     pages = {1--8},
     publisher = {mathdoc},
     volume = {10},
     number = {1},
     year = {2016},
     doi = {10.26493/1855-3974.438.300},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.438.300/}
}
TY  - JOUR
AU  - Miguel Raggi
TI  - Forbidden configurations: Finding the number predicted by the Anstee-Sali conjecture is NP-hard
JO  - Ars Mathematica Contemporanea
PY  - 2016
SP  - 1
EP  - 8
VL  - 10
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.438.300/
DO  - 10.26493/1855-3974.438.300
LA  - en
ID  - 10_26493_1855_3974_438_300
ER  - 
%0 Journal Article
%A Miguel Raggi
%T Forbidden configurations: Finding the number predicted by the Anstee-Sali conjecture is NP-hard
%J Ars Mathematica Contemporanea
%D 2016
%P 1-8
%V 10
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.438.300/
%R 10.26493/1855-3974.438.300
%G en
%F 10_26493_1855_3974_438_300
Miguel Raggi. Forbidden configurations: Finding the number predicted by the Anstee-Sali conjecture is NP-hard. Ars Mathematica Contemporanea, Tome 10 (2016) no. 1, pp. 1-8. doi : 10.26493/1855-3974.438.300. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.438.300/

Cité par Sources :