Le probleme d'etoiles pour graphes est np-complet

Nous appelons problème de ‘recollement de voisinages’ (RV) (‘star problem’ ou ‘problème d'ètoiles’) le problème qui consiste à savoir, étant donnée une famille $\text{V}$ de parties d'un ensemble S, s'il existe un graphe (non orienté et sans boucle) dont la famille de voisinages coïncide avec $\text{V}$. L'objectif de cet article est de montrer que le problème RV est NP-complet. La preuve s'appuiera sur l'èquivalence entre RV et le probléme de trouver un automorphisme d'ordre 2 dans un graphe quelconque (AUT2). La NP-complétude de AUT2 a été démontrée par Anna Lubiw [5].     

Sur le joint d'une famille de graphes

Les graphes envisagés dans cet article sont non orientés, sans boucles ni arês multiples. On désigne par X(G) et E(G) les ensembles de sommets et d'arêtes d'un graphe G; ces ensembles seront toujours finis. Les notations usuelles sont ceiles de Berge [1].Dans [5], Zykov introduit la notion de graphe joint de deux graphes donnés. Une propriété du joint de deux graphes dont l'un est réduit à un sommet est donnée dans [3]; c'est une étude plus générate et systématique que nous présentons ici.     

Random spanning tree

Dans cet article, nous proposons un algorithme de complexité polynomiale pour construire un arbre au hasard qui soit un graphe partiel d'un graphe donné. Il consiste essentielleement à construire une arborescence de rang donné sur ce graphe, l'ensemble des arborescences étant ordonné par rapport aux valeurs croissantes de la racine et à racine égale suivant l'ordre lexicographique du codage utilisé pour les arborescences.     

Polynômes de Degré Minimum connectant deux projections dans une Algébre de Banach

Etant données deux projections p et q dans une algèbre de Banach A réelle ou complexe, qui appartiennent à la même composante connexe de l'ensemble P des projections de A, il existe un polynôme joignant p et q dans P. On cherche le degré minimum d'un tel polynôme. On démontre que si p ? q est inversible, alors le degré minimum est inférieur ou égal à 3. On établit que ce résultat reste vrai, sans l'hypothése que p ? q est inversible, dans le cas où A = M_n(K) (K = R ou C), et on donne une interprétation géométrique de ce dernier résultat pour A = M₂(K).     

Nonexistence of maximal asymptotic union nonbases

Un sous-ensemble $\text{B}$ de Pensemble $\text{F}$ de toutes les parties finies de $\text{N}$ est une U-base asymptotique d'ordre h si chaque élément de $\text{F}$, à un nombre fini d'exceptions près, est l'union de h, pas nécessairement distincts, éléments de $\text{B}$. On démontre qu'une partie $\text{B}$ de $\text{F}$ qui n'est pas une U-base asymptotique d'ordre h ne peut pas vérifier le critère de maximalité ci-dessous: pour tout A appartenant à $\text{F}$|$\text{B}$, $\text{B}$∪{A} soit U-base asymptotique d'ore h.A subcollection $\text{B}$ of the collection $\text{F}$ of all finite subsets of $\text{N}$ is an asymptotic union basis of order h, if all but finitely many sets in $\text{F}$ are unions of h, not necessarily distinct, elements of $\text{B}$. Otherwise, $\text{B}$ is an asymptotic union nonbasis of order h. We prove that no asymptotic union nonbasis $\text{B}$ of order h fulfills the following criterion of maximality: for every A belonging to $\text{F}$ but not to $\text{B}$, $\text{B}$ ∪{A}; is an asymptotic union basis of order h.     

Type des orbites périodiques des flots associés à des lagrangiens optiques homogènes

Résumé. Soit L : T M → ℝ un lagrangien optique et homogène dans la fibre défini sur le fibré tangent d’une variété orientable de dimension n et γ un lacet régulier 1-périodique qui est un point critique non dégénéré d’indice p de l’action lagrangienne associée à L (il lui correspond alors un point périodique (x, v) du flot d’Euler-Lagrange (φ_t )). Soit T une transversale en (x, v) au champ de vecteurs dans la surface d’énergie et P l’application de premier retour de Poincaré dans cette transversale; on montre alors que le nombre de Lefschetz pour P en (x, v) est (−1)^n−1+p. On en déduit que si 2n_h est le nombre de multiplicateurs de Floquet réels strictement positifs et non nuls, alors: n_h = n − 1 + p (mod 2). On explique comment déduire qu’un lagrangien optique quelconque défini sur le fibré tangent d’une variété orientable compacte de dimension paire de π₁ non trivial a une une orbite périodique qui est soit dégénérée, soit a un exposant de Floquet hyperbolique dans tout niveau d’énergie au dessus du niveau critique de Ma?é.      

Nuove considerazioni sulla famiglia delle quadriche generalizzate

Riassunto Si studiano le superficie algebriche d’ordine 2n che toccano il piano all’infinito secondo una conica contatan volte nell’intersezione con detto piano (quadriche generalizzate) e si mettono in rilievo le loro proprietà diametrali.

---

Résumé On étudie les surfaces algébriques d’ordre 2n ayant un contactn-ple avec le plan à l’infini (quadriques généralisées) et l’on s’occupe de leurs propriétés diamétrales.

     

Irreductibilité de certaines représentations de G(x)

Étant donné un groupe localement compact G et un espace mesuré (X, μ) avec μ non atomique, notons G^(x) le groupe des applications mesurables de X dans G ne prenant qu'un nombre fini de valeurs. Il existe une méthode pour construire des représentations unitaires de G^(x) qui soient invariantes (àéquivalence unitaire près) par toutes les permutations de X conservant μ. Cette construction utilise la théorie des produits tensoriels continus de représentations; en gros, on sait associer une telle représentation $\text{U}\text{?}$ à tout triplet (A, b, c) où A est une représentation unitaire de G, b un 1-cocycle pout A et c une application de G dans $\text{R}$ qui vérifie $\text{Im}\text{(b(g) ¦ b(g′)) = c(gg′) ? c(g) ? c(g′)}$. Verchik, Gelfand Graiev ont démontré (Funk. An. igo Priloz.8 (1974), 67–69) que $\text{U}\text{?}$ est irreductible si b(G) est total dans l'espace de A et si de plus G contient un sous groupe compact K tel que b restreint à K soit nul et $\text{A}{}_{\mathrm{¦K}}$ ne contient pas la représentation triviale.Dans le présent article, nous démontrons un théorème de structure du commutant de $\text{U}\text{?}$; pour cela nous utilisons la théorie des formes standards des algèbres de Von Neumann ainsi qu'un théorème de Araki et Woods sur les algèbres booléennes complètes de facteurs de type I. Comme corollaire nous retrouvons le résultat précité de Verchik, Gelfand, Graiev et d'autre part que $\text{U}\text{?}$ est irréductible dès que A (non triviale) a la même propriété et que b n'est pas un cobord.     

Hypergraphes arbores

Un hypergraphe arboré est l'hypergraphe d'une familie de sous-arbres d'un arbre. Un hypergraphe est arboré si, et seulement si, il a la propriété de Helly et sa représentation triangulée; cette derniére propriété est ensuite remplacée par une condition sur les cycles de l'hypergraphe.     

Sur les espaces fonctionnels dont la source est le classifiant d’un groupe de Lie compact commutatif

Résumé Nous montrons dans cet article comment les connaissances acquises sur les espaces fonctionnels de source le classifiant du groupeZ/p ([La2], [DS]) et l’utilisation de MU-résolutions instables permettent d’obtenir des résultats sur les espaces fonctionnels de source le classifiant d’unp-groupe abélien fini ou d’un tore si l’on impose au but d’avoir une cohomologie à coefficientsp-adiques sans torsion. Nous montrons notamment que l’ensemble des classes d’homotopie d’applications du classifiant X d’un tore dans un espace Y simplement connexe dont l’homologie entière est nulle en degré impair et un groupe abélien libre de dimension finie en chaque degré pair, et dont la cohomologie rationnelle est polynomiale, s’identifie à l’ensemble des applications de la K-théorie de Y dans la K-théorie de X qui préservent la structure de λ-anneau. Le premier auteur a bénéficié pendant l’achèvement de ce travail d’une allocation de recherche de l’école Polytechnique.     

Principe local-global pour les zéro-cycles sur certaines fibrations au-dessus d’une courbe: I

Soit X une variété projective lisse sur un corps de nombres, fibrée au-dessus d’une courbe C, à fibres géométriquement intègres. On démontre que, en supposant la finitude de III(Jac(C)), si les fibres au-dessus d’un sous-ensemble hilbertien généralisé satisfont le principe de Hasse (resp. l’approximation faible), alors l’obstruction de Brauer–Manin provenant de la courbe en bas est la seule au principe de Hasse (resp. à l’approximation faible) pour les zéro-cycles de degré 1 sur X. Ceci est appliqué à l’exemple récent de Poonen.     

Quelques proprietes des ensembles de fermetures sur un ensemble ordonne

L'exposé contient deux résultats principaux. Le premier est une caractérisation de la décomposition canonique d'une fermeture par deux conditions. Le second donne une condition nécessaire et suffisante pour que l'ensemble des fermetures supérieures d'un ensemble ordonné E soit un sous inf-demi treillis complet de l'ensemble des parties de E.     

Sur les immeubles triangulaires et leurs automorphismes

Résumé  Les travaux de J. Tits ont conduit à la classification complète des immeubles euclidiens de dimension supérieure ou égale à 3. L’ensemble de ces immeubles à isomorphisme près est dénombrable et paramétré par les corps locaux qui leur correspondent. Dans cet article nous nous intéressons aux immeubles triangulaires, qui sont euclidiens de dimension 2 et pour lesquelles une paramétrisation analogue est impossible. Nous construisons une lamination Λ sur un espace topologique localement compact séparé, dont l’espace des feuilles est l’ensemble des immeubles triangulaires à isomorphisme près. On considère ainsi les immeubles triangulaires comme points d’un espace dont Λ est une désingularisation naturelle. Nous établissons des résultats de chirurgie sur les immeubles triangulaires à données locales fixées. Ils entra?nent par exemple que Λ est topologiquement transitive. Nous montrons qu’un immeuble triangulaire générique au sens de Baire a un groupe d’automorphismes trivial et qu’il contient toutes les géométries locales possibles. L’espace des immeubles triangulaires à isomorphisme près est un nouvel exemple d’espace non commutatif. Le second auteur a été en partie financé par JSPS.     

On chain morphisms of commutative rings

Résumé  On dit qu’un homomorphismef :A →B d’anneaux commutatifs est un morphisme de cha?ne (resp., den-cha?ne pour un entiern ≥ 1) si toute cha?ne d’idéaux premiers (resp., d’au plusn idéaux premiers) deA se relève en une cha?ne d’idéaux premiers deB. Sif est un morphisme den-cha?ne, alorsf n’est pas forcément un morphisme de (n + 1)-cha?ne, même siA etB sont des anneaux intègres, doncf n’est pas un morphisme de cha?ne. Sif est un morphisme den-cha?ne pour toutn, alorsf est un morphisme de cha?ne. Un morphisme de cha?ne n’est pas forcément un morphisme de cha?ne universel. Pour tout entiern ≥ 2,f est universellement un morphisme den-cha?ne si et seulement sif est universellement un morphisme de cha?ne. Un morphisme qui est universellement de cha?ne et universellement incomparable n’est pas nécessairement entier, même siA etB sont des anneaux intègres de dimension 1 (au sens de Krull).      

Ondes asymptotiques non linéaires

Résumé Le terme du premier ordre de l'onde asymptotique a une forme particulièrement simple non seulement quand la solution de base est constante mais aussi, en ce qui concerne sa norme, lorsque les équations dérivent d'un principe variationnel. Par un changement des variables de champ les équations d'évolution d'Euler s'écrivent comme un système symétrique du premier ordre avec second membre antisymétrique dont toutes les matrices sont constantes sauf celle qui multiplie la dérivée temporelle et qui est un double gradient. A Dario Graffi à l'occasion de son 70-ème anniversaire Entrata in Redazione il 15 giugno 1975.     

Sur Les Operateurs Lineaires Qui Transforment la Boule Unite D’Un Espace de Banach En Une Partie Latticiellement Bornee D’Un Espace de Banach Reticule

L’object de cette note est de répondre à un problème posé par N. J. Nielsen, Dissertationes Math.109 (1973). Cette réponse est la suivante:X étant un espace de Banach réticulé minimal,E un espace de Banach tel que l’image de la boule unité par tout opérateur linéaire continu deE dansX soit latticiellement bornée. AlorsE est nécessairement de dimension finie.     

Sur les proportions respectives de triangles uni,bi ou tricolores dans un tricoloriage des arêtes du n-emble

On determine le nombre maximum de triangles bicolores quand n tend vers l'infini, soit $\text{24}\text{25}\text{(}{}^{\mathrm{n}}{}_3\text{)+O(n}{}^2\text{)}$. On prouve aussi que, pour n assez grand, plus d'un triangle sur vingt-neuf est unicolore le methode suivie est susceptible de constituer une approche du probléme posé par une conjecture d'Erdos. Sos et Turan sur le nombre maximum de triangles tricolores.     

Sur les équations d’Halphen et les actions de SL<Subscript>2</Subscript>(C)

Résumé On étudie les aspects locaux et globaux des actions holomorphes de SL₂(C) sur les variétés complexes de dimension trois, à partir de l’étude des algèbres de Lie de champs de vecteurs qui engendrent une action uniforme. On décrit géométriquement et dynamiquement une famille de telles algèbres étudiée par Halphen vers la fin du XIXème siècle. On donne des formes normales pour les actions de SL₂(C) au voisinage des orbites unidimensionnelles. On étudie ensuite les compactifications équivariantes des espaces homogènes de SL₂(C). On prouve que si Γ⊂SL₂(C) est un sous-groupe discret non-élémentaire alors Γ\SL₂(C) admet une compactification équivariante (comme variété complexe) si et seulement si Γ est géométriquement fini et n’a pas d’éléments paraboliques. On démontre que toutes les compactifications équivariantes sont biméromorphiquement équivalentes. De plus, si Γ n’a pas de torsion, Γ\SL₂(C) admet une compactification minimale, obtenue comme quotient d’un ouvert de l’unique compactification biéquivariante de SL₂(C).