Résumé - Quels paramètres de motif de graphes sont comptés ?

Quels paramètres de motif de graphes sont comptés ?

2025-07-16 13:55:16

{"Markus Bläser","Radu Curticapean","Julian Dörfler","Christian Ikenmeyer"}

{cs.CC,math.CO,"68Q25, 68R99","G.2.1; F.1.3"}

L'article "Quels paramètres de motifs de graphes comptent?" de Markus Bläser, Radu Curticapean, Julian Dörfler et Christian Ikenmeyer explore l'interprétation combinatoire des paramètres de motifs de graphes. Les paramètres de motifs de graphes sont des combinaisons linéaires de fonctions qui comptent les sous-graphe induits d'un graphe fixe H dans un graphe donné G. L'article se concentre sur la détermination des paramètres de motifs de graphes qui ont une interprétation combinatoire, c'est-à-dire s'ils comptent quelque chose de significatif. Le résultat principal de l'article stipule que parmi les combinaisons linéaires de fonctions comptant des sous-graphe induits impliquant uniquement des graphes sans sommets isolés, celles avec des coefficients entiers positifs conservent une interprétation combinatoire. Cela signifie que les paramètres de motifs de graphes avec des coefficients négatifs ne peuvent pas être interprétés comme comptant quelque chose de significatif. L'article utilise des techniques de théorie de la complexité computationnelle, en particulier la classe de complexité #P, pour prouver ses résultats. Il montre que l'évaluation des paramètres de motifs de graphes avec des coefficients négatifs est impossible dans une variante oraculaire de #P, où un graphe implicite est accédé par des requêtes oraculaires. La preuve suit la classification des propriétés de fermeture relativisées de #P par Hertrampf, Vollmer et Wagner, ainsi que le cadre développé par Ikenmeyer et Pak. L'article étend ses techniques des graphes aux structures relationnelles, y compris les graphes colorés. Il introduit des paramètres de motifs sur les catégories qui comptent les occurrences de sous-objets dans la catégorie. Ensuite, il prouve un théorème de dichotomie général qui caractérise quels tels paramètres ont une interprétation combinatoire. En utilisant des résultats connus en théorie de Ramsey pour les catégories, il obtient une dichotomie pour les paramètres de motifs des espaces vectoriels finis ainsi que les ensembles de paramètres. L'article contribue à la compréhension de la complexité des problèmes de comptage en combinatoire et en théorie de la complexité. Il fournit un cadre pour caractériser quels paramètres de motifs de graphes ont une interprétation combinatoire et montre le pouvoir des techniques de la théorie de la complexité computationnelle dans l'analyse des problèmes de comptage.