Forbidden configurations - Raggi, Miguel (Ars mathematica contemporanea, 2016)
Naj bo ?$F$? (ne nujno enostaven) hipergraf in naj ?$\text{forb}(m, F)$? označuje maksimalno število neusmerjenih povezav, ki jih lahko ima enostaven hipergraf z ?$m$? vozlišči, če ne vsebuje ?$F$? kot podhipergraf. Domneva, ki sta jo postavila Anstee in Sali, napoveduje asimptotsko vedenje ?$\text{forb}(m, F)$? za fiksen ?$F$?. V tem članku dokažemo, da je celo iskanje tega napovedanega asimptotskega vedenja NP-težek problem. To pomeni: če je Anstee-Sali domneva resnična, potem je iskanje asimptotočnega vedenja ?$\text{forb}(m, F)$? NP-težko.
Keywords: Anstee-Sali conjecture; Anstee-Sali domneva; forbidden configuration; hipergraf; hypergraph; NP-complete; NP-hard; NP-poln; NP-težek; prepovedana konfiguracija; sled; trace