Graph signal processing analyzes signals supported on the nodes of a network with respect to a shift operator matrix that conforms to the graph structure. For shift-invariant graph filters, which are polynomial functions of the shift matrix, the filter response is defined by the value of the filter polynomial at the shift matrix eigenvalues. Thus, information regarding the spectral decomposition of the shift matrix plays an important role in filter design. However, under stochastic conditions leading to uncertain network structure, the eigenvalues of the shift matrix become random, complicating the filter design task. In such case, empirical distribution functions built from the random matrix eigenvalues may exhibit deterministic limiting behavior that can be exploited for problems on large-scale random networks. Acceleration filters for distributed average consensus dynamics on random networks provide the application covered in this thesis work. The thesis discusses methods from random matrix theory appropriate for analyzing adjacency matrix spectral asymptotics for both directed and undirected random networks, introducing relevant theorems. Network distribution properties that allow computational simplification of these methods are developed, and the methods are applied to important classes of random network distributions. Subsequently, the thesis presents the main contributions, which consist of optimization problems for consensus acceleration filters based on the obtained asymptotic spectral density information. The presented methods cover several cases for the random network distribution, including both undirected and directed networks as well as both constant and switching random networks. These methods also cover two related optimization objectives, asymptotic convergence rate and graph total variation.

We present several results for growth functions of ideals of different com- binatorial structures. An ideal is a set downward closed under a containment relation, like the relation of subpartition for partitions, or the relation of induced subgraph for graphs etc. Its growth function (GF) counts elements of given size. For partition ideals we establish an asymptotics for GF of ideals that do not use parts from a finite set S and use this to construct ideal with highly oscillating GF. Then we present application characterising GF of particular partition ideals. We generalize ideals of ordered graphs to ordered uniform hypergraphs and show two dichotomies for their GF. The first result is a constant to linear jump for k-uniform hypergraphs. The second result establishes the polynomial to exponential jump for 3-uniform hypergraphs. That is, there are no ordered hypergraph ideals with GF strictly inside the constant-linear and polynomial- exponential range. We obtain in both dichotomies tight upper bounds. Finally, in a quite general setting we present several methods how to generate for various combinatorial structures pairs of sets defining two ideals with iden- tical GF. We call these pairs Wilf equivalent pairs and use the automorphism method and the replacement method to obtain such pairs. 1

No description available.

No description available.

No description available.

We consider a stochastic differential equation on a domain D in n-dimensional real space, where the associated dynamical system is linear, and D contains a repulsive type stationary point at the origin O. We obtain an exit law for the first exit time of the solution process from a ball of arbitrary radius centered at the origin, which involves additive scaling as in Day (1995). The form of the scaling constant is worked out and shown to depend on the structure of the Jordan form of the linear drift. We then obtain an extension of this exit law to the first exit time of the solution process from the general domain D by considering the exit in two stages: first from the origin O to the boundary of the ball, for which the aforementioned exit law applies, and then from the boundary of the ball to the boundary of D. In this way we are able to determine for which Jordan forms we can obtain a limiting distribution for the first exit time to the boundary of D as the noise approaches 0. In particular, we observe there are cases for which the exit time distribution diverges as the noise approaches 0. / Ph. D.

The behaviour of free-surface gravity waves on small Froude number fluid flow past some obstacle cannot be determined using ordinary asymptotic power series methods, as the amplitude of the waves is exponentially small. An exponential asymptotic method is used by Chapman and Vanden-Broeck (2006) to consider the problem of two-dimensional, steady flow past a submerged obstacle in the small Froude number limit, finding that a steady downstream wavetrainis switched on rapidly across a curve known as a Stokes line. Here, equivalent wavetrains on three-dimensional and unsteady flow configurations are considered, and Stokes switching causedby the interaction between exponentially small free-surface components is shown to play an important role in both cases. The behaviour of free-surface gravity waves is introduced by considering the problem of steady free-surface flow due to a line source. A steady wavetrain is shown to exist in the far field, and the behaviour of these waves is compared to existing numerical results. The problem of unsteady flow over a step is subsequently investigated, with the flow behaviour formulated in terms of Lagrangian coordinates so that the position of the free surface is fixed. Initially, the problem is linearized in the step-height, and the steady wavetrain is shown to spread downstream over time. The position of the wavefront is determined by considering the full Stokes structure present in the problem. The equivalent fully-nonlinear problem is then considered, with the position of the Stokes lines, and hence the wavefront, being determined numerically. Finally, linearized three-dimensional free-surface flow past an obstacle is considered in both the steady and unsteady case. The surface is shown to contain downstream longitudinal and transverse waves. These waves are shown to propagate downstream in the unsteady case, with the position of the wavefront again determined by considering the full Stokes structure of the problem.

We consider the problem of testing whether r (>=2) samples are drawn from the same continuous distribution F(x). The test statistic we will study in some detail is defined as the maximum of the circular differences of the empirical distribution functions, a generalization of the classical 2-sample Kolmogorov-Smirnov test to r (>=2) independent samples. For the case of equal sample sizes we derive the exact null distribution by counting lattice paths confined to stay in the scaled alcove $\mathcal{A}_r$ of the affine Weyl group $A_{r-1}$. This is done using a generalization of the classical reflection principle. By a standard diffusion scaling we derive also the asymptotic distribution of the test statistic in terms of a multivariate Dirichlet series. When the sample sizes are not equal the reflection principle no longer works, but we are able to establish a weak convergence result even in this case showing that by a proper rescaling a test statistic based on a linear transformation of the circular differences of the empirical distribution functions has the same asymptotic distribution as the test statistic in the case of equal sample sizes. / Series: Research Report Series / Department of Statistics and Mathematics

Ce mémoire se veut une synthèse, destinée à la communauté combinatoricienne, de quelques outils développés pour aborder le problème d'Hurwitz ainsi qu'une présentation des résultats récoltés. Le problème d'Hurwitz consiste à évaluer, dans un groupe symétrique, le nombre (dit d'Hurwitz) de factorisations transitives de la permutation identité dont on a imposé le type cyclique des facteurs. Nous décrivons tout d'abord les origines topologiques de ce problème à travers le dénombrement des revêtements ramifiés de la sphère. Nous présentons également un cadre algébrique naturel, le monoïde des permutations scindées, qui permet d'exprimer les nombres d'Hurwitz comme coefficients de structure de l'algèbre de ce monoïde, plus précisément de la sous-algèbre engendrée par les classes de conjugaison, dont une base naturelle est indexée par les multipartitions (ou partitions scindées). La théorie des représentations de cette algèbre fournit un algorithme pour calculer les nombres d'Hurwitz à une partition dont la complexité (minimale, uniforme et exponentielle) est bien meilleure que celle d'une approche naïve. Ce cadre algébrique donne par ailleurs une formule décrivant les séries d'Hurwitz à plusieurs partitions comme polynômes en les séries d'Hurwitz à une seule partition. Nous présentons secondement le cadre géométrique dans lequel s'expriment d'une part la formule ELSV, laquelle décrit les nombres d'Hurwitz à une partition comme fonctions de certaines intégrales, d'autre part un théorème de M. Kazarian exprimant les séries de Hurwitz à une partition comme polynômes en certaines séries formelles dont l'étude asymptotique est achevée. Une fois décrit le fonctionnement de ce cadre intégral, nous récoltons l'asymptotique de tous les nombres d'Hurwitz / This thesis is meant to be a digest, adressed to the combinatorician community, of some tools developped to tackle the problem of Hurwitz, as well as an exhibition of the thus-harvested results. The problem of Hurwitz consists of computing, in a symmetric group, the (so-called Hurwitz) number of transitive factorisations of the identity permutation whose factors have prescribed cyclic types. We first describe the topological layout of this problem through the enumeration of the ramified coverings of the sphere. We also present a natural algebraic frame, the monoid of split permutations, which allows to describe Hurwitz numbers as structure coeffcients of the algebra of this monoid, more precisely of the subalgebra spanned by the conjugacy classes, whose natural basis is indexed by multipartitions (or split partitions). The representation theory of this algebra yields an algoithm to compute one-partition Hurwitz numbers whose complexity (minimal, uniform and exponential) is far better than that of a naive edging about. This algebraic frame yields a formula describing several-partition Hurwitz series as polynomials in one-partition Hurwitz series. We secondly present the geometric frame in which are been expressed on the one hand the ELSV formula, which describes one-partition Hurwitz numbers as functions of some integrals, one the other hand a theorem of M. Kazarian expressing one-partition Hurwitz series as polynomials in some formal power series whose asymptotics is completly understood. Once the using of this integration frame has been described, we derive the asymptotics of all Hurwitz numbers

We apply the data cloning method developed by Lele et al. (2007) to estimate the model of Smets and Wouters (2007). The data cloning algorithm is a numerical method that employs replicas of the original sample to approximate the maximum likelihood estimator as the limit of Bayesian simulation-based estimators. We also analyze the identification properties of the model. We measure the individual identification strength of each parameter by observing the posterior volatility of data cloning estimates, and access the identification problem globally through the maximum eigenvalue of the posterior data cloning covariance matrix. Our results indicate that the model is only poorly identified. The system displays bad global identification properties, and most of its parameters seem locally ill-identified. / Neste trabalho aplicamos o método data cloning de Lele et al. (2007) para estimar o modelo de Smets e Wouters (2007). O algoritmo data cloning é um método numérico que utiliza réplicas da amostra original para aproximar o estimador de máxima verossimilhança como limite de estimadores Bayesianos obtidos por simulação. Nós também analisamos a identificação dos parâmetros do modelo. Medimos a identificação de cada parâmetro individualmente ao observar a volatilidade a posteriori dos estimadores de data cloning. O maior autovalor da matriz de covariância a posteriori proporciona uma medida global de identificação do modelo. Nossos resultados indicam que o modelo de Smets e Wouters (2007) não é bem identificado. O modelo não apresenta boas propriedades globais de identificação, e muitos de seus parâmetros são localmente mal identificados.