Добірка наукової літератури з теми "Matrices laplaciennes"

International audience We give a new formula for the weighted high-dimensional tree-numbers of matroid complexes. This formula is derived from our result that the spectra of the weighted combinatorial Laplacians of matroid complexes consist of polynomials in the weights. In the formula, Crapo’s $\beta$-invariant appears as the key factor relating weighted combinatorial Laplacians and weighted tree-numbers for matroid complexes. Nous présentons une nouvelle formule pour les nombres d’arbres pondérés de grande dimension des matroïdes complexes. Cette formule est dérivée du résultat que le spectre des Laplaciens combinatoires pondérés des matrides complexes sont des polynômes à plusieurs variables. Dans la formule, le $\beta$;-invariant de Crapo apparaît comme étant le facteur clé reliant les Laplaciens combinatoires pondérés et les nombres d’arbres pondérés des matroïdes complexes.

International audience We aim to generalize a theorem on the number of rooted spanning forests of a highly symmetric graph to the case of asymmetric graphs. We show that this can be achieved by means of an identity between the minor determinants of a Laplace matrix, for which we provide two different (combinatorial as well as algebraic) proofs in the simplest case. Furthermore, we discuss the connections to electrical networks and the enumeration of spanning trees in sequences of self-similar graphs. Nous visons à généraliser un théorème sur le nombre de forêts couvrantes d'un graphe fortement symétrique au cas des graphes asymétriques. Nous montrons que cela peut être obtenu au moyen d'une identité sur les déterminants mineurs d'une matrice Laplacienne, pour laquelle nous donnons deux preuves différentes (combinatoire ou bien algébrique) dans le cas le plus simple. De plus, nous discutons les relations avec des réseaux électriques et l'énumération d'arbres couvrants dans de suites de graphes autosimilaires.

The $\textit{simplicial rook graph}$ $SR(d,n)$ is the graph whose vertices are the lattice points in the $n$th dilate of the standard simplex in $\mathbb{R}^d$, with two vertices adjacent if they differ in exactly two coordinates. We prove that the adjacency and Laplacian matrices of $SR(3,n)$ have integral spectra for every $n$. We conjecture that $SR(d,n)$ is integral for all $d$ and $n$, and give a geometric construction of almost all eigenvectors in terms of characteristic vectors of lattice permutohedra. For $n \leq \binom{d}{2}$, we give an explicit construction of smallest-weight eigenvectors in terms of rook placements on Ferrers diagrams. The number of these eigenvectors appears to satisfy a Mahonian distribution. Le $\textit{graphe des tours simplicials}$ $SR(d,n)$ est le graphe dont les sommets sont les points du réseau dans le $n$ième dilation du simplexe standard dans $\mathbb{R}^d$ ; deux sommets sont adjacents s’ils diffèrent dans exactement deux coordonnées. Nous montrons que tous les valeurs propres des matrices d’adjacence et laplacienne de $SR(3,n)$ sont entiers, pour tous les $n$. Nous conjecturons que les valeurs propres sont entiers pour tous $d$ et $n$, et donnons une construction géometrique de presque tous les vecteurs propres en termes des vecteurs caractéristiques de permutoèdres treillis. Pour $n \leq \binom{d}{2}$, nous donnons une construction explicite des vecteurs propres de plus petits poids en termes desplacements des tours sur diagrammes de Ferrers. Le nombre de ces vecteurs propres semble satisfaire une distribution Mahonian.

Avec la croissance exponentielle de la quantité de données, l’échantillonnage est une méthode pertinente pour étudier les populations. Parfois, nous avons besoin d’échantillonner un grand nombre d’objets d’une part pour exclure la possibilité d’un manque d’informations clés et d’autre part pour générer des résultats plus précis. Le problème réside dans le fait que l’échantillonnage d’un trop grand nombre d’individus peut constituer une perte de temps.Dans cette thèse, notre objectif est de chercher à établir des ponts entre la statistique et le k-processus ponctuel déterminantal(k-DPP) qui est défini via un noyau. Nous proposons trois projets complémentaires pour l’échantillonnage de grands ensembles de données en nous basant sur les k-DPPs. Le but est de sélectionner des ensembles variés qui couvrent un ensemble d’objets beaucoup plus grand en temps polynomial. Cela peut être réalisé en construisant différentes chaînes de Markov où les k-DPPs sont les lois stationnaires.Le premier projet consiste à appliquer les processus déterminantaux à la sélection d’espèces diverses dans un ensemble d’espèces décrites par un arbre phylogénétique. En définissant le noyau du k-DPP comme un noyau d’intersection, les résultats fournissent une borne polynomiale sur le temps de mélange qui dépend de la hauteur de l’arbre phylogénétique.Le second projet vise à utiliser le k-DPP dans un problème d’échantillonnage de sommets sur un graphe connecté de grande taille. La pseudo-inverse de la matrice Laplacienne normalisée est choisie d’étudier la vitesse de convergence de la chaîne de Markov créée pour l’échantillonnage de la loi stationnaire k-DPP. Le temps de mélange résultant est borné sous certaines conditions sur les valeurs propres de la matrice Laplacienne.Le troisième sujet porte sur l’utilisation des k-DPPs dans la planification d’expérience avec comme objets d’étude plus spécifiques les hypercubes latins d’ordre n et de dimension d. La clé est de trouver un noyau positif qui préserve le contrainte de ce plan c’est-à-dire qui préserve le fait que chaque point se trouve exactement une fois dans chaque hyperplan. Ensuite, en créant une nouvelle chaîne de Markov dont le n-DPP est sa loi stationnaire, nous déterminons le nombre d’étapes nécessaires pour construire un hypercube latin d’ordre n selon le n-DPP
With the exponentially growing amount of data, sampling remains the most relevant method to learn about populations. Sometimes, larger sample size is needed to generate more precise results and to exclude the possibility of missing key information. The problem lies in the fact that sampling large number may be a principal reason of wasting time.In this thesis, our aim is to build bridges between applications of statistics and k-Determinantal Point Process(k-DPP) which is defined through a matrix kernel. We have proposed different applications for sampling large data sets basing on k-DPP, which is a conditional DPP that models only sets of cardinality k. The goal is to select diverse sets that cover a much greater set of objects in polynomial time. This can be achieved by constructing different Markov chains which have the k-DPPs as their stationary distribution.The first application consists in sampling a subset of species in a phylogenetic tree by avoiding redundancy. By defining the k-DPP via an intersection kernel, the results provide a fast mixing sampler for k-DPP, for which a polynomial bound on the mixing time is presented and depends on the height of the phylogenetic tree.The second application aims to clarify how k-DPPs offer a powerful approach to find a diverse subset of nodes in large connected graph which authorizes getting an outline of different types of information related to the ground set. A polynomial bound on the mixing time of the proposed Markov chain is given where the kernel used here is the Moore-Penrose pseudo-inverse of the normalized Laplacian matrix. The resulting mixing time is attained under certain conditions on the eigenvalues of the Laplacian matrix. The third one purposes to use the fixed cardinality DPP in experimental designs as a tool to study a Latin Hypercube Sampling(LHS) of order n. The key is to propose a DPP kernel that establishes the negative correlations between the selected points and preserve the constraint of the design which is strictly confirmed by the occurrence of each point exactly once in each hyperplane. Then by creating a new Markov chain which has n-DPP as its stationary distribution, we determine the number of steps required to build a LHS with accordance to n-DPP