Using numerical simulations and combinatorics, this dissertation focuses on connections between random matrix theory and graph theory.We examine the adjacency matrices of three-regular graphs representing one-face maps. Numerical studies have revealed that the limiting eigenvalue statistics of these matrices are the same as those of much larger, and more widely studied classes of random matrices. In particular, the eigenvalue density is described by the McKay density formula, and the distribution of scaled eigenvalue spacings appears to be that of the Gaussian Orthogonal Ensemble (GOE).A natural question is whether the eigenvalue statistics depend on the genus of the underlying map. We present an algorithm for generating random three-regular graphs representing genus zero one-face maps. Our numerical studies of these three-regular graphs have revealed that their eigenvalue statistics are strikingly different from those of three-regular graphs representing maps of higher genus. While our results indicate that there is a limiting eigenvalue density formula in the genus zero case, it is not described by any established density function. Furthermore, the scaled eigenvalue spacings appear to be described by the exponential distribution function, not the GOE spacing distribution.The embedded graph of a genus zero one-face map is a planar tree, and there is a correlation between its vertices and the primitive cycles of the associated three-regular graph. The second half of this dissertation examines the structure of these embedded planar trees. In particular, we show how the Dyck path representation can be used to recast questions about the probabilistic structure of random planar trees into straightforward counting problems. Using this Dyck path approach, we find:1. the expected number of degree k vertices adjacent to j degree d vertices in a random planar tree, 2. the structure of the planar tree's adjacency matrix under a natural labeling of the vertices, and 3. an explanation for the existence of eigenvalues with multiplicity greater than one in the tree's spectrum.

Dans les années 90 Garsia et Haiman ont introduit le $mathfrak S_n$-module des emph{harmoniques diagonales}, c'est à dire les co-invariants de l'action diagonale du groupe symétrique $mathfrak S_n$ sur les polynômes à deux ensembles de $n$ variables. Ils ont proposé la conjecture selon laquelle le caractère de Frobenius bi-gradué de leur module est $abla e_n$, où $abla$ est un opérateur sur l'anneau des fonction symétriques. En 2002, Haiman prouva cette conjecture. Quelques années plus tard, Haglund, Haiman, Loehr, Remmel et Ulyanov proposèrent une formule combinatoire pour la fonction symétrique $abla e_n$, qu'ils appelèrent la emph{conjecture shuffle}. Les objets combinatoires qui y figurent sont les chemins de Dyck étiquetés. Un raffinement emph{compositionnel} de cette formule fut ensuite proposé par Haglund, Morse et Zabrocki. C'était ce raffinement que Carlsson et Mellit réussirent enfin à montrer en 2018, établissant ainsi le emph{théorème shuffle}. La emph{conjecture Delta} est une paire de formules combinatoires pour la fonction symétrique $Delta'_{e_{n-k-1}}e_n$ en termes des chemins de Dyck étiquetés et décorés, qui généralise le théorème shuffle. Elle fut proposée par Hagund, Remmel et Wilson en 2015 est reste aujourd'hui un problème ouvert. Dans la même publication les auteurs proposèrent une formule pour $Delta_{h_m}Delta'_{e_{n-k-1}}e_n$ en termes de chemins de Dyck partiellement étiquetés et décorés, appelé emph{conjecture Delta généralisée}. Nous proposons un raffinement compositionnel de la conjecture Delta en utilisant des nouveaux opérateurs de fonctions symétriques: les opérateurs Theta. Nous généralisons les arguments combinatoires que Carlsson et Mellit utilisèrent pour la preuve du théorème shuffle au contexte de la conjecture Delta. Nous prouvons également la formule pour $Delta_{h_m} abla e_n$ en termes de chemins de Dyck partiellement étiqueté, c'est à dire le cas $k=0$ de la conjecture Delta généralisée. En 2006, Can et Loehr proposèrent la emph{conjecture carré}, exprimant la fonction symétrique $(-1)^{n-1}abla p_n$ en termes de chemins carrés étiquetés. Sergel montra que le théorème shuffle implique la conjecture carré. Nous généralisons le résultat de Sergel en montrant que une des formules de la conjecture Delta généralisée implique une formule combinatoire de la fonction $(-1)^{n-k}Delta_{h_m}Theta_kp_{n-k}$ e / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

No description available.

El tema d'aquesta tesi és l'enumeració de permutacions amb subseqüències prohibides respecte a certs estadístics, i l'enumeració de permutacions que eviten subseqüències generalitzades.Després d'introduir algunes definicions sobre subseqüències i estadístics en permutacions i camins de Dyck, comencem estudiant la distribució dels estadístics -nombre de punts fixos' i -nombre d'excedències' en permutacions que eviten una subseqüència de longitud 3. Un dels resultats principals és que la distribució conjunta d'aquest parell de paràmetres és la mateixa en permutacions que eviten 321 que en permutacions que eviten 132. Això generalitza un teorema recent de Robertson, Saracino i Zeilberger. Demostrem aquest resultat donant una bijecció que preserva els dos estadístics en qüestió i un altre paràmetre. La idea clau consisteix en introduir una nova classe d'estadístics en camins de Dyck, basada en el que anomenem túnel.A continuació considerem el mateix parell d'estadístics en permutacions que eviten simultàniament dues o més subseqüències de longitud 3. Resolem tots els casos donant les funcions generadores corresponents. Alguns casos són generalitzats a subseqüències de longitud arbitrària. També descrivim la distribució d'aquests paràmetres en involucions que eviten qualsevol subconjunt de subseqüències de longitud 3. La tècnica principal consisteix en fer servir bijeccions entre permutacions amb subseqüències prohibides i certs tipus de camins de Dyck, de manera que els estadístics en permutacions que considerem corresponen a estadístics en camins de Dyck que són més fàcils d'enumerar.Tot seguit presentem una nova família de bijeccions del conjunt de camins de Dyck a sí mateix, que envien estadístics que apareixen en l'estudi de permutacions amb subseqüències prohibides a estadístics clàssics en camins de Dyck, la distribució dels quals s'obté fàcilment. En particular, això ens dóna una prova bijectiva senzilla de l'equidistribució de punts fixos en les permutacions que eviten 321 i en les que eviten 132. A continuació donem noves interpretacions dels nombres de Catalan i dels nombres de Fine. Considerem una classe de permutacions definida en termes d'aparellaments de 2n punts en una circumferència sense creuaments. N'estudiem l'estructura i algunes propietats, i donem la distribució de diversos estadístics en aquests permutacions.En la següent part de la tesi introduïm una noció diferent de subseqüències prohibides, amb el requeriment que els elements que formen la subseqüència han d'aparèixer en posicions consecutives a la permutació. Més en general, estudiem la distribució del nombre d'ocurrències de subparaules (subseqüències consecutives) en permutacions. Resolem el problema en diversos casos segons la forma de la subparaula, obtenint-ne les funcions generadores exponencials bivariades corresponents com a solucions de certes equacions diferencials lineals. El mètode està basat en la representació de permutacions com a arbres binaris creixents i en mètodes simbòlics.La part final tracta de subseqüències generalitzades, que extenen tant la noció de subseqüències clàssiques com la de subparaules. Per algunes subseqüències obtenim nous resultats enumeratius. Finalment estudiem el comportament assimptòtic del nombre de permutacions de mida n que eviten una subseqüència generalitzada fixa quan n tendeix a infinit. També donem fites inferiors i superiors en el nombre de permutacions que eviten certes subseqüències.