Rapport sur l'état de mes recherches

1. Invariants des ensembles partiellement ordonnés gradués: Une grande partie de ma recherche la plus récente porte sur les invariants des ensembles partiellement ordonnés gradués en général, ou sur une certaine sous-classe d'eux en particulier.
1.1 Des drapeaux dans les ensembles partiellement ordonnés gradués: Dans notre article "Linear inequalities for flags in graded partially ordered sets" avec L. Billera nous montrons que la clôture du cône convexe engendré par tous les vecteurs f drapeau des ensembles partiellement ordonnés gradués est polyhédral. En particulier, nous détérminons toutes les inégalités définissant une facette du cône polaire qui donne toutes les fonctinnels positives d'enumérations des chaînes pour cette classe d'ensembles partiellement ordonnés. Celles-ci sont en bijection avec les antichaînes d'intervals sur l'ensemble des rangs, et sont ainsi comptés par les nombres de Catalan. De plus, nous montrons que la convolution introducit par Kalai assigne des rayons extrêmes aux paires de rayons extrêmes dans la plûpart des cas. Nous décrivons les inégalités les plus fortes possibles pour les ensembles partiellement ordonnés gradués dont le rang est au plus 5. En général, la même question semble mener à un problème extrêmement difficile de l'optimisation combinatoire.
Nous avons continué cette recherche dans l'article "Decompositions of partially ordered sets". Nous montrons que pour tout ensemble partiellement ordonneé gradué P, le complexe simplicial dont les faces sont les chaînes de P, possède d'un effeuillage "faible" tel que l'intersection de chaque cellule avec les cellules attachées auparavant est homotopique à une boule ou à une sphère. En généralisant la technique d'étiquettage utilisée dans la preuve du notre téorème principal sur la clôture du cône convexe engendré par tous les vecteurs f drapeau des ensembles partiellement ordonnés gradués, nous introdusions la notion d'un étiquettage des chaînes et des arêtes "avec la propriété du premier atome". Ces étiquettages generalisent les effeuilages lexicographiques, introduits par Björner et Wachs. Une autre sous-classe de ces étiquettages nous permet de décrire la clôture du cône convexe engendré par tous les vecteurs f drapeau des ensembles partiellement ordonnés gradués planaires, en proposant une analogue planaire de la notion du vecteur h. Il se revèle que, pour les ensembles partiellement ordonnés planaires ayant la propriété Cohen-Macaulay, les deux vecteurs h sont égaux, et le cône des vecteurs h est un orthant dont la dimension est un nombre de Fibonacci.
1.2 Permutations d'André et index cd d'ensembles partiellement ordonnés eulériens, cubiques et simpliciaux: Dans mon article "On the cd-variation polynomials of André and simsun permutations" (Discrete & Computational Geometry, 16 (1996), 259-276) je démontre une conjecture de Stanley qui raffine le théorème de Purtill sur l'index cd d'une algèbre booléenne. Je définis une nouvelle classe de permutations d'André signées, et j'étends la notion de la variation cd aux permutations signées d'une nouvelle manière. Ces permutations d'André signées me permettent non seulement de donner une formule pour l'index cd de l'ensemble partiellement ordonné des faces d'un cube, mais elles apparaissent aussi comme un système de représentants des orbites pour une généralization signée de l'action, définie par Foata et Strehl, d'un groupe commutatif sur les permutations.

J'ai continué cette recherche avec R. Ehrenborg. Dans notre article "Flags and shellings of Eulerian cubical posets", nous démontrons un analogue cubique du théorème de Stanley, qui exprime l'index cd d'un ensemble partiellement ordonné simplicial eulérien en fonction de son vecteur h. Notre résultat implique que, si le vecteur h cubique de Ron Adin est positif pour les complexes cubiques de Cohen-Macaulay, alors la conjecture de positivité de l'index cd des ensembles partiellement ordonnés ayant la propriété Gorenstein* est vraie dans le cas cubique. Nous montrons un analogue cubique d'une conjecture de Stanley, portant sur le rapport entre l'index cd de la semisuspension des composants d'effeuillage d'un complexe simplicial, et les polynômes de variation réduite de certaines sous-classes des permutations d'André. La notion de permutation d'André signée utilisée dans ce résultat est une généralisation commune de deux définitions antérieures des permutations d'André signées. Le résumé de cet article a été présenté au 7-ème colloque international Séries Formelles et Combinatoire Algébrique à Paris en mai 1995.
Dans notre article "Permutation trees and variation statistics" (à paraître dans European Journal of Combinatorics) avec E. Reiner nous étudions des représentations de permutations par des arbres binaires avec le but de donner une preuve combinatoire du résultat de Purtill sur l'égalité entre la variation cd totale des permutations d'André et la variation ab totale de toutes les permutations. Inspiré par la démonstration de Purtill, nous introduisons une nouvelle action de groupe "à la Foata-Strehl" sur les permutations. Cette action nous permet de donner une preuve élémentaire du théorème de Purtill, et d'établir une bijection entre les permutations d'André de premier type et les permutations alternantes qui commencent avec une descente. Une version modifié de notre action de groupe nous améne à l'étude d'une nouvelle classe des permutations d'André qui ont une structure ressemblant à celle des permutations "simsun".
1.3 Invariants des complexes cubiques: Dans mon article "On the Stanley ring of a cubical complex" (Discrete & Computational Geometry 14 (1995), 305-330), j'examine les propriétés d'un anneau défini pour les complexes cubiques de façon analogue à l'anneau de Stanley-Reisner. Je calcule la série de Hilbert de cet anneau en termes du vecteur f, et je démontre que, si on prend l'idéal initial de l'idéal de définition par rapport à l'ordre lexicographique inverse des termes, on obtient alors les relations définissant l'anneau de Stanley-Reisner de la triangulation du complexe cubique, obtenue "en tirant les sommets". En utilisant une ancienne idée de Hochster, je prouve que cet anneau a la propriété de Cohen-Macaulay si le complexe admet un effeuillage. Je démontre de plus que son idéal de définition est engendré par des quadriques si ce complexe est aussi le sous-complexe du complexe du bord d'un polytope cubique. Je présente un analogue cubique aux complexes simpliciaux de Cohen-Macaulay équilibrés : la classe des complexes cubiques avec un effeuillage, dont les arêtes peuvent être orientées de sorte que les arêtes "parallèles" pointent "vers la même direction". En utilisant les résultats de Stanley sur les complexes simpliciaux de Cohen-Macaulay complètement équilibrés, ainsi que le système de générateurs homogènes de degré deux de l'idéal de définition, j'obtiens un ensemble infini d'exemples vérifiant une conjecture de Eisenbud, Green et Harris. Cette conjecture affirme que le vecteur h du quotient d'un anneau polynômial de n variables par un idéal contenant un système de paramètres homogènes de degré deux de n éléments est le vecteur f d'un complexe simplicial.
Soit I un invariant des complexes cubiques qui peut être exprimé comme une combinaison linéaire des nombres des faces de différentes dimensions. Dans mon article "Invariants des complexes cubiques" (Annales des Sciences Mathématiques du Québec, 20 (1996), 35-52) je démontre que, si I ne diminue pas quand on ajoute une nouvelle facette à un effeuillage, alors I est une combinaison linéaire positive des éléments du vecteur h de Ron Adin. Il est bien connu que les éléments du vecteur h torique possèdent cette propriété, et je montre qu'elle est aussi vraie pour le "vecteur h de triangulation" qui provient de la série de Hilbert de l'anneau de Stanley d'un complexe cubique. Ainsi, la positivité du vecteur h de Ron Adin implique la positivité de tout autre vecteur h cubique connu. Je démontre cette positivité pour tout complexe cubique obtenu comme subdivision barycentrique d'une sphère simpliciale. Le résumé de ce travail a été présenté au 8-ème colloque international Séries Formelles et Combinatoire Algébrique à Minneapolis en juin 1996.
2. Espèces cubiques et algèbres non-associatives: Comme stagiaire post-doctoral au LACIM j'ai contribué à jeter les fondements de la théorie d'espèces cubiques. La théorie d'espèces classique concerne l'énumération des structures sur un ensemble, l'analogue cubique considère les mêmes questions sur les cubes. Le rôle du groupe symérique est joué par le groupe hyperoctahédral. Dans notre article "Cubical Species and Nonassociative Algebras" (Advances in Applied Mathematics, 21 (1998), 499-546) avec Pierre Leroux et Gilbert Labelle nous analysons des espèces cubiques, des espèces cubiques moléculaires, les opérations fondamentales entre eux, en donnant des exemples explicites. En particulier, nous montrons que le produit cubique induit, d'une manière naturelle, un anneau non-associatif de séries formelles. Nous terminons avec une analyse détaillé de cet anneau non-associatif.
3. Construction combinatoire de l'homologie cubique: Dans l'article "Generalizations of Baxter's theorem and cubical homology" (Journal of Combinatorial Theory A, 69 (1995), 233-287.), écrit avec R. Ehrenborg, nous généralisons un lemme sur des colorations des triangulations d'une sphère de dimension 2 aux dimensions arbitraires et à des pseudo-variétés cubiques (le lemme que nous avons généralisé était utilisé à l'origine pour une démonstration combinatoire du théorème de Brouwer sur le point fixe en dimension 2). Lors des démonstrations de nos théorèmes de coloration, nous avons découvert une approche purement combinatoire de la théorie de l'homologie cubique.
4. Caractérisation algébrique de la représentabilité linéaire des matroïdes: Dans un texte non publié, j'ai donné une caractérisation algébrique de la représentabilité linéaire des matroïdes qui est analogue au résultat de P. Vámos et à la construction des anneaux de parenthèses de N. White. Mon critère pour la représentabilité lineaire est qu'un idéal de déterminants d'un anneau polynômial doit être disjoint du semigroupe des monômes.
5. Sur l'ordonnabilité du produit libre de deux semi-groupes ordonnés: Dans mon article "On ordering the free product of ordered semigroups" (Annales Univ. Sci. Budapestiensis De Rolando Eötvös Nominatae, Tomus XXXII (1989), 233-241) je donne une réponse partielle à la question suivante de I. E. Yu. Gabovich : étant donnés deux semi-groupes ordonnés A et B, quand leur produit libre A*B est-il ordonnable? R. Johnson a prouvé qu'il est suffisant d'exiger que A et B possèdent la propriété de la simplification à droite et à gauche, et qu'aucun d'eux ne contienne d'éléments idempotents. Gabovich a démontré qu'il est nécessaire que l'un des deux ne contienne pas d'idempotent.
J'ai montré qu'il est nécessaire que ni A ni B ne contienne d'idempotent et que les deux semi-groupes doivent avoir la propriété de simplification à droite (resp. à gauche). Ainsi nous obtenons une condition nécessaire et suffisante dans le cas des semi-groupes commutatifs. Dans le cas général, je montre qu'aucune autre condition nécessaire ne s'impose simultanément à A et à B.
6. Le diamètre des graphes de Cayley aléatoires du groupe symétrique: L. Babai conjecture qu'il existe une constante absolue c₁ telle que, étant donné un groupe simple quelconque G et un système de générateurs S de G, le diamètre du graphe de Cayley Gamma(G,S) est inférieur ou égal à (ln|G|)^c₁. En particulier, il existerait une constante c₂ telle que l'on a diam Gamma(A_n,S)<= n^c₂ pour G=A_n , le groupe alterné de degré n. Ceci impliquerait le même énoncé pour le groupe symétrique G=S_n. La meilleure borne supérieure connue de diam Gamma(G,S) pour G=A_n ou S_n était exp( sqrt nln n(1+o(1)). (Dû à L. Babai et Á. Seress.)
Dans notre article "On the Diameter of Random Cayley Graphs of the Symmetric Group" (Combinatorics, Probability & Computing 1 (1992), 201-208) avec L. Babai nous démontrons que, lorsqu'une paire aléatoire d'éléments de S_n est donnée, le graphe de Cayley du groupe et de ces deux générateurs est presque toujours au plus
exp((1/2+o(1)) (ln² n). (L'expression "presque toujours" veut dire que la probabilité de l'événément contraire converge vers zéro quand n tend vers l'infini.) En tenant compte d'un résultat de Dickson qui montre qu'une paire aléatoire de permutations engendre presque toujours au moins A_n, nous obtenons une borne supérieure pour diam Gamma(A_n,S), valable pour presque tout (A_n,S), et qui est beaucoup plus basse que la meilleure borne supérieure détérministe connue.