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.     

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.     

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].     

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.     

Dimension de Krull,Nullstellensätze et évaluation dynamique

Résumé. Nous démontrons un Nullstellensatz qui établit une équivalence entre l'existence d'une identité algébrique d'un certain type, d'une part, et l'impossibilité de trouver une suite croissante de variétés irréductibles répondant à certaines contraintes d'autre part. De ce point de vue le Nullstellensatz usuel correspond au cas des variétés réduites à un point. Nous établissons aussi un Nullstellensatz formel du même type, en relation avec les suites croissantes d'idéaux premiers. Un cas particulier important est donné par la notion de suite pseudo régulière, plus générale que la notion de suite régulière. Nous obtenons de cette manière une nouvelle caractérisation de la dimension de Krull d'un anneau : un anneau a une dimension de Krull si et seulement si il existe une suite pseudo régulière de longueur dans l'anneau. Dans les cas où ces résultats peuvent avoir une signification constructive précise, nos preuves y aboutissent constructivement. Nous pensons avoir donné ainsi quelques éléments en vue d'une interprétation constructive de la théorie de la dimension de Krull des anneaux commutatifs. Notre méthode utilise la notion de structure algébrique dynamique introduite dans des articles précédents. Received: 4 October 1999; in final form: 11 October 2000 / Published online: 25 June 2001     

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.     

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).     

Sur les décompositions directes des contractions de l'espace de Hilbert

Soit H un espace de Hilbert séparable, T ∈ $\text{B}$(H) une contraction complètement nonunitaire et H₁ ? H un sous-espace fermé, invariant à T. Le but de cette Note est de trouver une condition nécessaire et suffisante pour qu'il existe un sous-espace fermé H′ ? H, invariant à T et tel que l'espace H se décompose en somme directe $\text{H = H′ ? H}{}_1$ pas nécessairement orthogonale.     

Sur une loi de probabilite conditionelle de kleitman

Nous donnons une généralisation et une démonstration très courte d'un théorème de Kleitman qui dit: Pour toute paire d'idéaux $\text{F}$, (β) d'éléments dans le produit cartésien de k ensembles totalement ordonnés P = [1, 2, … n₁] ? … ? [1, 2, … n_k], nous avons ($\text{|}\text{F}\text{|}\text{|P|}$). ($\text{|(β)|}\text{|P|}\text{) ?}\text{|}\text{F}\text{∩ (β)|}\text{|P|}$ ou en langage probabiliste $\text{Pr(}\text{F}\text{? Pr (}\text{F}\text{|(β))}$.     

On Extremal Permutations AvoidingωN = NN − 1 . . . 1

Dedicated to the memory of Marcel–Paul Schützenberger Cet article présente une étude des permutations qui évitent le motif de la permutation maximaleω_N = NN − 1 . . . 1. Après avoir donné les définitions classiques, nous montrons que l’ensemble de ces permutations est un idéal pour l’ordre de Bruhat faible et faisons l’étude de ses éléments maximaux. Nous exhibons alors un algorithme pour calculer ces éléments et nous montrons que ceux-ci peuvent être obtenus à partir d’un automate. Nous terminons en donnant des estimations asymptotiques de leur nombre. This paper presents a study of permutations avoiding the patternω_N = NN − 1 . . . 1. After recalling the basic definitions, we prove that this set of permutations is an ideal for the weak Bruhat order and begin the study of its maximal elements. We then present an algorithm that generates these elements and find out that they can be obtained from an automaton. Finally, we give some asymptotics about their number.     

Lagrange and the Solution of Numerical Equations

In 1798 J.-L. Lagrange published an extensive book on the solution of numerical equations. Lagrange had developed four versions of a general systematic algorithm for detecting, isolating, and approximating, with arbitrary precision, all real and complex roots of a polynomial equation with real coefficients. In contrast to Newton's method, Lagrange's algorithm is guaranteed to converge. Some of his powerful ideas and techniques foreshadowed methods developed much later in geometry and abstract algebra. For instance, in order to make a more efficient algorithm for isolating roots, Lagrange essentially worked in a quotient ring of a polynomial ring. And to accelerate both the convergence and calculation of his continued fraction expansions of the roots, he employed nonsimple continued fractions and Möbius transformations. Copyright 2001 Academic Press.En 1798 J.-L. Lagrange publié un important traité sur la résolution d'équations numériques. Dans ce traité, Lagrange développe quatre versions d'un algorithme général qui systématiquement détecte, isole, et approxime, avec toute la précision voulue, toutes les racines réelles et complexes d'une équation polynomiale à coefficients réels. Contrairement à la méthode de Newton, l'algorithme de Lagrange converge toujours. Certaines de ses idées et techniques les plus brillantes ont ouvert la voie à des méthodes en géométrie et en algèbre développées beaucoup plus tard. Par exemple, pour augmenter l'efficacité de son algorithme afin d'isoler les racines, Lagrange travaille essentiellement dans un anneau quotient d'un anneau de polynômes. De plus, dans le but d'accélérer à la fois la convergence et les calculs de l'expansion des racines via des fractions continues, il emploie des fractions continues non-simples ainsi que des transformations de Möbius. Copyright 2001 Academic Press.1798 veröffentlichte J.-L. Lagrange ein ausführliches Buch über die Lösung von numerischen Gleichungen. Lagrange entwickelte vier Versionen eines allgemeinen systematischen Algorithmus für die Identifizierung, Isolation, und beliebig genaue Approximation, aller reellen und imaginären Wurzeln einer Polynomgleichung mit reellen Koeffizienten. Im Gegensatz zu Newtons Methode konvergiert Lagranges Algorithmus immer. Einige seiner machtvollen Ideen und Techniken waren Vorläufer von Methoden in der Geometrie und Algebra die erst viel später entwickelt wurden. Zum Beispiel arbeitete Lagrange im Grunde in einem Quotientenring eines Polynomringes um seinen Algorithmus für die Isolation von Wurzeln effizienter zu machen. Und um sowohl die Konvergenz wie auch die Berechnung seiner Kettenbruchexpansion der Wurzeln zu beschleunigen benützte er nichteinfache Kettenbrüche und Möbiustransformationen. Copyright 2001 Academic Press.MSC subject classifications: 01A50; 65-03; 65H05; 65B66; 00A30.     

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.     

Extension de quelques theoremes sur les densites de series d'elements de n a des series de sous-ensembles finis de n

For a sequence A = {A_k} of finite subsets of N we introduce: $\text{δ(A) =}\text{inf}{}_{\mathrm{m?n}}\text{A(m)}\text{2}{}^{\mathrm{n}}$, $\text{d(A) =}\text{lim inf}{}_{\mathrm{n\to \infty }}\text{A(n)}\text{2}{}^{\mathrm{n}}$, where A(m) is the number of subsets A_k ? {1, 2, …, m}.The collection of all subsets of {1, …, n} together with the operation $\text{a ∪ b, (a ∩ b), (a 1 b = a ∪ b ? a ∩ b)}$ constitutes a finite semi-group N^∪ (semi-group N^∩) (group $\text{N}{}^1$). For N^∪, N^∩ we prove analogues of the Erdös-Landau theorem: δ(A+B) ? δ(A)(1+(2λ)^?1(1?δ(A>))), where B is a base of N of the average order λ. We prove for $\text{N}{}^{\mathrm{\cup }}\text{, N}{}^{\mathrm{\cap }}\text{, N}{}^1$ analogues of Schnirelmann's theorem (that δ(A) + δ(B) > 1 implies δ(A + B) = 1) and the inequalities λ ? 2h, where h is the order of the base.We introduce the concept of divisibility of subsets: a|b if b is a continuation of a. We prove an analog of the Davenport-Erdös theorem: if d(A) > 0, then there exists an infinite sequence {A_kr}, where A_kr | A_kr+1 for r = 1, 2, …. In Section 6 we consider for $\text{N∪, N∩, N1}$ analogues of Rohrbach inequality: $\text{2n}\text{? g(n) ? 2}\text{n}$, where g(n) = min k over the subsets {a₁ < … < a_k} ? {0, 1, 2, …, n}, such that every m? {0, 1, 2, …, n} can be expressed as m = a_i + a_j.Pour une série A = {A_k} de sous-ensembles finis de N on introduit les densités: $\text{δ(A) =}\text{inf}{}_{\mathrm{m?n}}\text{A(m)}\text{2}{}^{\mathrm{m}}$, $\text{d(A) =}\text{lim inf}{}_{\mathrm{n\to \infty }}\text{A(n)}\text{2}{}^{\mathrm{n}}$ où A(m) est le nombre d'ensembles A_k ? {1, 2, …, m}. L'ensemble de toutes les parties de {1, 2, …, n} devient, pour les opérations $\text{a ∪ b, a ∩ b, a 1 b = a ∪ b ? a ∩ b}$, un semi-groupe fini N^∪, N^∩ ou un groupe N¹ respectivement. Pour N^∪, N^∩ on démontre l'analogue du théorème de Erdös-Landau: δ(A + B) ? δ(A)(1 + (2λ)^?1(1?δ(A))), où B est une base de N d'ordre moyen λ. On démontre pour $\text{N}{}^{\mathrm{\cup }}\text{, N}{}^{\mathrm{\cap }}\text{, N}{}^1$ l'analogue du théorème de Schnirelmann (si δ(A) + δ(B) > 1, alors δ(A + B) = 1) et les inégalités λ ? 2h, où h est l'ordre de base. On introduit le rapport de divisibilité des enembles: a|b, si b est une continuation de a. On démontre l'analogue du théorème de Davenport-Erdös: si d(A) > 0, alors il existe une sous-série infinie {A_kr}, où A_kr|A_kr+1, pour r = 1, 2, … . Dans le Paragraphe 6 on envisage pour N^∪, $\text{N}{}^{\mathrm{\cap }}\text{, N}{}^1$ les analogues de l'inégalité de Rohrbach: $\text{2n}\text{? g(n) ? 2}\text{n}$, où g(n) = min k pour les ensembles {a₁ < … < a_k} ? {0, 1, 2, …, n} tels que pour tout m? {0, 1, 2, …, n} on a m = a_i + a_j.     

Sur la représentation analytique d’une branche uniforme d’une fonction monogène

Sans résumé La présente note est un extrait des différentes communications qui ont été faites à l’Académie des sciences de Stockholm dans le courant de l’année 1898, et qui ont été publiées sous les titres suivants:Om en generalisering af potensserien (9 Mars 1898).Om den analytiska framst?llningen af en allm?n monogen funktion: F?rsta meddelande (11 Maj 1898); Andra meddelande (11 Maj 1898); Tredje meddelande (14 Sept. 1898).     

Couplage éléments finis-potentiels retardés pour la diffraction électromagnétique par un obstacle hétérogène

Summary. On s'intéresse au calcul du champ électromagnétique diffracté par un obstacle conducteur recouvert d'un matériau hétérogène. On étudie une méthode numérique consistant à coupler une approximation par éléments finis de volumes avec des potentiels retardés de surface. Plusieurs formulations variationnelles espace-temps sont présentées. On établit des résultats de stabilité et de convergence pour la méthode proposée. Received September 28, 1998 / Revised version received June 2, 2000 / Published online March 20, 2001     

Sulla classificazione delle curve algebriche sghembe in base alla determinazione di tutti i multilateri sghembi connessi per ogni ordine e genere

Riassunto In questa Nota si dà un metodo per ottenere il numero ed i tipi di multilateri sghembi di ordinen e generep dati, conn+p−1 vertici di connessione e che sono casi limite di curve algebriche sghembe irriducibili.

---

Résumé Dans la prèsente Note on donne une méthode pour obtenir le nombre et les types des multilatères gauches d'ordren e de genrep donnés, ayantn+p−1 sommets de connexion, et qui sont des cas limites de courbes gauches algébriques irriductibles.

     

Nombres D’Euler, approximants de Padé et constante de Catalan

Résumé Au moyen d’une méthode d’approximation de Padé introduite par Prévost dans [13], nous construisons des familles d’approximations rationnelles rapidement convergentes vers la constante de Catalan G. Bien que cela ne suffise pas à prouver l’irrationalité de G, nous montrons le lien inattendu avec la méthode hypergéométrique récemment mise en avant dans l’étude diophantienne des fonction ζ de Riemann et β de Dirichlet, ce qui nous permet de prouver la ≪ conjecture des dénominateurs ≫ de [17].

---

---

Mathematics Subject Classification Primary—11J99, 41A21, 05A40     

Méthodes spectrales dans une portion de disque

Résumé. On propose une méthode spectrale pour la discrétisation d'équations elliptiques dans une portion de disque, par passage en coordonnées polaires et approximation par des polyn?mes de degréélevé par rapport à chaque coordonnée. On décrit la discrétisation pour deux problèmes modèle: l'équation de Poisson et l'équation du bilaplacien, on en effectue l'analyse et on présente des résultats numériques. Received December 14, 1995