Cette question est motivée par une question MathOverflow de Peng Zhang . Valiant a montré que le comptage des cliques maximales dans un graphique général est # P-complet, mais que se passe-t-il si nous nous limitons aux graphiques d'incomparabilité (c'est-à-dire que nous voulons compter les antichaines maximales dans un poset fini)? Cette question semble assez naturelle pour que je soupçonne qu'elle ait été envisagée auparavant, mais je n'ai pas pu la localiser dans la littérature.
la source