339 articles
Cet article démontre que la conjecture de Lovász est vérifiée pour les graphes de Cayley suffisamment denses en prouvant l'existence d'un cycle hamiltonien pour tout graphe de Cayley connexe à sommets de degré , grâce à une nouvelle preuve évitant le lemme de régularité de Szemerédi au profit d'un lemme de régularité arithmétique spécialisé.
Cet article étudie la distribution de l'indice de profondeur sur les couplages parfaits, en fournissant une description combinatoire et un polynôme générateur, et démontre que cette statistique est équidistribuée avec la fonction de rang de l'ordre de Bruhat.
Cet article démontre que la conjecture alternative des arbres, initialement formulée pour l'embeddabilité, est vérifiée pour la relation de mineur de graphes.
Cet article présente une version généralisée du théorème de l'arbre matriciel pour les graphes dirigés avec des sommes de colonnes non nulles, permettant de relier les déterminants et les mineurs d'une matrice à des sommes pondérées d'arborescences et de forêts, avec des applications à l'évolution temporelle des systèmes discrets et au calcul des déterminants.
Cet article introduit le nombre de carton pour étudier la complexité computationnelle du nombre de brouillage, démontrant qu'il n'admet pas de certificats NP, en caractérisant des familles de graphes pour lesquels une approximation polynomialle est possible, en prouvant la tractabilité paramétrée de sa version disjointe, et en établissant que l'encombrement des sommets borne le nombre de brouillage, ce qui permet de nouvelles bornes sur la largeur arborescente des graphes linéaires et le nombre de brouillage des graphes planaires.
Cet article développe des outils pour l'étude quantitative des arbres couvrants minimaux (MST) aléatoires, en considérant des poids indépendants tirés d'une distribution unique ou de distributions arbitraires formant des mesures produit.
Cet article étudie les propriétés structurelles et spectrales des graphes d'Engel et co-Engel de groupes finis, en établissant des résultats sur la détermination du graphe dirigé par le graphe non orienté, l'identification des éléments d'Engel gauches comme noyau du sous-groupe de Fitting, et la classification des groupes non-Engel dont le graphe co-Engel réduit possède un nombre de clique faible et est torique ou projectif.
Cet article établit une règle de Murnaghan-Nakayama pour les caractères irréductibles de l'algèbre de Hecke cyclotomique sur les éléments standards de Shoji, fournissant ainsi une méthode combinatoire directe pour calculer leur table complète et permettant d'obtenir de nouvelles formules d'orthogonalité et d'application.
Cet article étudie les propriétés du nombre chromatique linéaire et établit des bornes améliorées pour cette mesure dans plusieurs classes de graphes, en réponse à une conjecture liant ce paramètre à la profondeur d'arbre.
Cet article établit des bornes extrémales précises pour les indices d'irrégularité d'Albertson et Sigma sur les arbres à séquences de degrés croissants, démontrant que les arbres en forme de chenille constituent les configurations optimales et mettant en évidence une croissance quadratique de l'indice Sigma par rapport à la croissance linéaire de l'indice d'Albertson.
Cet article établit une séparation exponentielle entre les nombres chromatiques quantique et classique pour les graphes de Hamming et les graphes de Hadamard généralisés, en déterminant les nombres chromatiques quantiques exacts via de nouvelles constructions de représentations orthogonales et l'analyse spectrale, tout en prouvant des bornes inférieures classiques par la méthode des motifs d'intersection interdits.
En s'appuyant sur la formule de Hochster et la théorie de Morse discrète de Forman, cet article étudie les nombres de Betti multigradés des plongements de Veronese en les interprétant via l'homologie de complexes simpliciaux pour en déduire des résultats d'annulation et de non-annulation.
Cet article caractérise les familles -intersectantes de plus grande taille dont le nombre de couverture est d'au moins pour suffisamment grand, généralisant ainsi deux résultats de Frankl.
Cet article étend la théorie des biais de longueurs d'accrochage aux partitions -centrales en établissant, par des méthodes combinatoires, des inégalités entre les nombres d'accrochages de différentes longueurs dans ces partitions.
Cet article présente de nouveaux résultats sur les sous-arbres induits entièrement feuillus des pavages de Penrose P2, démontrant qu'ils sont des chenilles et réfutant la conjecture selon laquelle il n'existerait qu'une seule chenille bi-infinie de ce type.
Cet article établit un lien entre les fonctions APN et les ensembles relatifs de différence en démontrant que l'image de certaines fonctions APN 2-to-1 constitue un ensemble relatif de différence, ce qui, via un résultat de Pott, relie également les fonctions APN aux fonctions bent.
Cet article généralise les opérations de sommes convexes et concaves pour les chirotopes afin d'obtenir une estimation asymptotique précise du nombre de triangulations du double cercle en utilisant une équation fonctionnelle et la méthode du noyau.
Cet article établit des seuils de probabilité précis pour qu'un ensemble aléatoire de sous-ensembles forme une base de matroïde, démontre que ces structures sont presque sûrement des matroïdes épars pavants, et améliore les estimations asymptotiques du nombre de matroïdes en permettant au rang de croître avec .
Cet article affine le théorème d'intersection restreinte non uniforme d'Alon-Babai-Suzuki en introduisant une borne multilevel basée sur les non-ombres et en établissant, via une analyse de la support binomiale des polynômes d'annulation, une borne modulaire sans lacune qui démontre que la borne classique n'est pas atteignable pour les résidus consécutifs.
Cet article introduit la nouvelle classe des graphes bipartis-presque-bipartis (BAB-graphs) pour unifier et généraliser les résultats antérieurs sur les graphes presque bipartis et R-disjoints, en décrivant leur structure via la décomposition de Gallai-Edmonds, en établissant une factorisation déterminante de leur matrice d'adjacence qui confirme une conjecture existante, et en déduisant de nouvelles bornes combinatoires.