47 articles
Ce papier présente HYGENE, la première méthode d'apprentissage profond basée sur la diffusion pour générer des hypergraphes réalistes et diversifiés en utilisant une approche d'expansion progressive locale sur leur représentation bipartite.
Cet article introduit une nouvelle notion de rigidité des polytopes où les longueurs d'arêtes et la coplanarité des faces sont préservées mais les formes des faces peuvent varier, prouvant que les polytopes convexes sont génériquement rigides en dimension 3 tout en conjecturant ce résultat pour toutes les dimensions supérieures ou égales à 3.
Cet article propose une démonstration simplifiée et accessible, dans le langage moderne, du résultat de Ralph Seifert (1971) établissant qu'aucun graphe fonctionnel premier n'existe, confirmant ainsi la conjecture récente selon laquelle tout graphe fonctionnel se décompose en facteurs non premiers.
Les auteurs démontrent qu'une méthode exacte simple résout la quasi-totalité des instances classiques du problème du voyageur de commerce avec fenêtres de temps en moins de dix secondes, révélant ainsi que ces benchmarks ne sont plus représentatifs pour évaluer les performances des algorithmes.
Cet article présente la preuve de la conjecture d'Erdős sur les appariements, un problème majeur en combinatoire extrême concernant la taille maximale d'une famille de sous-ensembles de taille ne contenant pas ensembles disjoints.
Les auteurs démontrent qu'asymptotiquement presque toutes les fonctions vectorielles sur les corps finis possèdent un stabilisateur affine étendu trivial, ce qui implique que le nombre de classes d'équivalence est asymptotiquement égal à l'estimation naïve et que les fonctions avec des stabilisateurs non triviaux constituent un sous-ensemble exponentiellement rare, validant ainsi les stratégies d'échantillonnage aléatoire pour la conception de primitives cryptographiques.
Cet article propose une approche algorithmique basée sur la génération de colonnes pour résoudre le problème de flot multi-commodités à objectif convexe, applicable aux variantes fractionnaires et non fractionnaires, afin d'optimiser la distribution du trafic dans les réseaux de télécommunications en tenant compte de coûts de liaison croissants de manière convexe.
Cet article détermine systématiquement l'indice chromatique circulaire de petits graphes et multigraphes de degré maximum 4, 5 et 6, construit des familles infinies présentant des valeurs spécifiques et réfute des variantes de la « conjecture du gap supérieur » concernant l'absence de graphes dont l'indice chromatique circulaire est juste inférieur à .
Cet article étudie le polynôme de domination du graphe co-maximal de l'anneau des entiers modulo , en dérivant des formules explicites pour certaines puissances de nombres premiers, en établissant des propriétés de unimodalité et de log-concavité, et en bornant les modules de ses racines à l'aide du théorème d'Eneström-Kakeya.
Cet article étudie les instances de Max-Cut pondérées géométriquement sur le graphe complet, établissant un diagramme de phase précis pour les coupes isolées via des polynômes de seuil et conjecturant que ces coupes sont globalement optimales pour .
Cet article présente le spectre d'adjacence pondérée des graphes multipartites complets, caractérise leurs familles à trois valeurs propres distinctes, identifie les matrices intégrales, corrige des résultats antérieurs sur la diminution de l'énergie et du rayon spectral après suppression d'arêtes, résout un problème ouvert concernant l'énergie ISI des graphes multipartites et calcule le spectre des graphes couronnés multipartites.
Cet article identifie trois conditions nécessaires pour l'existence d'une orientation acyclique avec contraintes de parité, définit des classes de graphes où ces conditions sont suffisantes, établit leurs relations d'inclusion et fournit des algorithmes constructifs polynomiaux pour résoudre le problème sur ces classes ainsi que sur les produits cartésiens de chemins et de cycles.
Cet article généralise les résultats de Raman et Ray en démontrant que pour un graphe hôte de genre borné et des sous-graphes croisés-libres, il existe un support de genre borné pour l'hypergraphe d'intersection, offrant ainsi une analyse unifiée pour les problèmes de recouvrement et de coloration sur des surfaces de genre borné.
Cet article étudie la densité d'arêtes des graphes dont les dessins évitent un type de cellule spécifique, établissant des bornes quasi-torales pour toutes les combinaisons de styles de dessins et de types de graphes, et caractérisant complètement les graphes simples admettant un dessin sans cellule non incidente à un croisement.
Cet article présente un cadre de localisation permettant d'améliorer les bornes existantes et de caractériser structurellement les graphes extrémaux pour divers problèmes de théorie des graphes extrémale, notamment ceux liés aux graphes planaires, aux degrés maximaux et aux longueurs de chemins.
Cet article démontre que pour un nombre de arbres phylogénétiques suffisamment petit par rapport à , il existe des ensembles d'arbres dépourvus de structure commune exploitable, obligeant tout réseau à en contenir un nombre de réticulations proche du pire cas théorique, soit .
Ce papier étudie la complexité des automates reconnaissant les relations et les opérations sur les suites -automatiques, établissant un lien entre la complexité des facteurs d'une suite intérieure et celle de ses sous-suites linéaires, tout en résolvant une question récente de Zantema et Bosma et en analysant la complexité de construction de ces automates via l'arithmétique de Büchi.
Cet article établit une preuve complète de la borne supérieure pour le nombre de double domination d'un graphe extérieur maximal, validant ainsi un résultat dont la démonstration précédente était incomplète.
Cet article établit des formules explicites pour les polynômes de position générale de certaines classes de graphes et démontre que la log-concavité et l'unimodalité de ces polynômes sont préservées pour les graphes multipartites complets équilibrés de petite taille ainsi que pour les coronas de divers graphes naturels, tout en identifiant des contre-exemples pour des tailles plus grandes.
Ce papier démontre que l'écart entre la taille minimale d'un circuit booléen et celle d'une formule sur la base AIG est toujours 0 ou 1, caractérisant précisément les conditions d'optimisation et les structures de partage nécessaires pour atteindre cette borne.