We study certain questions related to the performance of the Karp-Sipser algorithm on the sparse Erdös-Rényi random graph. The Karp-Sipser algorithm, introduced by Karp and Sipser [34] is a greedy algorithm which aims to obtain a near-maximum matching on a given graph. The algorithm evolves through a sequence of steps. In each step, it picks an edge according to a certain rule, adds it to the matching and removes it from the remaining graph. The algorithm stops when the remining graph is empty. In [34], the performance of the Karp-Sipser algorithm on the Erdös-Rényi random graphs G(n,M = [^cn/₂]) and G(n, p = ^c/_n), c > 0 is studied. It is proved there that the algorithm behaves near-optimally, in the sense that the difference between the size of a matching obtained by the algorithm and a maximum matching is at most o(n), with high probability as n → ∞. The main result of [34] is a law of large numbers for the size of a maximum matching in G(n,M = ^cn/₂) and G(n, p = ^c/_n), c > 0. Aronson, Frieze and Pittel [2] further refine these results. In particular, they prove that for c < e, the Karp-Sipser algorithm obtains a maximum matching, with high probability as n → ∞; for c > e, the difference between the size of a matching obtained by the algorithm and the size of a maximum matching of G(n,M = ^cn/₂) is of order Θ_{log n}(n^1/5), with high probability as n → ∞. They further conjecture a central limit theorem for the size of a maximum matching of G(n,M = ^cn/₂) and G(n, p = ^c/_n) for all c > 0. As noted in [2], the central limit theorem for c < 1 is a consequence of the result of Pittel [45]. In this thesis, we prove a central limit theorem for the size of a maximum matching of both G(n,M = ^cn/₂) and G(n, p = ^c/_n) for c > e. (We do not analyse the case 1 ≤ c ≤ e). Our approach is based on the further analysis of the Karp-Sipser algorithm. We use the results from [2] and refine them. For c > e, the difference between the size of a matching obtained by the algorithm and the size of a maximum matching is of order Θ_{log n}(n^1/5), with high probability as n → ∞, and the study [2] suggests that this difference is accumulated at the very end of the process. The question how the Karp-Sipser algorithm evolves in its final stages for c > e, motivated us to consider the following problem in this thesis. We study a model for the destruction of a random network by fire. Let us assume that we have a multigraph with minimum degree at least 2 with real-valued edge-lengths. We first choose a uniform random point from along the length and set it alight. The edges burn at speed 1. If the fire reaches a node of degree 2, it is passed on to the neighbouring edge. On the other hand, a node of degree at least 3 passes the fire either to all its neighbours or none, each with probability 1/2. If the fire extinguishes before the graph is burnt, we again pick a uniform point and set it alight. We study this model in the setting of a random multigraph with N nodes of degree 3 and α(N) nodes of degree 4, where α(N)/N → 0 as N → ∞. We assume the edges to have i.i.d. standard exponential lengths. We are interested in the asymptotic behaviour of the number of fires we must set alight in order to burn the whole graph, and the number of points which are burnt from two different directions. Depending on whether α(N) » √N or not, we prove that after the suitable rescaling these quantities converge jointly in distribution to either a pair of constants or to (complicated) functionals of Brownian motion. Our analysis supports the conjecture that the difference between the size of a matching obtained by the Karp-Sipser algorithm and the size of a maximum matching of the Erdös-Rényi random graph G(n,M = ^cn/₂) for c > e, rescaled by n^1/5, converges in distribution.

Cette thèse est consacrée à l'étude mathématique de quelques modèles d'équations aux dérivées partielles issues de la physique des plasmas. On s'intéresse principalement à l'analyse théorique de différents régimes asymptotiques de systèmes d'équations cinétiques de type Vlasov-Poisson-Fokker-Planck. Dans un premier temps, en présence d'un champ magnétique extérieur on se concentre sur l'approximation des électrons sans masse fournissant des modèles réduits lorsque le rapport me{mi entre la masse me d'un électron et la masse mi d'un ion tend vers 0 dans les modèles. Suivant le régime considéré, on montre qu'à la limite les solutions vérifient des modèles hydrodynamiques de type convection-diffusion ou sont données par des densités de type Maxwell-Boltzmann-Gibbs, suivant l'intensité des collisions dans la mise à l'échelle. En utilisant les propriétés hypocoercives et hypoelliptiques des équations, on est capable d'obtenir des taux de convergence en fonction du rapport de masse. Dans un second temps, par des méthodes similaires, on montre la convergence exponentielle en temps long vers l'équilibre des solutions du système de Vlasov-Poisson-Fokker-Planck sans champ magnétique avec des taux explicites en les paramètres du modèles. Enfin, on conçoit un nouveau type de schéma volumes finis pour des équations de convection-diffusion non-linéaires assurant le bon comportement en temps long des solutions discrètes. Ces propriétés sont vérifiées numériquement sur plusieurs modèles dont l'équation de Fokker-Planck avec champ magnétique / This thesis is devoted to the mathematical study of some models of partial differential equations from plasma physics. We are mainly interested in the theoretical study of various asymptotic regimes of Vlasov-Poisson-Fokker-Planck systems. First, in the presence of an external magnetic field, we focus on the approximation of massless electrons providing reduced models when the ratio me{mi between the mass me of an electron and the mass mi of an ion tends to 0 in the equations. Depending on the scaling, it is shown that, at the limit, solutions satisfy hydrodynamic models of convection-diffusion type or are given by Maxwell-Boltzmann-Gibbs densities depending on the intensity of collisions. Using hypocoercive and hypoelliptic properties of the equations, we are able to obtain convergence rates as a function of the mass ratio. In a second step, by similar methods, we show exponential convergence of solutions of the Vlasov-Poisson-Fokker-Planck system without magnetic field towards the steady state, with explicit rates depending on the parameters of the model. Finally, we design a new type of finite volume scheme for a class of nonlinear convection-diffusion equations ensuring the satisfying long-time behavior of discrete solutions. These properties are verified numerically on several models including the Fokker-Planck equation with magnetic field