The present thesis constructs an alternative framework to online matching algorithms on large graphs. Using the configuration model to mimic the degree distributions of large networks, we are able to build algorithms based on local matching policies for nodes. Thus, we are allowed to predict and approximate the performances of a class of matching policies given the degree distributions of the initial network. Towards this goal, we use a generalization of the differential equation method to measure valued processes. Throughout the text, we provide simulations and a comparison to the seminal work of Karp, Vazirani and Vazirani based on the prevailing viewpoint in online bipartite matching.

3

I could never be grateful enough to my supervisors, Pascal Moyal and Vincent Robin, for their unwavering kindness, their guidance, and mentorship throughout my PhD. These last few years were not easy, especially on the personal level but their feedback, criticism, and more importantly their support were invaluable.

I would like to thank the members of my thesis committee. The remarks of Mr Broutin and Ms Olvera-Cravioto gave me invaluable insights on my work. I thank Ms Gayraud, Ms Ben Hamou, Ms Veber and Mr Perchet for their valuable comments and suggestions whether they were given directly through courses and comments or indirectly through works and conferences.

I am indebted to my colleagues in the Université de Technologie de Compiègne for their insight, their help and their opinions. Especially, I would like to thank Ms Schaefflen from LMAC, Ms Prelle, Ms Kaczkowski and Ms Aaras-Andaloussi from the ED for they were always quick to give me their support in all matters.

I dare not say that I am grateful to my family. I wish to defend before picking a fight upon what is 'normal' to do for each other. What I will say is that I am blessed to have them.

I would also like to thank my friends for their emotional support and encouragement. They know I owe them this PHD and even more.

Thank you all for your contributions and support.

7

Frequently used Notations and Conventions

We introduce several of the notations and conventions later used in the text. All of the notations introduced here will properly be reintroduced in context.

Graph related objects and sets are illustrated using the mathcal calligraphy. Thus, G = (V, E) is a graph on the vertex set V with edge set V. For a node I, the notation N (I) is also often used. It denotes the neighbors of node I apart from itself. Oftentimes, objects will also be indexed by a time/iteration indicator. Thus, N t (I) simply means the neighbors of I at time/iteration t.

N and R are respectively the set of integers and that of real numbers. Both are endowed with their natural topology.

Likewise, for any topological space E, C b (E) (respectively C c (E)) is the space of real valued bounded (respectively compactly supported) functions on E endowed with the uniform topology.

The Borel sigma-algebra B(E) on E is the sigma-algebra generated by the topological open sets and we denote M F (E) (resp. M) the space of finite measures on E (resp. the finite measure with mass ≤ 1). Both the weak (induced by the duality with C b (E)) and vague (induced by C c (E)) topology will be relevant to our work. D(R + , E) is the space of right continuous, left limited functions from R + to E.

A generic probability space Ω, F, P is also used to handle all the random variables.

An E valued random variable is a measurable function from Ω, F, P to (E, B(E)). And we define a random process as D(R + , E) valued random variable. Sometimes, processes are called 'dynamics' or 'algorithms'.

Chapter I Introduction I.1 The early days of matching theory

Considered as one of Leonhard Euler's most notorious papers, 1735's Solutio problematis ad geometriam situs pertinentis presents the solution to a puzzle: Euler established that there was no path which crossed all the seven bridges of Königsberg once and only once. Today, this paper is viewed as the earliest work both in graph theory and in topology. But, where topology broke free of its recreational roots and quickly expanded into its own fundamental branch of mathematics, the history of graph theory is more peculiar. Most of its early developments stayed rooted in recreational puzzles, consequently making it thorny to paint an accurate picture (see [START_REF] Mitsuko | The works of KONIG Dénes (1884-1944) in the domain of mathematical recreations and his treatment of recreational problems in his works of graph theory[END_REF]). In fact, it took more than a century and a half for matchings to become a definitive subject of study in graph theory.

The inception of graph theory as we know is widely attributed to Julius Petersen and Dénes König. Matching theory, an earlier focus of their work, thus became a fundational concept of graph theory. While Petersen worked mostly on regular graphs, he touched matching theory in a oblique way. By Regular graphs, it is meant graphs where all the vertex have the same degree. In 1891, [START_REF] Petersen | Die Theorie der regulären graphs[END_REF] Petersen reformulated an algebraic factorization problem due to Hilbert as a graph factorization problem, already hinting at deeper ties between algebra and the newborn graph theory. A k-factor of a graph G is a subgraph F such that every vertex has exactly degree k in F. In particular, a matching is a 1-factor: each vertex in a matching has exactly one neighbor and thus is matched to it. In the same paper, Petersen remarkably proved that any regular graph of even degree is in fact the reunion of two edge disjoint 2-factors, tying his results to the work of Euler 150 years earlier. More importantly (for matching theory), he noticed that odd degree regular graphs having no more than two cutlines admitted a perfect matching, one that covered all the vertices. I.1. THE EARLY DAYS OF MATCHING THEORY CHAPTER I. INTRODUCTION Petersen then became interested in the Four Colors Theorem (1852), only a conjecture at the time. A detailed account of the early research on the conjecture is given in [R. J. et al., 1976]. In his pursuit of the conjecture, P. G Tait [START_REF] Tait | Xxiii.-note on a theorem in geometry of position[END_REF] in 1880 had claimed that every polyhedral cubic graph could be factorised in three disjoint perfect matchings (perfect means every vertex is covered in the matching). Petersen's answer came 10 years later, in Sur le théorème de Tait [START_REF] Petersen | Sur le théorème de tait[END_REF], and it came in the form of a counterexample, perhaps the single most famous graph in graph theory rightly called The Petersen graph.

Figure I.1: The Petersen Graph

In parallel to the early works of Petersen, another wing of important results had sprouted under the father of graph theory, Dénes König. To this day, this branch stays the most studied part of matching theory. Bipartite matching is a fundamental affectation problem. As an illustration, we provide one of its formulations : the marriage problem. Say n men and n women are to get married, where n is an arbitrary number. Since they live in a conservative society, polyamorous and homosexual relationships are excluded and each person needs to get married to someone they are acquainted with. The marriage problem asks : When is it possible for each individual to get married? or reformulating in graph theoretical terms : Under which conditions does a bipartite graph admit a perfect matching? Again, the study of bipartite matching would find new roots in an algebraic problem. In 1912, Frobenius while working on the reducibility of determinants proved in [START_REF] Frobenius | Über Matrizen aus nicht negativen Elementen[END_REF] that if M is a n × n matrix with either zero or unique entries, then the det(M ) is a factorisable polynomial of the non zero entries if and only if there exists a permutation of the rows and columns of M such that it exhibits a p × (n -p) sized zero block with 0 ≤ p ≤ n. Frobenius' proof was hard to follow at the time and König, only 3 years later in [START_REF] König | Line systems and determinants[END_REF], observing the combinatorial aspect of the reasoning, gave a much simpler proof using bipartite graphs by introducing a new representation today called incidency matrices. In retrospect, this approach is only a natural path to take and again a preface to the deep ties between linear algebra and graph theory. In the 1910s, König only faced the unwillingness of Frobenius to acknowledge the theory of line systems as a useful mathematical theory and his graph-theoretic proof was hence given little credence.

M 1 M 2 M 3 M 4 W 1 W 2 W 3 W 4
Nevertheless, only one year later the same method of using incidency matrices proved fruitful in establishing the first formal result directly addressing matching theory.

Theorem I. 1.1 ([König, 1916]). Every regular bipartite graph of degree k ∈ N is the (edge) disjoint union of k perfect matchings.

In algebraic terms, this theorem meant every bi-stochastic square matrix (where each row and each column have the same sum) with non negative entries had to have a non zero term in its determinant. In particular, it implies that bi-stochastic square matrices are the convex sum of permutation matrices. This is the Birkhoff-Von Neumann theorem and it was rediscovered almost half a decade later by Von Neumann [von Neumann, 1953] and Birkhoff [START_REF] Birkhoff | Three observations on linear algebra. (spanish)[END_REF].

A few months later in 1917, Frobenius published his own follow up result. In [START_REF] Frobenius | Uber zerlegbare determinanten[END_REF], he provided a simpler proof of his first lemma using a stronger theorem on determinants that were identically zero. Perhaps ironically, this theorem came to be known mostly in its combinatorial form as the Marriage Theorem and it is predominantly used in graph theory and in optimization. The marriage theorem stipulates that the marriage problem admits a solution if and only if each subgroup of k men collectively know at least k women. It was also the precursor (in fact, it was discovered to be equivalent to) the single most important characterization theorem for perfect matchings on bipartite graphs: Theorem I.1.2 (Theorem on Distinct Representatives [START_REF] Hall | On representatives of subsets[END_REF]). Let S 1 , ..., S n be a finite collection of sets, there exists a collection of distinct elements x 1 , ..., x n such that x i ∈ S i if and only if every union of k sets contains at least k elements.

During the same time frame, through König's Theorem (1931), König [START_REF] König | Graphen und matrizen[END_REF] established the duality between the maximum matching problem and the minimal edge cover on bipartite graphs (generalized the same year to weighted graphs by Egervàry [START_REF] Egerváry | Matrixok kombinatorius tulajdonságairol[END_REF]). König's theorem inscribes itself in the line of minmax theorems which paved the way to the algorithmic paradigm not only in graph theory, but also in several other combinatorial domains such as linear programming or convex optimization. In fact, in the first graph theory textbook [START_REF] König | Theorie der endlichen und unendlichen graphen, akad. Verlagsgeselschaft[END_REF], König showed that both marriage theorems (by Hall and Frobenius) and Menger's graph connectivity theorem [START_REF] Karl | Zur allgemeinen kurventheorie[END_REF] were direct consequences of his minmax theorem.

I.2 Birth of an algorithmic approach

After König's book, matching theory stagnated until post world war II. Most results were still characterization theorems focused on regular and bipartite graphs. Then the first breakthrough for general graphs happened in 1947 with [START_REF] Tutte | The factorization of linear graphs[END_REF], where Tutte generalized Hall's theorem to all graphs : Theorem I.2.1 (Tutte). Let G = (V, E) a graph. G has a perfect matching if and only if for every subset U of V, the subgraph G \ U has at most |U| odd components (connected components having an odd number of vertices).

It then took Ore eight years [START_REF] Ore | Graphs and matching theorems[END_REF] to follow Tutte's result by a "defect" version of Hall's theorem. Ore's is called a defect version of Hall's theorem because it identifies I.2. BIRTH OF AN ALGORITH-MIC APPROACH CHAPTER I. INTRODUCTION maximum (cardinality) matchings on bipartite graphs instead of perfect matchings. And then, where it took Hall's theorem decades to be generalized to all graphs, Berge [START_REF] Berge | Two theorems in graph theory[END_REF] was able to produce a general defect version of Ore's theorem only one year later: Theorem I.2.2 (Berge). A matching M in a graph G is of maximum cardinality if and only if there is no augmenting path with M (a path where endpoint vertices are unmatched and that alternates between edges in and out the matching).

Figure I.4: Augmentation of a path

More than the identification of maximum matchings, Berge rightfully noticed that his theorem yielded a naive algorithm for finding maximum matchings. He pointed that to build a maximum matching, one simply had to start from any maximal matching M then search for augmenting paths between any two pairs of edges. Once an augmenting path P was found, (M \ P) ∪ (P \ M) was a larger matching: the procedure is called an augmentation (see figure I.4) of the matching and it was to be repeated until a maximum matching was reached. To this day, most maximum matching algorithms are based either around augmentation or the use of equivalent objects to matchings (Maximum Flow for example).

Berge's observation appends the question that has been looming over matching theory for decades. The existence of maximum/perfect matchings could be fully characterized, yet a way to exhibit such objects was still to be explicited. Incidentally, these questions overlapped with the invention of computers immediately after World War II and were followed by a surge of interest in algorithms. It was simpler to build matching algorithms on bipartite graphs, since the basic steps had already been laid in the 1930s by König and Egervàry. Thus, when [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF] and [START_REF] Hall | An algorithm for distinct representatives[END_REF] built the first bipartite matching algorithm, Kuhn named it The Hungarian Method as an homage to both König and Egervary. The hungarian method also provided a way to cast bipartite matching as a linear programming question in the light of a primal-dual setting which could be solved by the simplex method [START_REF] Dantzig | Maximization of linear function of variables subject to linear inequalities. Activity Analysis of Production and Allocation[END_REF]), producing another equivalence for maximum bipartite matching. Almost simultaneously, Ford and Fulkerson published the first papers on The Theory of Network Flows [START_REF] Ford | Maximal flow through a network[END_REF], [START_REF] Ford | A simple algorithm for finding maximal network flows and an application to the hitchcock problem[END_REF] I.3. MODERN DAYS CHAPTER I. INTRODUCTION [START_REF] Ford | Network flow and systems of representatives[END_REF] which again permitted another formulation of the already rich maximum matching problem with the use of the Max Flow Min Cut theorem.

As milestones were being set on bipartite graphs, matching on general graphs turned out to be a considerably more difficult problem. Almost a decade elapsed before Gallai published [START_REF] Gallai | Maximale systeme unabhängiger kanten[END_REF] in 1964. Using another existence theorem, Gallai established that every graph admitted a canonical decomposition in terms of its maximum matchings. The Gallai-Edmonds Structure Theorem proved to be the much needed breakthrough because the next year, [START_REF] Edmonds | Paths, trees, and flowers[END_REF] was headlining BLOSSOM. BLOSSOM was the first non trivial algorithm for maximum matching on general graphs, and it settled as a staple not only in graph theory but also in the burgeoning algorithmic complexity theory. Its complexity set up polynomial as a criteria for performance and efficiency for algorithms.

After 1965, the classical theory of maximum matching mostly settled on using Berge's Theorem in the most way efficient possible like BLOSSOM did. Research is still about improving the search for augmenting paths or attacking matchings using the ever expanding multitude of equivalent formulations (an example is given in Lovász Grötschel et al. [1981]). We defer to [START_REF] Dua | Linear-time approximation for maximum weight matching[END_REF] for an up to date survey of the modern techniques in the theory.

I.3 Modern days

Even as the classical matching theory was settling and computers were being commercialized to the public, the newborn computer science faced its first obstacles. Computers were severely limited by their hardware. In theory, a multitude of algorithms had been devised to solve problems. In practice, only a few were usable because the first computers simply could not handle them. This led to the emergence of newer techniques whose prime focus would be viability.

The first of such techniques that is relevant to our work is randomization (eg. Karp [START_REF] Karp | An introduction to randomized algorithms[END_REF]). Random algorithms had existed alongside the deterministic ones from the early days of the theory. However, randomization as an important technique to drive down the cost of algorithms really started getting traction only after the fifties. In 1946, after a review of the performances of the ENIAC, the first computer, Ulam and later by Von Neumann saw the potential of the use of statistical sampling to simplify calculations. Later, as they needed a codename for their new method, they would rebrand it as the "'Monte-Carlo"' method1 [START_REF] Metropolis | The monte carlo method[END_REF][START_REF] Metropolis | The beginning of the monte carlo method[END_REF]. The Monte Carlo method is today a staple in almost all domains that require complicated calculations, but at its beginnings, the technique only gave a starting push to the use of randomization [START_REF] Solovay | A fast monte-carlo test for primality[END_REF] in 1977 and Rabin [START_REF] Rabin | Probabilistic algorithm for testing primality[END_REF] in 1980 published randomized primality tests.

The second relevant technique is the use of online algorithms. The online setup is defined by the need for algorithms to process their input progressively without total knowledge of the data. It models situations where the resources are limited (for example the first computers were very limited in memory). The performance of online algorithms is then tested against that of offline optimal algorithms, algorithms to which the totality of the input is made available from the start. This is manifested by the competitive ratio, a ratio between the worst case result for the online algorithm and the optimal offline one. Competitive analysis for online algorithms had been first introduced in 1985 by [START_REF] Sleator | Amortized efficiency of list update and paging rules[END_REF] for list updates and paging rules and after the paper of Manasse in 1986[START_REF] Manasse | Competitive algorithms for on-line problems[END_REF], it is, to this day the main approach to the performance analysis of online algorithms. In the 1990s, the theory of online algorithms exploded with its use on various topics [START_REF] Borodin | On the power of randomization in online algorithms[END_REF]; [START_REF] Karp | On-line algorithms versus off-line algorithms: How much is it worth to know the future[END_REF]. In particular, it resulted in the seminal paper for online bipartite matching: An Optimal Algorithm for On-Line Bipartite Matching [START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF] by [START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF][START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF] presented RANKING an optimal2 algorithm for Online bipartite matching. In the paradigm they studied, the graph is split into customers and items.

Customers arrive one by one, and it is the role of the matching algorithm to pick one of the items for a match. The use of RANKING led to the now classical 1 -1/e bound for the matching coverage, namely, the ratio of matched items out of the total set. Theorem I.3.1. The performance of any on-line bipartite matching algorithm is < n(1 -

1 e ) + o(n).
Since then, applications in online advertising prompted the construction of algorithms that are able to beat this benchmark under various conditions. Such algorithms are the the subject of an important line of research, see e.g. [START_REF] Goel | Online budgeted matching in random input models with applications to adwords[END_REF]; [START_REF] Feldman | Online stochastic matching: Beating 1-1/e[END_REF] and references therein. More recently, various extensions of the online bipartite matching problem have been proposed among which, stochastic matching by [START_REF] Borodin | Bipartite stochastic matching: Online, random order[END_REF] (meaning that each edge emanating from the online nodes exists with a given probability), random customer arrivals by [START_REF] Lovasz | Online bipartite matching with random arrivals: An approach based on strongly factor-revealing lps[END_REF], or models with patience times by [START_REF] Brubach | Follow your star: New frameworks for online stochastic matching with known and unknown patience[END_REF]. Because of the importance of online advertisement, online bipartite matching is today, in terms of volume the most used aspect of matching theory [START_REF] Mehta | Online matching and ad allocation[END_REF]).

In computer science, online algorithms went through a rebranding. Streaming algorithms are algorithms that only process a stream of the data. This line of research mainly focuses on the type of input for the stream (either dynamic or enter only), its randomness or its relative size to the whole graph. Thus several authors have worked to apply them to the matching problem (see e.g. [START_REF] Chen | Optimal streaming algorithms for graph matching[END_REF], [START_REF] Farhadi | Approximate maximum matching in random streams[END_REF] and [START_REF] Tirodkar | Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model[END_REF], and references therein).

Meanwhile, newer mathematical techniques introduced newer bounds for matching sizes on certain classes of graphs. These bounds furthered the computations of the competitive ratio of matching algorithms despite being overall graph dependent. The first model of random graph was popularized in the sixties by Erdös and Rényi (reprinted for example in [START_REF] Erdös | On the evolution of random graphs[END_REF]) and Erdös used it for the Probabilistic Method. The probabilistic method is a technique for proving the existence of a graph with certain properties (say a perfect matching) by constructing an appropriate probability space and showing that a randomly chosen element in this space had the desired properties with positive probability. This probability is viewed as a proportion of graphs with the given property on the space. Thus a non zero probability implied the existence of the desired object. In matching theory, the probabilistic method was used by Erdös and Rényi in [START_REF] Erdös | A problem on independent r-tuples[END_REF] to exhibit a size transition for the appearance of a perfect matching on the Erdös-Rényi random graph, almost surely characterizing the parameters at which a perfect matching appeared. The book of [START_REF] Lovász | Matching Theory[END_REF] contains a more precise account of the relevant techniques and how they relate to matching theory.

The usage of random graphs brought the necessary second shift in perspective leading to our work. Coming in the 20th century, Watts and Strogatz had introduced the small world model [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]) and it was followed by the preferential attachment model of [START_REF] Albert | Statistical mechanics of complex networks[END_REF]. These two models led to an explosion in the research because they exhibited properties observed in real world complex networks. Internet, social networks or protein chains all shared the property that they were difficult to describe because of their sheer size. As a consequence, their complete description was utterly impossible both in theory, because there was no unifying definition of limits for graphs, and in practice because it would cost an unfathomable amount of resources to have a complete and precise map of say the internet. This naturally led to a more statistical and local approach to networks : the theory would study the rules by which vertices were locally connected to one another and how those rules were to change when the graph size grew arbitrarily large. This is the so called local limit of graphs (in the Benjamini-Schramm sense). And, oftentimes the edge defining rules were defined through probabilistic means.

Thus, random graphs became the perfect tool for mimicking properties of real networks since they naturally integrate a layer of randomness in their structure, akin to how the structure of complex networks is often studied only through sampling. The chosen random graph model (in our case the configuration model) is then to be viewed as the underlying model producing the complex network under study, similarly to statistics where samples are assumed to be generated from a given law3 .

I.4 Motivation

In this thesis, we present an alternative to online algorithms using the local construction of maximal matchings provided by random graphs. Over the structural randomness of the configuration model, we construct local matching algorithms that are built around the choice of a matching criterion (a preferential choice of edges to add to the matching for every node).

Afterward, we will manage to predict the performance of chosen criteria given a graph (or at least its degree distribution). Moreover, our results apply directly to general graphs instead of being restricted to the usual bipartite matching problem. In the traditional online bipartite matching, there is a layer of randomness that comes from the order of arrivals, from the exploration of the graph. Our goal is to add a second layer, representing the exploration, to the first layer of randomness already acknowledging an uncertainty in the structure of large networks. To capture the randomness of the structure, we use the configuration model. Even for large networks, characteristics like degree distributions are more accessible than the whole topology and have huge effects on the networked systems. Because it emulates such an important characteristic, the configuration model is one of the most important theoretical models in the study of networks. In particular, since it can emulate a uniformly drawn graph from a degree sequence, it strikes an ideal balance between realism and simplicity. Hence, given a matching criterion, we approximate the matching size as a function of the degree sequence of the graph. This is done through a deterministic approximation of a stochastic process representing the matching procedure4 , in the large graph asymptotic. The general idea is as follows: rather than precisely defining and keeping track of the whole geometry of the graph, we generate a graph from the configuration model [START_REF] Bollobás | Random graphs[END_REF] and Hofstad [2016]). To this end, we use a classical uniform pairing procedure of the half-edges of the nodes (a more precise description is given in the next chapter). This construction leads a uniformly drawn realization of a graph having the prescribed degree distribution. In parallel, we simultaneously construct an online matching (meaning in this context, that each edge I.4. MOTIVATION CHAPTER I. INTRODUCTION that is added to the matching cannot be erased afterward) on the resulting graph. This can be viewed as using simultaneously the two layers of randomness: the structure of the graph (1st layer) is discovered alongside the exploration process (2nd layer) associated to the matching criterion.

The whole procedure can be viewed as an exploration of the configuration model, where the edges to be added to the matching are marked following the designated criterion. Our idea of viewing the matching algorithms as exploration processes originate from the course Limites d'échelles de graphes aléatoires [START_REF] Broutin | Cours :limites d'échelles de graphes aléatoires[END_REF] by N. Broutin at Sorbonne Universités. In an adjacent paper [START_REF] Broutin | Asymptotics of trees with a prescribed degree sequence and applications[END_REF] to the course, an encoding for the exploration of trees with prescribed degree distributions is provided. In our case, the interest lied more in the number of marked edges than in the structure of the explored graph. Thus, the marking process is encoded in a different manner.

The simultaneous construction leads to a simple Markov representation, keeping track of the remaining degrees of the nodes that are not yet fully attached to the graph (a definition that will be made precise hereafter), provided that the matching algorithm depends only on these remaining degrees. This will be our preferred encoding of the exploration. We say in that case that the matching algorithm is local. The underlying Markov process is then measure-valued, where each measure is a sum of Dirac masses marking the remaining degrees of the nodes. By doing so, we do not need to keep track of the precise form of the constructed graph, and in fact, we do not need to have access to it. Then, using usual approximation tools for Markov processes, one can identify the approximation of the considered process as the solution of an ordinary differential equation. This results in a generalization, for measure-valued processes, of the celebrated Differential Equation Method, introduced by [START_REF] Kurtz | Solutions of ordinary differential equations as limits of pure jump markov processes[END_REF][START_REF] Kurtz | Extensions of trotter's operator semigroup approximation theorems[END_REF] and later popularized in the random graphs community by [START_REF] Wormald | The differential equation method for random graph processes and greedy algorithms[END_REF]. By doing so, we retrieve an estimate of the resulting matching coverage as a simple function of the latter (deterministic) solution, without knowledge of the precise geometry of the graph at hand. Remarkably, we show hereafter that the resulting matching coverage has the same distribution as the one obtained when applying the corresponding online and local matching algorithm on a previously constructed graph G, conditional on the fact that the resulting graph constructed by the CM is precisely G. As a consequence, our estimate of the matching coverage by the differential equation method, provides a remarkably accurate estimation of the matching coverage of the considered local algorithm on a given graph, a result that we support with simulations.

In fact, at the same moment the present thesis was being written [START_REF] Noiry | Online matching in sparse random graphs: Non-asymptotic performances of greedy algorithm[END_REF] wrote a paper constructing a greedy algorithm on the bipartite configuration model. Their work focused on the bipartite case using a representation of the matching process leaning I.5. LAYOUT OF THE DOCUMENT CHAPTER I. INTRODUCTION on generating functions. Despite using an overall different approach, the empirical results obtained are similar to those obtained in restricting our version to the greedy matching [START_REF] Aoudi | Markovian online matching algorithms on large bipartite random graphs[END_REF]). Hence, our aim in this thesis is a generalization of this approach to general graphs and to broader matching criteria. In any case, both the author and [START_REF] Noiry | Online matching in sparse random graphs: Non-asymptotic performances of greedy algorithm[END_REF] go even deeper in the comparison of this alternative technique to existing methods in online bipartite matching.

The extension of the differential equation method to measure-valued processes, resulting from a simultaneous construction of the CM and an exploration algorithm on the latter, first appeared in a paper by Decreusefond et al. [2012] to describe the propagation of an SIR epidemics on an heterogeneous graph. A closely related idea was then applied in [START_REF] Bermolen | The jamming constant of uniform random graphs[END_REF] to approximate the size of maximal independent sets on graphs with given degree distributions (for a more direct use of the differential equation method on the same topic, see also [START_REF] Brightwell | The greedy independent set in a random graph with given degrees[END_REF]). This led to various extensions, for example to address various coverage problems in CSMA-type algorithms for radio-mobile and ad-hoc communication networks, see [START_REF] Bermolen | Estimating the transmission probability in wireless networks with configuration models[END_REF].

Before that, measure-valued processes Markov processes were first introduced in the queueing literature. Space of measures are amenable to showing weak convergence of sequences of processes under an appropriate scaling, and the exhaustive representation of queuing systems by point measures, in which each Dirac mass typically represents the characteristic of a customer in line, led to fruitful developments in fluid and diffusion approximations of the systems at hand, see e.g. [START_REF] Gromoll | The fluid limit of a heavily loaded processor sharing queue[END_REF] for processor sharing queues, [START_REF] Doytchinov | Real-time queues in heavy traffic with earliest-deadline-first queue discipline[END_REF]; Decreusefond and Moyal [2008a] for queueing systems with impatient customers, Decreusefond and Moyal [2008b] for infinite-server queues, or [START_REF] Kaspi | Law of large numbers limits for many-server queues[END_REF] for many-server queues.

I.5 Layout of the document

This thesis is organized in three main chapters.

In Chapter II, we introduce the framework for the rest of the work. At first, the local marking process is provided for finite deterministic graphs. Here, we build an intuition for the behavior of matching criteria on finite graphs before transposing said criteria to the configuration model. The chapter ends with our first batch of simulations, illustrating the definitions given in the chapter for practical cases.

Chapter III is devoted to the representation of the matching process as a measure valued Markov process. It starts with a theorem linking the exploration of given graphs to that of the configuration model. Then, the properties of the associated process are studied in preparation for Chapter IV. The chapter is closed with a section dedicated to a proper normalization of the dynamic.

Chapter IV presents the main result of our thesis. We are able to prove the convergence of the matching process to a deterministic function. By studying this function, we show that the matching coverage for given criteria converges to a value we are able to compute by solving an ordinary differential equation. This value serves as a predictor for the performance of the given matching criteria. The convergence is also illustrated empirically through a second batch of simulations.

Chapter II

Local Matching Algorithms

The naive algorithm for building a maximal matching consists of the repetition of the following iteration: 1. an edge is added to the matching 2. its neighboring edges are blocked. Maximum matching algorithms would then proceed to progessively augment the resulting maximal matching1 . The present thesis studies local matching criteria and their influence on the size of the first maximal matching produced without augmentation. A matching criterion is a procedure selecting the edge added to the matching at each iteration. And it is local when it depends only on the neighborhood of an edge.

In this chapter, the general formula for the local matching algorithms studied hereafter is provided. Section II.1 defines the local approach on given graphs as a prelude(the graph is considered a realization of the CM that is simple). The context of given graphs can be viewed as conditioning the model by a given structure. Thus, the structure of the graph is known and available, so the edges locally explored and added to matching already exist and are only to be discovered. In II.2, the process is transposed to the configuration model where instead of discovering the graph, it is built alongside the matching, using the uniform pairing procedure (which symbolizes the randomness in structure). Thus, the configuration model serves as a placeholder for large complex networks where complete information is often inaccessible. Finally, we provide a batch of simulations illustration the whole approach and comparing it to the optimal traditional online algorithm.

II.1 Local Matching Algorithms on Given Graphs

For the entirety of this section, G = ( V, E) represents a graph with vertex set V and edge set E. We differentiate given graphs in this section from the configuration model generated ones later by using the˚symbol. Those graphs will be later addressed without A choice function Φ on Ů is a probability law on Ů. A choice following the function Φ I is a random variable I whose law is Φ I . For u ∈ Ů, we write :

P( I = u) := Φ I ( Ů)(u) (II.1)
A matching criterion Φ := (Φ I ( V), Φ I′ ( N ( I))) is a pair of choice functions such that Φ I ( V) chooses a node I among all vertex and Φ I′ ( N ( I)) chooses its match among its neighbors.

A matching criterion defines a method for picking an edge ( I, I′ ) which is later explored and added to the matching. The choice of I fixes a priority order to the exploration of the graph since it dictates the first vertex seen at each iteration, it is then followed by the choice of I′ functionally completing the selection of the edge added to the matching.

Example II.1.1.

The uniform choice on Ů is the choice function where every node is picked with the same probability:

P Ů ( I = u) := unif I ( Ů)(u) = 1 Ů (u) | Ů| (II.2)
The maximal (degree) choice selects uniformly amongst the maximal degree nodes:

P Ů ( I = u) := max I ( Ů)(u) = unif I ( Ůmax )(u) = 1 Ůmax (u) | Ůmax | . (II.3)
If we define the d max ( Ů) = max u∈ Ů d(u) as the maximal degree in Ů, we write

Ůmax := {u ∈ Ů | d(u) = d max ( Ů)}
Likewise the minimal (degree) choice is a uniform choice amongst the minimal degree nodes:

P Ů ( I = u) := min I ( Ů)(u) = unif I ( Ůmin )(u) = 1 Ůmin (u) | Ůmin | . (II.4) where d min ( Ů) = max u∈ Ů d(u) is the minimal degree in Ů, we write Ůmin := {u ∈ Ů | d(u) = d min ( Ů)} II.1. LOCAL MATCHING ALGORITHMS ON GIVEN GRAPHS CHAPTER II. LOCAL MATCHING ALGORITHMS Remark II.1.1.
It is important to stress that we do not count a node among its own neighbors, even when there is a loop. This is to avoid adding loops to the matching. As we will later see, loops will occur in the configuration model and whenever they are marked, the algorithms would no longer produce a matching. Asymptotically, it will be irrelevant since the total number of loops will be negligible compared to the number of marked edges. Nevertheless we have to mention it, since loops appear with positive probability.

Another way to circumvent the problem and produce a matching is to allow loops to be included but to later erase them whenever they are marked.

II.1.2 Local matching through exploration

We now construct the local matching algorithms later considered in this work. Fix a (non-oriented) graph G = ( V, E), where V is the set of nodes and E ⊂ V × V is the set of edges and a matching criterion

Φ := (Φ I ( V), Φ I′ ( N ( I)). Fix the size of V as | V| = n for n ∈ N.
At any iteration t, are given two disjoint subgraphs of G: Gt = ( Ůt , Et ) is the undiscovered part of the graph for our procedure at time t. The nodes of Ůt are said to be available at t. Those are the nodes whose fate still is to be determined.

G′

t = ( Mt , G′ t ) is the matching at time t. It is a 1 -f actor, a subgraph of G in which all nodes have only one neighbor with Mt containing all the matched nodes.

It is also defined as isolated nodes at t, that is nodes which will not be matched at all, because all of their neighbors have been matched. Thus,

V = Ůt ∪ Mt ∪ It . (II.5)
At first, the whole graph is available to be matched, meaning Ů0 = V, M0 = ∅ and I0 = ∅. The matching process has yet to start, we also set E0 = E and E′ 0 = ∅, in a way that G0 = G and G′ 0 = (∅, ∅). The matching algorithm then proceeds by induction, repeating the following procedure:

At any time t ∈ 0, n -1 ,

Step 1. A vertex I is chosen following Φ I ( Ůt )

Step 2. A match for I is selected among the neighbors of I, it is a choice I′ following Step 3. The matched nodes I and I′ as well as their neighboring edges are explored. Those are removed from the unexplored graph (in grey). Specifically, we set Step 4. We set t := t + 1 and go back to step 1.

     Ůt+1 = Ůt \ { I, I′ }, Gt+1 = Induced subgraph of Ůt+1 in Gt , Mt+1 = Mt ∪ { I, I′ }, E′ t+1 = E′ t ∪ {( I, I′ )}, It+1 = It ∪ {v ∈ Gt+1 |d t+1 (v) = 0}. I I′ (

II.1. LOCAL MATCHING ALGORITHMS ON GIVEN GRAPHS CHAPTER II. LOCAL MATCHING ALGORITHMS

At the terminating point t = n, all the nodes are either matched or isolated, begetting

| In | + | Mn | = | V|.
The matching coverage Mn Φ ( G), the proportion of initial nodes that ended up in the matching at the termination time n is expressed as a simple function of the sets we tracked during the matching dynamic.

Mn Φ ( G) = | Mn | n = 1 - | In | n ∈ [0, 1]. (II.6)
Such expression is crucial in the remainder of this work. It expresses the matching proportion as a function of the matching dynamic. Later on, concentration results will allow us to establish the convergence of the matching coverage given any criterion.

We can now introduce the main criteria that have been the focus of our simulations :

Definition II.1.2.
Φ is greedy, denoted Φ = greedy, if both choices of I and I′ are uniform. We can write

greedy = unif I ( V), unif I′ ( N ( I)) . (II.7)
Φ is minimal residual, denoted Φ = minres if I is matched to its lower degree neighbor. The goal here is to obtain a better matching by decreasing the probability of augmenting paths. Since minres matches I to its lowest degree neighbor, it has a better chance of being matched to leaves2 , thus decreasing the chance of creating a situation where both leaves are left out of the matching, creating an augmenting path.

minres = unif I ( V), min I′ ( N ( I)) . (II.

II.2 Local matching on the configuration model

The main feature of complex networks is their size. The larger they get, the more complicated it becomes to access their exact topology. This has prompted researchers to turn to other viewpoints. The local approach to large graphs is one such viewpoint: Even without full information, are there ways to describe the relationships between vertices?

One answer to this question is statistical. If we have access to a descriptor of the graph, for example its degree sequence, it can be used to pick uniformly a similar graph in some sense. If the degree distribution is known for example, one reasonable assumption to make is that typical vertex of the network and their neighborhoods should follow such distribution. From that assumption, concentration techniques can be used to obtain global properties on any procedure that is local. This led to random graph models being used as substitutes for complex networks.

The configuration model [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF]), also known as the uniform pairing model, is one of the most important theoretical models in the study of networks. Because, when conditioned on being simple, it represents a uniform drawing of a graph given its degree sequence, it is both realistic and simple enough to be used in a myriad of situations (Decreusefond et al. [2012] for the spread of an epidemic based on the SIR model or [START_REF] Bermolen | The jamming constant of uniform random graphs[END_REF] for a study of the jamming constant of general graphs). Moreover, the sequential nature of the construction of the configuration model makes the model at hand amenable to the fabrication of local algorithms (Appendix A.1), especially like we intended to do in the first section of the present chapter. This section uses this sequential II.2. LOCAL MATCHING ON THE CONFIGURATION MODEL CHAPTER II. LOCAL MATCHING ALGORITHMS procedure to transpose the local matching algorithms to the configuration model. The algorithms are now built on a model with both layers of randomness.

Set ξ a probability measure on N. Set n be a positive integer and d := (d( 1), ..., d(n)) a n-sample of the probability distribution ξ. We intend d to model the degree sequences of a given graph so it has to be graphic3 . Alternatively, we call µ := i≤n δ d(i) the measure valued representation of d.

Thus, we let V = {v 1 , ..., v n } be the set of nodes of the graph and for all i ∈ 1, n , d(i) being the degree of node v i . A realization of the configuration model consists of giving every vertex v, d(v) half-edges which are to be completed into edges through uniform pairing (see Appendix A.1).

II.2.1 Matching criteria on the CM

Definition II.2.1 (Matching criteria on degree sequences). Let d a degree sequence, we can redefine matching criteria for degree sequences (or equivalently on their measure valued representation) as follows:

A choice function Φ on d is again a probability law on d. A random variable K = d(I) is called choice following the function Φ K when its law is Φ K . Again, let k ∈ d we write :

P(K = k) := Φ K (d)(k).
(II.9) abusing notations, for µ = d∈d δ d , Φ can be written as a measure on M F (N) :

Φ K (µ) := Φ K (d) = k Φ K (d)(k)δ k .
(II.10)

Let µ ′ := v∈N (I) δ d(v) the degree sequence of the neighbors of I. A matching criterion Φ := (Φ K (µ), Φ K ′ (µ ′ ))
is again a pair of choice functions such that a node Φ K (µ) chooses a vertices I of degree K among all vertices and Φ K ′ (µ ′ ) chooses the degree of its match among the degree of its neighbors.

This time, the matching criterion defines the degrees (K, K ′ ) of the edge (I, I ′ ) added to the matching.

Example II.2.1.

The uniform choice on d is the choice function where every degree is picked with the same probability. For k ∈ d, we use d and µ interchangeabily:

II.2. LOCAL MATCHING ON THE CONFIGURATION MODEL CHAPTER II. LOCAL MATCHING ALGORITHMS Figure II.4: A running example: Initial state for d = (3, 2, 1, 4, 2, 2) v 1 v 2 v 3 v 4 v 5 v 6 unif K (µ)(k) := P µ (K unif = k) = ⟨µ, 1 k ⟩ ⟨µ, 1⟩ . (II.11)
The maximal (degree) choice selects uniformly amongst the maximal degrees:

max K (µ)(k) := P µ (K max = k) = 1 dmax (k).
(II.12)

where d max := max d = max i d i with d i ∈ d
Again, the minimal (degree) choice selects uniformly amongst the minimal degrees:

min K (µ)(k) := P µ (K min = k) = 1 d min (k).
(II.13)

where

d min := min d = min i d i with d i ∈ d

II.2.2 The matching process on the CM

We can now set the trackers for the number of available stubs. Stubs (or half edges) are to be paired sequentially uniformly into edges, for all i we set a 0 (v i ) = d(i) and define the following set of initial availabilities:

A 0 = v 1 , a 0 (v 1 ) , • • • , v n , a 0 (n) .
At first, all stubs are available and the G 0 has no edges. We get G 0 := (V, ∅). The matching is empty, and all the edges have to be discovered, hence we also set

M 0 = II.2. LOCAL MATCHING ON THE CONFIGURATION MODEL CHAPTER II. LOCAL MATCHING ALGORITHMS ∅, U 0 = V and G ′ 0 is the empty graph, i.e. G ′ 0 = (∅, ∅).
To define the tempo of our construction, set t as an iteration count. In a similar fashion to the first section, we shall proceed by induction. At iteration t, we are given

A multi-graph G t = (V, E t ) = (M t ∪U t ∪I t , E t )
representing the partially constructed connections between elements of V, where we denote by: -M t the set of matched nodes at t which are nodes that are fully attached to the graph at t (no available stubs), and belong to the matching at t; -U t the set of unexplored nodes at t, that is, nodes that do not belong to the matching at t, but can still be attached to it (it means they are unmatched but they have available stubs which can yet become edges added to the matching); -I t , the set of isolated nodes at t, that is, nodes that are already fully attached to the graph at t, but do not belong to the matching at t (unmatched and no more stubs to connect them to an eventual match).

By our very construction, all nodes of M t (if any) will have degree at least 1 in G t , and we let U t = {v i 1 , ..., v ip } ⊂ V. (We skip the dependance in t in the parameters v j l , for short.)

A maximum matching G ′ t = (M t , E ′ t ) on the induced subgraph of M t in G t . In particular, E ′
t is a set of subsets of pairs of M t of the form {v i , v j } for v i , v j ∈ M t such that any element of M t appears in exactly one pair of E ′ t .

Two sets of pairs, where all active nodes, nodes that have yet to be visited, are in

A t = v i 1 , a t (v i 1 ) , • • • , v ip , a t (v ip )
and active nodes with stubs available are in

A * t = v i l1 , a t (v i l1 ) , • • • , v i lm , a t (v i lm ) with ∀(v, a t (v)) ∈ A * t , a t (v) > 0. For any l ∈ 1, p , a t (v i l )
is interpreted as the availability of node v i l at t, that is, the number of available stubs.

The next iteration is then triggered :

Step 1. An unexplored node I of positive availability K is selected following

Φ K ({a t (v i l 1 ), • • • , a t (v i lm )}), this defines (I, K) = (v iq , a t (v iq )) ∈ A *
t for some q. The uniform pairing procedure is used to complete the K stubs of I into edges II.2. LOCAL MATCHING ON THE CONFIGURATION MODEL CHAPTER II. LOCAL MATCHING ALGORITHMS more specifically : We draw, without repetition, K elements uniformly at random among l m bunches of elements of respective sizes a t (v i l ), l ∈ 1, l m to construct the emanating edges of node I (recall that l m = |A * t | is the number of nodes with available half edges). Then, we let N t (I) := {I ′ 1 , ..., I ′ u } ⊂ v i l 1 , ..., v i lm , where u ≤ K is the set of the u neighbors of I, i.e., the indexes of the bunches containing the chosen half-edges. Note that this operation may lead to parallel edges or loops whenever several elements of the same bunch of half-edges are chosen. In this case, u < K. However, is a well known fact that baring some restrictions on the initial degree sequence, the number of loops/multiple edges is O(1) (see for example [START_REF] Angel | Limit laws for self-loops and multiple edges in the configuration model[END_REF]) so it does not affect the large graph matching coverage.

For all l ∈ 1, l m , we let D I ′ l be the number of edges shared by I ′ l with I, that is, the number of elements in the bunch I ′ l chosen in the uniform pairing procedure.

v 1 v 2 v 3 v 4 v 5 v 6 (a) greedy v 1 v 2 v 3 v 4 v 5 v 6 (b) minres Figure II.5: Chosing I = v 1 and discovering its neighbors N t (I) := {v 2 , v 3 , v 6 }. We also have that K = 3 and a t (v 2 ) = 2, a t (v 3 ) = 1, a t (v 6 ) = 2.
Step 2. The match of I is chosen within the set

{I ′ 1 , ..., I ′ k }. Call it I ′ = I ′ m , with availability K ′ , where K ′ is drawn following the law Φ K ′ ({a t (I ′ 1 ), ..., a t (I ′ u )}).
Henceforth, both nodes I and I ′ together with the edge {I, I ′ } can be added to the matching G ′ t , that is, we set

M t+1 = M t ∪ {I, I ′ } and E ′ t+1 = E t ∪ {I, I ′ } .
Step 3. Finally, we determine the neighboring edges on the I ′ side.

If K ′ > D I ′ , I ′ still has K ′ -D I ′ uncompleted half-edges. The procedure in
Step 1. is reiterated. We draw at random the indexes I 1 , ..., I ℓ of the neighbors of I ′ other than I using the same uniform pairing procedure. Namely, we draw a t (I ′ ) -D I ′ elements uniformly at random among the l m -1 "bunches" (recall that l m is the number of available bunches) of elements of respective sizes a t (v i l ) -D i l , l ∈ 1, l m \ {q} (that is, all unexplored elements now that I = v iq has been matched), to determine the other neighbors of I ′ .

II.2. LOCAL MATCHING ON THE CONFIGURATION MODEL CHAPTER II. LOCAL MATCHING ALGORITHMS v 1 v 2 v 3 v 4 v 5 v 6 (a) greedy chooses the match ran- domly v 1 v 2 v 3 v 4 v 5
We let {I 1 , ..., I ℓ } ⊂ v i 1 , ..., v i lm \ {i q } (for ℓ ≤ a t (I ′ ) -D I ′ ) be the set of the ℓ neighbors of I, i.e., the indexes of the bunches containing the chosen half-edges. For all l ∈ 1, ℓ , we let F I l be the number of edges shared by I l with I ′ , that is, the number of elements in the bunch I l chosen in the uniform pairing procedure.

If K ′ = D I ′ (which for example the case if u = 1), then I ′ has no more open half-edges to complete. In this case we do not do anything at this stage, and just set ℓ = 0. After all those operations, in the illustrative example for greedy we have that A t+1 = {(v 3 , 0), (v 4 , 3), (v 5 , 1), (v 6 , 1)} and A * t+1 = {(v 4 , 3), (v 5 , 1), (v 6 , 1)}. The other relevant sets are easily deduced as well.

v 1 v 2 v 3 v 4 v 5 v 6 (a) For greedy, I ′ = v 2 has a neigh- bor v 1 v 2 v 3 v 4 v 5
In all cases, the neighboring edges of (I,I ′ ) are now complete, and we can summarize the operations

E t+1 = E t ∪ {I, I ′ 1 }, ..., {I, I ′ k } ∪ {I 1 , I ′ }, ..., {I ℓ , I ′ } ,
where the second set on the right-hand side above is understood as empty if ℓ = 0. We also update the sets of availabilites A t by deleting the pairs corresponding to the newly matched nodes I and I ′ , and by updating the remaining number of stubs of the unmatched nodes connected to the two newly matched ones, if any. In other words, we set for the edges on both sides

               A t+1 = A t ∪ {(I 1 , a t (I 1 ) -F I 1 ) , • • • , (I ℓ , a t (I I l ) -F I ℓ )} \ {(I, a t (I)), (I 1 , a t (I 1 )) , • • • (I ℓ , a t (I ℓ ))} ; A t+1 = A t+1 ∪ {(I ′ 1 , a t (I ′ 1 ) -D 1 ) , • • • (I ′ u , a t (I ′ u ) -D u )} \ {(I ′ , a t (I ′ )), (I ′ 1 , a t (I ′ 1 )) , • • • (I ′ u , a t (I ′ u ))} .
(II.14)

The procedure terminates at most at time n, when U n becomes empty. One last operation is needed to complete the process. All the active nodes become isolated :

I n = I n ∪ A n , .
A n = ∅.

(II.15)

At that time, we end up with a multi-graph G := G n = (V, E n ), since all stubs have been completed. Moreover all the nodes are either matched or isolated.

The matching coverage is reexpressed the same way:

M n Φ ( G) = |M n | n = 1 - |I n | n ∈ [0, 1]. (II.16)

II.3 Simulations

To motivate the remainder of our work we provide some early simulation results. [START_REF] Aoudi | Markovian online matching algorithms on large bipartite random graphs[END_REF]) gives a more detailed account of the technical aspects. We chose to focus on bipartite graphs since it is the most relevant framework for practical uses. We test the II.3. SIMULATIONS CHAPTER II. LOCAL MATCHING ALGORITHMS empirical convergence of the matching coverage under both Greedy and Minres. This section serves also as a prelude for testing the robustness of our method. For the entirety of this section, the work presented is restricted to the bipartite configuration model. Hence, the empirical degree sequence is divided accordingly in {+} and {-} sides, representing the bipartition. We write

d = (d + , d -), (II.17)
where d is the initial degree sequence. The criteria are also lined accordingly: Φ I is restricted to d + .

II.3.1 Convergence of the Matching Size : a case study on 3-regular graphs

In this section, we use 3-regular graphs to test the convergence of M n Φ (G)/n, for G a 3regular graph and the initial degree sequence d + = d -= 3 ⊗n , for n the number of vertices on both sides.

To illustrate the convergence of M n Φ (G)/n, we proceed as follows: for each value of n from 10 to 10 000, we use the bipartite configuration model to draw a 3-regular graph as a realization of the CM. For various graph sizes, we ran N = 50 iterations of the previous procedure.

As Table II.1 hints at the convergence results we later establish in Chapter 3 and 4. The shrinking of the standard deviations confirm the heuristic convergence to a deterministic value. It also stresses on the better performances of Minres with respect to Greedy for this particular degree distribution. In the next part, we develop this comparison for a larger range of degree distributions.

II.3. SIMULATIONS CHAPTER II. LOCAL MATCHING ALGORITHMS

II.3.2 An Array of Degree Distributions

Here, we study the evolution of the performances of the two algorithms Greedy and Minres under varying parameters of the configuration model. We empirically identify the convergence along various degree distributions and various parameters. Our procedure is the following: for each degree distribution, we use still the bipartite CM to generate a large graph (of size n = 10 4 nodes), in which the degrees of the nodes form a n-sample of the prescribed degree distribution, after testing the graphicality of the latter degree distribution (i.e., the feasibility of the generation of the graph). For each distribution, again we ran 50 iterations of both algorithms, following the first construction of Section II. These results illustrate perfectly the growth of the performance of both algorithms as the average degree grows. For each designated distribution, we can also confirm that the matching coverage of Minres is consistently larger than that of Greedy.

Comparing the sub-figures of Figure II.8 with the corresponding sub-figures of Figure II.9 for the same average degree, we make the two following observations: First, both algorithms consistently perform better on regular graphs than on graphs with Poisson degree distributions. Regular graphs can be written as the disjoint union of perfect matchings so their structure might drastically increase the chance of building one. We II.3. SIMULATIONS CHAPTER II. LOCAL MATCHING ALGORITHMS also conjecture that this phenomena is due to the variance of Poisson degrees in the first panel: by restricting choices, the optimal partners for certain nodes (which we are trying to reach) might get blocked, while regular distributions provide more latitude to chose a match without missing an optimal one4 . Second, for both algorithms, the distribution of matching coverages has higher variance on regular graphs than on graphs having Poisson degrees. It seems that a uniform initial degree distribution provides more opportunities to deflect from typical runs, while the variance of degrees often restricts the choices, creating a disparity between nodes.

II.3.3 The Influence of Topology and Another Approach

To Online Bipartite Matching: Optimal Algorithm by Karp, Vazirani and Vazirani In [START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF], Karp, Vazirani and Vazirani present a different approach for online bipartite matchings on graphs. The authors define online algorithms as a way of picking the matches of "girls" (i.e., nodes on the '+' side) that arrive one by one, based only on the identity of their neighbors on the 'boys' side (i.e., the '-' side). On the adjacency matrix of the graph, it translates to the fact that the columns are revealed one by one and the match is processed upon knowing the information of the current column. Our approach based on local algorithms has slight differences and actually uses more information. Indeed, we also consider the degree of each neighbor, of the incoming 'girl', and the neighbors of its match, of her 'boy' neighbor.

Second, the performance metric considered in [START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF] is the so-called adversary approach. It allows to get a lower bound on the performance of online algorithms, as defined above. Namely, Theorem 2 in [START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF] states that in that context, the matching coverage is at least 1 -1/e -o(n)/n on average. This average happens to be the expected matching coverage attained by the Random algorithm defined therein (which is roughly equivalent to our Greedy). In our paper, a different metric is used: we establish convergence to a deterministic value of the average matching ratio, rather than a lower bound. Therefore, it is clear that our framework differs from that of [START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF]. However, to gain some insights on how much our algorithms based on the degree distribution stand up against their counterparts on real graphs, we conducted the following study: we let G be a randomly generated graph with 5000 nodes, from an upper triangular adjacency matrix that is specified as follows: all diagonal elements are 1, thereby insuring the II.3. SIMULATIONS CHAPTER II. LOCAL MATCHING ALGORITHMS existence of a perfect matching, and all upper elements are Bernoulli(p) random variables, where p is so that the graph has average degree, say, 5. Such graphs provide the worst case scenarios for the framework in [START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF]. Then, the exploration algorithms are run on G (Section II. .10 shows that matching algorithms that are jointly constructed with the CM achieve a better matching coverage than on this given realization. In other words, matching algorithms typically perform badly on this particular graph, with respect to a graph that is obtained as a uniform draw amongst graphs having the same degree distribution, unsurprisingly hinting at the influence of the graph topology on the considered matching algorithms. Simulations seem to indicate that this influence is more so enhanced in Greedy. Finally, we also observe that Minres produces a better matching coverage than Greedy anyway.

Notes II.3.1 (Choice of the Configuration Model). In the introduction, we mentioned that random graphs were analogous to statistical models for complex networks. And statistical models are picked accordingly to the populations under study. Hence, the choice of the underlying random graph model should also depend on the network at hand. This means our approach has more legitimacy on networks that are well described by the CM.

We chose the CM mostly because of its local description of the neighborhood of nodes which ends up being convenient for building local algorithms. Our algorithms could be transposed to other asymptotic graph models with local descriptors, although it would perhaps require a different set of mathematical tools to study their performances.

Another observation to be made is that the matching problem we are studying is defined on simple graphs. This restricts the use cases for our model. For the CM to produce and asymptotically be 'close' to a simple graph, it is a well known fact that some moments restrictions have to be imposed on the degree distribution van der Hofstad [2016] which we will explore later. This is the reason why most of the distributionx we picked for simulations admit at least moments of order 4.

II.3.4 Notes

In the next chapters, we will develop the procedure used to approximate and predict the matching coverage of local matching algorithms on graphs. Representing the matching algorithms as a dynamic on the degree distribution will allow us to predict the results of the considered algorithms with remarkable accuracy. In particular, the next chapter will delve into such representation. Notice that this results in a dramatic reduction of the problem complexity: as long as one is interested in the matching coverage of the algorithm under consideration, one only needs to keep track of the unexplored part of the graph.

As our simulations indicate, two natural and interesting problems already arise from this chapter: The first (and probably the harder) one is to quantify the influence of the graph topology on the average matching coverage for a given algorithm. How much does the structure of the network influence the performance of algorithms?

The second concerns the potential optimality of Minres as a criterion. Among all the criteria we addressed, Minres always seemed to give the better matching coverages in average. An interested follow up to this work could be the establishment of a (stochastic?) order on all the matching criteria.

Chapter III Local Matching Algorithms as Markov processes

Chapter II described the algorithms we consider as local. Chapter III extends the representation of the latter algorithms as operations on empirical measures. Each iteration is written as a sequence of calculations on the current degree distribution of the graph. Random dynamics on spaces of measures are an immensely prominent wing in the study of stochastic processes. Being the prime representation for point processes, their uses range from the study of population processes in biology [START_REF] Fournier | A microscopic probabilistic description of a locally regulated population and macroscopic approximations[END_REF]; [START_REF] Champagnat | From individual stochastic processes to macroscopic models in adaptive evolution[END_REF]) to statistical physics and interacting particle systems [START_REF] Liggett | Interacting Particle Systems. Grundlehren der mathematischen Wissenschaften[END_REF]). Likewise, a series of important results comes from the queuing literature, noticeably with the concept of fluid limits and its applications to several related problems [START_REF] Gromoll | The fluid limit of a heavily loaded processor sharing queue[END_REF]; Decreusefond and Moyal [2008b,a]). We intend to follow the works of [START_REF] Bermolen | The jamming constant of uniform random graphs[END_REF] and use the vast variety of tools for measure spaces on the particular study of local algorithms as we previously defined them.

Chapter III is comprised of two sections. The first section is an examination of matching algorithms as measure valued processes. The intent is to find a representation of the local algorithms as defined in the last chapter. It is as much an alternative representation as it is a simplification. We can then rewrite the matching coverage as a continuous function of the process describing the algorithm and we can proceed to the study of its properties. The section starts by proving a theorem that bridges the first two sections of chapter II as hinted by the simulations. An equivalence of sorts is established between the behavior of criteria on the finite given graphs and their behavior on the configuration model. The tendencies a given criteria exhibits on defined graphs stays the same when extended to the configuration model. The second section then concludes the chapter with the establishment of a proper scaling of the measure valued representation. It can be seen as a normalization, used to study and predict the behavior of matching criteria based III.1. NOTATIONS AND HYPOTHESES CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES algorithms when the graphs get arbitrarily large. In the section, we mostly define the normalized version of the measure valued processes in prevision of the next chapter, where we prove its convergence to a deterministic function.

III.1 Notations and Hypotheses

For the rest of this work, the superscript n will be used to represent the size of the empirical distributions/measures. As the number of vertices, it will also be the scaling parameter of our study. Recall that, M F (N) is the space of finite valued measures on N. We shorten it to M F . Likewise, we define M n F as the subset of M F whose elements are counting measures with total mass ≤ n. M n is then the space or normalised space associated to M n F . We write

M n := 1 n M n F = { 1 n µ |µ ∈ M n F }.
Finally, M is the space of N valued measures with total mass ≤ 1. Usually, those measure spaces are endowed with their weak topology (resp. vague topology): Moreover, we reintroduce some functions and notations of interest :

µ n M F --→ µ ⇐⇒ ⟨µ n , f ⟩ := f dµ n - → f dµ := ⟨µ, f ⟩ (III.
χ(x) = x the identity function ∇f (x) = f (x) -f (x -1) the discrete gradient
For two real valued functions f and g, we say that

f (n) = o(g(n)) if lim n→∞ f (n) g(n) = 0. Likewise f (n) = O(g(n)) if lim sup n→∞ | f (n) g(n) | < C for some positive constant C.
Finally, unless the criterion is specified µ n t , n ∈ N, t ≥ 0 designates the process affiliated with a generic matching criterion Φ.

III.1.1 Main Hypotheses

Let {μ n ; n ∈ N * } be a sequence of D[(0, T ), M F (N)] valued processes, let ν in M F , ⟨ν, χ p ⟩ < ∞ and p ≤ 3. We say that {μ n ; n ∈ N * } satisfies H0 if, for some ν ∈ M the following conditions on the initial states hold :

III.1. NOTATIONS AND HYPOTHESES CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

Hypothese H0

1. Weak convergence of the initial degree distributions:

⟨μ n 0 , f ⟩ n - → ⟨ν, f ⟩ < ∞, f ∈ C b (N) (III.2)
2. Convergence of the first three initial moments:

⟨μ n 0 , χ p ⟩ n - → ⟨ν, χ p ⟩ < ∞ (III.3) for 1 ≤ p ≤ 3.
As we will later see, these conditions guarantee a bound on the moments of the empirical degree distribution throughout all the dynamic. However, their interest is not limited to the technical aspect. The average number of second neighbors1 of a typical node in the configuration model CM (ν) is shown to be [START_REF] Newman | Networks[END_REF]; van der Hofstad [2016]; [START_REF] Angel | Limit laws for self-loops and multiple edges in the configuration model[END_REF]) ⟨ν, χ 2 ⟩ -⟨ν, χ⟩ and each one of those second neighbors have a degree that again follows the size-biased degree distribution. H0 warrants that this number of neighbors is (almost surely) finite, thus one can define a dynamic depending on second neighbors of a given node. And since second neighbors characterize the neighboring edges of any given edge, this allows us to transpose the construction of local algorithms asymptotically to the configuration model. Moreover, it is a way to ensure that loops and parallel edges do not disturb our construction since their number becomes O(1) [START_REF] Angel | Limit laws for self-loops and multiple edges in the configuration model[END_REF]) meaning their influence on the proportion of matched nodes vanishes as n goes to infinity.

Notice that H0 is an hypothesis on the initial degree distribution and it does not impact the dynamic yet. It does however affect the properties of the CM.

Notes III.1.1. Those restrictions on the moments of the degree distribution are standard for the configuration model. The whole premise of our work rests on the fact that realizations of our models are close to that of simple graphs (in the sense that multiple edges are asymptotically negligible). On the configuration model, this is guaranteed by a second moment on the normalized degree sequence [START_REF] Janson | The probability that a random multigraph is simple[END_REF]. As will be seen later, this is also the reason why we have a crucial o( √ n) estimate for the degree of the first node selected I. Now I ′ is chosen amongst the neighbors of I who all follow a distribution that is very close to a size biased version of the initial degree distribution. But, for the size biased version of a measure to admit a variance, the original version needs to have at least 3

III.2. DISCRETE TIME MARKOV CHAIN CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

moments, justifying our hypothesis. A finite variance on our dynamic will prove to be essential in establishing most of the useful properties in the present chapter and even later (tightness, maximum degree control and cancellation of the martingale part for example).

In fact, the moment requirement will have to be increased to 3.5 to prove the main theorem for greedy.

III.2 Discrete time Markov chain

We can properly instigate the study of the process induced by the matching dynamic on degree sequences. Unless stated otherwise, in this section the graph size is considered constant and the iteration count is the variable.

III.2.1 Measure valued representation and Markov Chain dynamic

Let µ n 0 : i δ d(i) := i δ a 0 (v i )
be an initial degree sequence and µ n k , k ∈ 0, n be the measure that tracks the availability of nodes over the course of a matching algorithm as set in chapter II (II.2). Going forward, the performance of the algorithms is tracked using measures. Specifically, let Φ be a matching criterion. First, we will initiate a comparison between the local algorithms on defined graphs to their extension when the structural layer of randomness is added by the configuration model. For all 0 ≤ k ≤ n:

We let μk be the empirical degree distribution of all unexplored nodes at k in the remaining graph Gk associated to the construction in Section II.1, that is

μk = v∈ Ůk δ d k (v) , (III.4)
where d k (v) is the degree of of v in Gk . Recall that the˚notation designates given deterministic graphs.

Likewise µ k will be the analogous empirical distribution representing the availabilities of all unexplored nodes at k when the configuration model is used (Section II.2):

µ k = v∈U k δ a k (v) .
(III.5)

The following theorem links the two constructions. It is a formalization of the fact that conditioning by a given structure first before applying the algorithms does not influence

III.2. DISCRETE TIME MARKOV CHAIN CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

the final law of the dynamic. The matching criteria behave "as expected" when ran on the CM.

Theorem III.2.1. Let n be a positive integer, G is a graph of size n, and let d its degree sequence. Let μt be the measure-valued stochastic process defined by (III.4) with initial value

μ0 = n i=1 δ d(i) .
Let G be the resulting multigraph of the second construction. Then for any t ∈ 0, n and any measure ν ∈ M n F (N). M n F (N) is the space of finite point measures such that ν(i) ∈ N, i≤n ν(i) ≤ n and ν(i) = 0 if i ≥ n. We get that

P µ t = ν | G = G = P [μ t = ν] .
Proof. Suppose that G = G, that is, the final result of the second construction produces the graph G. We index the nodes of V consistently in the two constructions.Take μ0 = µ 0 , the result is obtained by induction on t.

Suppose that, at some time t ∈ 0, n -1 we have Gt = U t and a t (v) = d t (v) for all v in Ůt = U t .

(III.6)

We exhibit a coupling such that (III.6) holds also at time t + 1, so that the empirical measures stay the same. Notice first that as Gt = G t , at Step 1 and 1 respectively, we can set a common realization of the draw on 1, |U t | , leading to the same values for I and I.

As described in the first chapter, the reader is reminded that D I l is the number of edges going from I ′ to I l , and that F I ′ j is likewise the number of edges going from I to I ′ j . Since a t (I) > 0, at step 1), as we have to produce the same graph, the uniform pairing procedure leads to the same set of neighbors for I as in G, namely

I ′ 1 = I′ 1 , ..., I ′ u = I′ u
because the same indexes can be picked in the two constructions. Then, as d t ( I) = a t (I) > 0, at steps 2) and 2) again we can align the draws so that I′ = I ′ in Ůt = U t , using the matching criterion Φ. Finally, as G = G the uniform pairing procedure leads again to the same set of neighbors for I ′ too as in G, namely I 1 = I1 , ..., I ℓ = Iℓ , again using the fact that we can use the same indexing. We then follow up with

Ůt+1 = Ůt \ { I, I′ } = U t \ {I, I ′ } = U t+1 .
G does not have multiple edges, so u = d t ( I) = K and ℓ = d t ( I′ ) = K ′ . Moreover, for MARKOV CHAIN CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES any l ∈ 1, k \ {m}, at step 1a) we obtain that

a t+1 (I ′ l ) = a t (I ′ l ) -D I l = a t (I ′ l ) -1 = d t (I ′ l ) -1 = a t+1 (I ′ l ),
And applying the same argument to the neighbors of

I ′ , l ∈ 1, ℓ \ {σ(m)}, a t+1 (I l ) = a t (I l ) -F I l = a t (I l ) -1 = d t (I l ) -1 = a t+1 (I l ).
Last, for any v ∈ U t+1 \ {I 1 , ..., I ℓ , I ′ 1 , ..., I ′ k } we get that

a t+1 (v) = a t (v) = d t (v) = d t+1 (v).
In all cases, expression (III.6) holds at step t + 1.

Thus, we can conclude that (III.6) holds in fact for all t ∈ 0, n . (III.4) and (III.5) imply in particular that μt = µ t for all t ∈ 0, n , concluding the proof. ■

This theorem establishes that whenever the configuration model produces a given graph, the local criterion based matching algorithm simply behaves like an exploration algorithm on the given graph (as given is the first section of chapter II).

We can finally tend to the study of the dynamic induced on the degree distribution.

Proposition III.2.1. Fix n ∈ N, n > 0, the matching algorithms on the CM induce a M n F valued Markov chain, (µ n k ) k≥0 with transition kernel

L n F (µ) := E µ F (µ + ϑ(µ)) -F (µ) , (III.7) for µ ∈ M n F and F a continuous bounded function M n F → R. ϑ(µ n k ) is defined as ϑ(µ n k ) = -   δ K + δ K ′ + I ′ l ∈N (I) δ a k (I ′ l ) -δ a k (I ′ l )-D I ′ l + I l ∈N (I ′ ) δ a k (I l ) -δ a k (I l )-F I l   .
(III.8)

In particular, for Π f (µ) = ⟨µ, f ⟩ , f ∈ C b (N), equation (III.7) is expressed as L n Π f (µ n k ) = E µ n k ⟨ϑ(µ n k ), f ⟩ . (III.9)
Moreover, the associated matching coverage can be rewritten as

M n Φ (µ n 0 ) = 1 - I n n n = 1 - µ n n ({0}) n • (III.10) MARKOV CHAIN

CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

All the quantities used in the definition of ϑ depend on the current state of the measure. We do not write the dependance to simplify notations.

Remark III.2.1. From this point forward, all the results are enunciated only on the cylindrical functions Π f (µ) := ⟨µ, f ⟩ [START_REF] Dawson | Measure-valued markov processes[END_REF]) for f : R → R, in our case in particular f would mostly be continuous and bounded. Theorem 3.2.6 shows that to characterize the convergence in law of measure valued process, it is enough to display the convergence over such functions. They are convergence determining.

Proof. Proposition III.2.1 First, we bring back equation (II.14) for iteration number k ≤ n :

               A k+1 = A k ∪ {(I 1 , a k (I 1 ) -F I 1 ) , • • • , (I ℓ , a k (I I l ) -F I ℓ )} \ {(I, a k (I)), (I 1 , a k (I 1 )) , • • • (I ℓ , a k (I ℓ ))} ; A k+1 = A k+1 ∪ {(I ′ 1 , a k (I ′ 1 ) -D 1 ) , • • • (I ′ u , a k (I ′ u ) -D u )} \ {(I ′ , a k (I ′ )), (I ′ 1 , a k (I ′ 1 )) , • • • (I ′ u , a k (I ′ u ))} .
Now for k ≥ 0, we recall that µ k represent the availabilities at iteration k. We can inspect the variations of the availabilities using the operations in equation (II.14). The couples associated to the matched nodes I and I ′ (or to their degrees K and K ′ ) are subtracted from the availability set while all the other couples involved only have theirs updated. Equation (III.8) is only a matter of writing the empirical measures associated to µ k and µ k+1 .

ϑ(µ k ) = -   δ K + δ K ′ + I ′ l ∈N (I) δ a k (I ′ l ) -δ a k (I ′ l )-D I ′ l + I l ∈N (I ′ ) δ a k (I l ) -δ a k (I l )-F I l   .
(III.11)

If we establish that ϑ(µ n k ) is independent of (µ n s ) s≤k-1 , it is immediate to write its kernel as :

L n F (µ) = E F (µ n k+1 ) -F (µ n k ) | µ n k = µ (III.12)
But given the matching criterion Φ, Φ(µ) can be chosen to be independent of the process (µ n k ) k≥0 when µ is deterministic, so that the randomness in the choices is independent from that of the process. For example, the independence is achieved if (Ω 1 , F 1 ) is chosen as a sub sigma algebra of (Ω, F) so that Φ(µ) is F 1 measurable and that F 1 is independent from σ(µ n k,k≥0 ). When such a sigma field does not exist, one can for example extend

III.2. DISCRETE TIME MARKOV CHAIN CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

(Ω, F) into (Ω ∪ Ω 1 , σ(F, F 1 )). This ensures that Φ(µ n k ) only depends on µ n k . Moreover, it is immediate that the next steps of the uniform pairing procedure depend only on the current availabilities. Hence, all the operations that define ϑ depend only on the current state of the process, showing that (µ n k ) k≥0 is a Markov chain. At last, we can revisit the definition of ϑ to obtain the matching coverage as in (III.10) . Ending every iteration, the points associated to the degrees of matched nodes are removed from the measure (those are δ K and δ K ′ ) while their neighbors lose mass. Only matched nodes are removed from the availability set so that at time n, when all the edges are created, the only remaining points in the measure are those affiliated with isolated nodes with no availability (recall that A n consists of all the non matched nodes whose availability is now 0). Thus, equation (III.10) is a direct consequence of equation(II.15). ■

Characterizing the matching dynamic as a Markov chain will later allow us to use scaling and the powerful theory of Markov processes. The rest of this document will be dedicated to the examination of the large scale behavior of dynamics [START_REF] Wormald | The differential equation method for random graph processes and greedy algorithms[END_REF]; [START_REF] Kurtz | Solutions of ordinary differential equations as limits of pure jump markov processes[END_REF]) and their concentration around a deterministic function serving as a prediction of their performance. Given a criteria, we will often be able to compute said function, predicting the matching coverage. The convergence will be fully established in chapter IV. For now, the next sections are devoted to tailoring the given Markov chain into a scalable process and to establishing its useful properties.

III.2.2 Moment estimates and properties

For any n, the sequence of measures (µ n k ) k≥0 loses mass (half edges). We formulate this fact in the next proposition: Proposition III.2.2. Let f : N → R be a positive and increasing function, and k ≥ 0.

Then,

⟨µ n k , f ⟩ ≥ µ n k+1 , f . (III.13) Specifically, for all p > 1, if ⟨µ n 0 , χ p ⟩ < ∞ then ⟨µ n k , χ p ⟩ < ∞ for all k.
Proof. For all such k and f , notice that

µ n k+1 , f -⟨µ n k , f ⟩ = ⟨ϑ(µ n k ), f ⟩ , (III.14) MARKOV CHAIN CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES making it so that (III.13) is directly implied by ⟨ϑ(µ n k ), f ⟩ < 0. But ⟨ϑ(µ n k ), f ⟩ = -   f (K) + f (K ′ ) + I ′ l ∈N (I) f (a k (I ′ l )) -f a k (I ′ l ) -D I ′ l + I l ∈N (I ′ ) f (a k (I l )) -f (a k (I l ) -F I l )   .
Both f (K) and f (K ′ ) are positive because f is so. And for any l, f (a proving (III.13). Then, applying (III.13) k times yields

k (I ′ l )) -f (a k (I ′ l ) - D I ′ l ) and f (a k (I l )) -f (a k (I l ) -F I l ) are positive because f is increasing. Hence µ n k+1 , f -⟨µ n k , f ⟩ = ⟨ϑ(µ n k ), f ⟩ < 0,
∞ > ⟨µ n 0 , f ⟩ ≥ ⟨µ n k , f ⟩ , (III.15)
concluding the proof. ■

The preceding result actually yields an universal bound over the moments of the trajectories under H0. Almost all of the results in the next chapter rest on this universal bound.

Corollary III.2.1 (Universal bound). Suppose that the sequence of Markov chains ( 1 n µ n . ) n≥1 satisfies H0. Then,

sup n,k 1 n ⟨µ n k , χ p ⟩ ≤ M < ∞ (III.16)
for some M > 0.

Proof. For any k, n, (III.13) brings forth

1 n ⟨µ n k , χ p ⟩ ≤ 1 n ⟨µ n 0 , χ p ⟩. But since 1 n µ n 0 satisfies H0, 1
n ⟨µ n 0 , χ p ⟩ is convergent and therefore bounded by some finite M . We write

1 n ⟨µ n k , χ p ⟩ ≤ 1 n µ 0 k , χ p ≤ M, (III.17)
which concludes the proof. ■

We conclude this section by providing yet another estimate. We assess the scale of the typical degrees in the local matching dynamic. This result of capital importance will be useful all around for bounds on the amplitude of matching criteria2 . We start with a general preliminary result,

; n ∈ N * } = 1≤i≤n δ d(i) ; n ∈ N * . Suppose that for all f ∈ C b (N) ∪ {χ 2 }, lim n→∞ i f (d n (i)) n = lim n→∞ ⟨µ n , f ⟩ n = ⟨ν, f ⟩ < ∞ (III.18)
for some ν in M F , and define the maximal degree

d n max = max i d n (i).
Then we have that

lim n→∞ d n max √ n = 0. (III.19) Proof. Take ϵ > 0. Since ⟨ν, χ 2 ⟩ < ∞, we gather the existence of M such that ν, χ 2 -ν, χ 2 1 0, √ M < ϵ. But as χ 2 1 0, √ M ∈ C b (N) we also have that lim n→∞ µ n , χ 2 1 0, √ M n = ν, χ 2 1 0, √ M . Thus, lim n→∞ µ n , χ 2 1 √ M +1,∞) n = lim n→∞ ⟨µ n , χ 2 ⟩ n -µ n , χ 2 1 0, √ M = ν, χ 2 -ν, χ 2 1 0, √ M < ϵ. (III.20)
Now, assuming that there exists n such that k be the degree choices under a generic choice criterion Φ. Then the following relation holds

(d n max ) 2 n ≥ ϵ ∨ M/n would imply that µ n , χ 2 1 √ M +1,∞) n ≥ ϵ,
lim n→∞ K µ n k √ n = lim n→∞ K ′ µ n k √ n = 0. (III.21)
Proof. The result is proven in two steps. First, we prove that for

k ∈ 0, n , it is clear that if M n k = max i a n k (v i ) then M n k is decreasing in k.
The procedure is essentially the same as in the proof of (III.13). By definition, ∀l > M n k , µ k (l) > 0. As a consequence,

µ n k+1 (M n k ) -µ n k (M n k ) = ϑ(µ n k ), 1 M n k = -   1 M n k (K) + 1 M n k (K ′ ) + I ′ l ∈N (I) 1 M n k (a k (I ′ l )) -1 M n k (a k (I ′ l ) -D I ′ l ) + I l ∈N (I ′ ) 1 M n k (a k (I l )) -1 M n k (a k (I l ) -F I l )   . (III.22) But, 1 M n k (a k (I ′ l )-D I ′ l ) = 1 would mean that a k (I ′ l ) > M n k , which is impossible by definition of M n k . Therefore, for all l, 1 M n k (a k (I ′ l ) -D I ′ l ) = 0 and likewise, 1 M n k (a k (I l ) -F I l ) = 0. Ultimately, ϑ(µ n k ), 1 M n k ≤ 0 and µ n k (M n k ) is decreasing in k. But under H0, 1 n µ n 0 satisfies the conditions of Lemma III.2.1 because lim n→∞ 1 n µ n 0 , χ 2 = ν, χ 2
and lim n→∞

1 n µ n 0 , f = ⟨ν, f ⟩ for f ∈ C b . It means that d n max (µ n 0 ) = M n 0 is o( √ n).
The assertion is proved by noticing that for all k,

K µ n k ≤ M n k ≤ M n 0 . (III.23) Proving the estimate for K ′ µ n
k is more subtle. The neighbors of a vertex do not have µ n k as their degree distribution. Since they are discovered following an edge, they follow a size biaised version of

µ n k -δ K µ n k : ( µ n k -δ K µ n k , f := µ n k -δ K µ n k , χf µ n k -δ K µ n k , χ
, (III.24)

III.3. NORMALIZATION AND SCALING CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

in other words the chances that some half-edge is linked to a node is proportional to the nodes' number of stubs. After replacing ⟨µ n k , f ⟩ by (

µ n k -δ K µ n k
, f , the proof is the same.

Only, we do have to show that if 1 n µ n 0 satisfies H0, 1 n ( (

µ n k -δ K µ n k
) still verifies the conditions of Lemma III.2.1. And it does, since for all bounded f , lim n→∞ (

µ n k -δ K µ n k , f n = lim n→∞ µ n 0 -δ K µ n 0 , χf µ n 0 -δ K µ n 0 , χ = lim n→∞ μn k -δ K µ n k , f n = ⟨ν, χf ⟩ ⟨ν, χ⟩
by dominated convergence, and again

lim n→∞ ⟨μ n k , χ 2 ⟩ n = lim n→∞ ⟨µ n 0 , χ 3 ⟩ ⟨µ n 0 , χ⟩ = ⟨ν, χ 3 ⟩ ⟨ν, χ⟩ • ■ Remark III.2.2.
For the final part of this proof, we used the fact that the neighbors asymptotically follow a size-biased version of µ n k . Otherwise, using exact laws causes small deviations from the perfect size biased version of µ n k (for example, in the case of the proof, a term in δ K µ n k appeared). This deviation makes the exact generator of the matching algorithms inconvenient to use. Thankfully, we will see in the next chapter that the deviation term vanishes when n gets large and that we can approximate the exact generator by that of a much simpler dynamic.

Notes III.2.1. It is seen here that the existence of at least a third moment guarantees a convenient order for the law of the maximum degree, further justifying our hypothesis.

III.3 Normalization and scaling

Finally, we aim to provide a suitable normalization for the Markov chain dynamic. In fact, the scaled process provided here will be the real object of our study. Later, it is used to study the asymptotic properties of the criteria.

III.3.1 Normalization

Fix n ∈ N * . Towards that purpose, we recall

M n := 1 n M n F ,
where M n F is the space of point measures with integer masses and with total mass smaller than n.

III.3. NORMALIZATION AND SCALING CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

The bar ¯notation is used to signal normalized objects.

Naturally, the process µ n can be extended to a rescaled right-continuous with lefthand limits (RCLL) semimartingale. As is often the case, the limiting behavior of the normalized process will be a continuous process [START_REF] Kurtz | Limit theorems for sequences of jump markov processes approximating ordinary differential processes[END_REF]). This is why we extend the Markov chain into a process on D([0, 1], M F ), giving us access to the Skorokhod topology [START_REF] Méléard | Sur les convergences étroite ou vague de processus à valeurs mesures[END_REF]; [START_REF] Joffe | Weak convergence of sequences of semimartingales with applications to multitype branching processes[END_REF]) for that space. For 0 ≤ t ≤ 1 we denote

μn t = 1 n µ n ⌊nt⌋ ,
where ⌊x⌋ = e ∈ N, e ≤ x < e + 1. We then accelerate time allowing the matching coverage to conveniently become

M n Φ (µ n 0 ) = 1 -μn 1 ({0})• (III.25)
This goes to show that the rescaled process converges directly in tune with the matching coverage. One immediate downside is that μn is no more a Markov process on D([0, 1], M F ). After all, its jump times are deterministic. Moreover, we still have no guarantee on the behavior of the criteria through normalization.

Since choice functions are defined on (∪ n≥1 M n F ), they can naturally be extended to functions on normalized degree sequences: (∪ n≥1 M n ). Again for a normalized degree sequence μn ∈ M n , we will use the superscript¯and we designate the choice functions on normalized sequences as:

Φ(μ n ) = Φ(nμ n )• (III.26)
On one hand, since the space (∪ n≥1 M n ) is dense in M (recall that M is the subpace of M F with total masses ≤ 1)3 , a natural assumption to make about choice functions would be that, if μn → μ for some adequate topology stronger than the weak topology, then it should also be true that Φ(μ n ) → Φ(μ) .

On the other hand however, even though some criteria are well defined on M n for every n, sometimes they can not trivially be extended to the whole space M. As an example, take μ to be a measure with unbounded support, the truncations of μ on M n would admit a maximal degree while max(μ) is obviously not defined. As a consequence, we have to impose some further restrictions (that would be either on the criteria under consideration or on the domains considered).

III.3. NORMALIZATION AND SCALING CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

Definition III.3.1.

1. A criterion is (asymptotically) well behaved on a (closed) subspace M Φ of M, when for all n ≥ 1, μn ∈ M n and μ ∈ M Φ such that μn → μ, we have Φ(μ n ) → Φ(μ) for a topology that is stronger than the weak topology.

2. A criterion preserves the moments of order up to p ≥ 1 if, for all μ ∈ M Φ and v < p, ⟨μ,

χ v ⟩ < ∞ implies Φ(μ), χ v < ∞
The order of the moment preservation is the important part. For example, if the base measure µ has moments up to an order p + 1, the uniform choice on its size biased version only preserves the moments up to p. This means the properties we can prove on our algorithms should also be true only up to order p. Moreover, take µ as any measure with exponential moments, technically Φ(µ) could be any probability law, especially one admitting no moments of higher order thus failing to preserve all the moments of the initial distribution. Φ(μ n ), χ p < M (III.27)

Proof. Since Φ preserves moments, this is a direct consequence of III.16. ■

III.3.2 Continuous time Markov chain

We finally undertake the restoration of the Markov property for the normalized continuous processes. To extend the discrete time Markov chain into a continuous one, assume θ 1 , θ 2 , ... is a sequence of independent identically distributed exponential random variables with parameter 1. Moreover, assume that (θ i ) i>0 is independent from μn t . Define the following sequence of random times

τ 0 = 0, τ i+1 = τ i + θ i /n.

The associated continuous time Markov chain to μn

. is the following process :

t -→ μn t := μn l/n
for τ l ≤ t < τ l+1 , l ∈ N.

(III.28)

III.3. NORMALIZATION AND SCALING CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

From now on, the tilde ˜superscript is used for the objects related to the continuous Markov extension.

Proposition III.3.2. For all n ∈ N * , μn

. is a continuous time Markov extension in the sense that 1. μn is a Feller Markov process with generator Ln :

Ln F (μ) := nE μ F μ + 1 n ϑ(nμ) -F (µ) ,
for μ in Mn , in particular,

Ln Π f (μ) := E μ ⟨ϑ(nμ), f ⟩ . 2. For f ∈ C b , E μn 0 ⟨μ n t , f ⟩ -E μn 0 ⟨μ n t , f ⟩ ≤ ∥L n Π f ∥|1/n + (t/n) 1/2 |.
Proof. Fix n ∈ N * . Since μn t is a pure jump markov process with bounded intensities, it is Feller continuous (see Theorem 12.18 of [START_REF] Kallenberg | Poisson and Pure Jump-Type Markov Processes[END_REF], or [START_REF] Ethier | Generators and Markov Processes[END_REF] p. 163). Thus it admits a strongly defined generator: For all F ∈ C b (M n ) and h > 0,

E μn 0 (F (μ n h ) -F (μ n 0 )) =P(τ 1 > h) × 0 + P(τ 1 < h, τ 2 > h)E μn 0 (F (μ n τ 1 ) -F (μ n 0 ) | τ 1 < h, τ 2 > h) + P(τ 1 < h, τ 2 < h)E μn 0 (F (μ n h ) -F (μ n 0 ) | τ 1 < h, τ 2 < h) Notice that P(τ 1 < h, τ 2 > h) = P(θ 1 /n < h, θ 1 /n + θ 2 /n > h) = (hn + o(nh)) and P(τ 1 < h, τ 2 < h) = (o(nh))
because θ 1 and θ 2 are independent exponential r.v.'s. We then write

E μn 0 (F (μ n h ) -F (μ n 0 )) = nhE μn 0 (F (μ n τ 1 ) -F (μ n 0 ) | τ 1 < h, τ 2 > h) + o(nh) = nhE μn 0 (F (μ n 0 + (1/n)ϑ(nμ n 0 )) -F (μ n 0 )) + o(nh), proving that lim h→0 1 h E μn 0 (F (μ n h ) -F (μ n 0 )) = Ln F (μ n 0 ). SCALING

CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

As for the second assertion, we first introduce

γ t := ⌊nt⌋-1 i=0 θ i+1 /n. (III.29)
By definition, for all t we have that μn t = μn γt . Assertion 1 showed that μn is Markov, whence the expression

E μn 0 ⟨μ n t , f ⟩ = E μn 0 ⟨μ n 0 , f ⟩ + t 0 L n ⟨μ n s , f ⟩ ds , (III.30)
Plus, because γ t is a stopping time

E μn 0 ⟨μ n t , f ⟩ = E μn 0 ⟨μ n 0 , f ⟩ + γt 0 L n ⟨μ n s , f ⟩ ds (III.31)
Which we follow up with

|E μn 0 ⟨μ n t , f ⟩ -E μn 0 ⟨μ n t , f ⟩ | = E μn 0 t γt L n ⟨μ n s , f ⟩ ≤ sup s |L n ⟨μ n s , f ⟩ |E μn 0 |γ t -t| (III.32) But E μn 0 |γ t -t| = E μn 0 γ t - ⌊nt⌋ + nt -⌊nt⌋ n ≤ 1/n + E μn 0 ⌊nt⌋-1 i=0 θ i+1 -1 n ≤ 1/n +   ⌊nt⌋-1 i=0 1 n 2   1/2 ≤ 1/n + (t/n) 1/2 (III.33)
where we used the fact that Eθ 2 i = 2. ■

As for now, this means the convergence of μn . can be estimated by that of a measure valued Markov process. The last key component for outlining the convergence is exhibiting the characteristic martingale. We tend to its study in the final part of chapter III.

III.3.3 Semi-martingale representation

We have just proven that for all n, μn . is a Feller process having generator Ln . For any f and n ≥ 1, the martingale problem for μn

. yields that:

III.3. NORMALIZATION AND SCALING CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES

Proposition III.3.3. The process defined for all t ∈ [0, 1] and f ∈ C b by

M f,n t = ⟨μ n t , f ⟩ -⟨μ n 0 , f ⟩ - t 0 Ln Π f (μ)ds (III.34)
is a square integrable martingale. Moreover, its predictable quadratic variation is equal to :

⟪M f,n ⟫ t = 1 n t 0 E μn s ⟨ϑ(μ n s ), f ⟩ 2 ds. (III.35)
For a R valued semi-martingale X . , we designate by [X] . its quadratic variation.

Thus, if 0 = t 0 < t 1 < ... ≤ t k = t (k ∈ N) is a subdivision of the time interval, [X]
. is defineed by the following expression when it exist:

[X] t = lim max t i -t i-1 →0, 1≤i≤k 1≤j≤k X t j -X t j-1 2 ,
where the limit is taken in probability. We also designate by ≪ X ≫ . the predictable quadratic variation of X . , the unique predictable compensator of [X] . . Proof. It is a characteristic property of Markov processes that M f,n t is martingale (e.g 5.1.2 in [START_REF] Dawson | Measure-valued markov processes[END_REF], or the chapter 4 of [START_REF] Ethier | Generators and Markov Processes[END_REF]). We simply need to compute the quadratic variation.

The book of Decreusefond and Moyal [2012] gives an explicit form for the quadratic variation of measure valued pure jump processes in its Theorem 7.15. Here we adapt the proof to the particular case of the matching process previously defined. Fix t ≥ 0 and recall that if

Π 2 f (μ n t ) = ⟨μ n t , f ⟩ 2 , L n Π 2 f (μ n t ) = nE μn t Π 2 f (μ n t + 1 n ϑ(nμ n t )) -Π 2 f (μ n t ) = nE μn t ⟨μ n t , f ⟩ 2 + 2 1 n ⟨ϑ(nμ n t ), f ⟩ ⟨μ n t , f ⟩ + 1 n 2 ⟨ϑ(nμ n t ), f ⟩ 2 -⟨μ n t , f ⟩ 2 = nE μn t 2 1 n ⟨ϑ(μ n t ), f ⟩ ⟨μ n t , f ⟩ + 1 n 2 ⟨ϑ(μ n t ), f ⟩ 2 .
On one hand, the martingale problem for Π 2 f gives that

Π 2 f (μ n t ) -Π 2 f (μ n 0 ) - t 0 L n Π 2 f (μ n s )ds (III.36)
is a martingale. On the other side, since X t := ⟨μ n t , f ⟩ is a finite variation pure jump III.3. NORMALIZATION AND SCALING CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES process, it is in particular a semi-martingale. For g ∈ C 2 (R), where C 2 (R) is the space of doubly differentiable functions with continuous second derivatives, Itô's formula (See [START_REF] Jacod | Limit Theorems for Stochastic Processes[END_REF] theorem 4.57 p57) yields :

g(X t ) -g(X 0 ) = t 0 g ′ (X s-)dX s + 1 2 t 0 g"(X s-)d[X s ] c + s≤t g(X s ) -g(X s-) -g ′ (X s-)∆X s - 1 2 g"(X s-)(∆X s ) 2 .
In our particular case, taking g(x) = x 2 gives

⟨μ n t , f ⟩ 2 -⟨μ n 0 , f ⟩ 2 = 2 t 0 μn s-, f d ⟨μ n s , f ⟩ + s≤t (⟨μ n s , f ⟩ -⟨μ n s -, f ⟩) 2 . (III.37)
Noticing that the martingale problem for

⟨μ n s , f ⟩ is equivalent, in its differential form, to d ⟨μ n s , f ⟩ = dM f,n t + L n Π f (μ n s )ds and also that s≤t ⟨μ n s , f ⟩ -μn s -, f 2 = M f,n t because ⟨µ s , f ⟩ et M f,n s
have the same jumps. The last expression easily implies that

⟨μ n t , f ⟩ 2 -⟨μ n 0 , f ⟩ 2 = 2 t 0 ⟨μ n s -, f ⟩ dM f,n t +2 t 0 ⟨μ n s -, f ⟩ Ln Π f (μ n s )ds+ M f,n t (III.38)
But a difference of (local) martingales is a (local) martingale, and (III.36) is compared to (III.38) yielding that

M f,n t - t 0 Ln Π 2 f (μ n s ) -2 ⟨μ n s -, f ⟩ Ln Π f (μ n s ) ds (III.39)
is a martingale. By uniqueness of the predictable compensator of M f,n , we can conclude that

≪ M f,n ≫ t = t 0 L n Π 2 f (μ n s ) -2 ⟨μ n s -, f ⟩ Ln Π f (μ n s ) ds = nE μn t ( 1 n ⟨ϑ(μ n t ), f ⟩) 2 .
Finally, we prove that M f,n is square integrable. For all t ∈ [0, 1], considering that III.3. NORMALIZATION AND SCALING CHAPTER III. LOCAL MATCHING ALGORITHMS AS MARKOV PROCESSES f (a t ) ≤ ∥f ∥ and a t < n, we beget

≪ M f,n ≫ t = 1 n E μn t (⟨ϑ(μ n t ), f ⟩ 2 ) = 1 n E μn t   f (K) + f (K ′ ) + I ′ l ∈N (I) f (a k (I ′ l )) -f (a k (I ′ l ) -D I ′ l ) + I l ∈N (I ′ ) f (a k (I l )) -f (a k (I l ) -F I l )   2 ≤ ∥f ∥ 2 (2 + 4n) 2 < ∞,
which implies that M f,n is indeed a square integrable martingale. ■

Chapter IV

Performance Prediction and Concentration Results

In this final chapter, we enunciate and we prove the main convergence result. As the number of nodes n becomes large, the matching coverage is concentrated around a deterministic value. In a similar fashion to the law of large numbers, this value will be used as a predictor for the performance of any given criterion. Subsequently, those predictors offer a framework for the comparison of matching criteria. Our work here closely follows that of [START_REF] Bermolen | The jamming constant of uniform random graphs[END_REF] on the jamming constant and can be seen in the context of the differential equation method (eg. [START_REF] Wormald | The differential equation method for random graph processes and greedy algorithms[END_REF]). Pioneered by [START_REF] Kurtz | Limit theorems for sequences of jump markov processes approximating ordinary differential processes[END_REF], this method consists of approaching random dynamics (especially on networks) by a limiting deterministic function solution of an Ordinary Differential Equation. Our particular procedure is an extension of the method in turn introduced by (Decreusefond et al. [2012]) where the Differential Equation Method was extended to measure valued processes. It is closely tied to [START_REF] Noiry | Online matching in sparse random graphs: Non-asymptotic performances of greedy algorithm[END_REF] where the same approach is applied to online bipartite matching, only the degree distribution is viewed in the light of its generating functions instead of using a measure valued approach.

The chapter is comprised of three main sections. In the first section, the main result of our research is established: the stochastic matching dynamic converges to a deterministic continuous function. A direct implication of this result is that the matching coverage also converges to a deterministic value. Evermore, we support this result by updating the simulations given in chapter II with the predicted values. Afterward, the following section is devoted to the proof of the main convergence result. The proof works as a typical convergence result in the Skorokhod topology. First, the existence of several limits is established via tightness, before the limits are characterized as unique with the use of the martingale property. The final section of the chapter is devoted to an application of the main result on the greedy criterion.

IV.1. MAIN THEOREM CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

IV.1 Main theorem

In this first section, we enunciate the main result of the thesis. Under properly defined criteria, the (random) dynamic defined by the algorithms, and by extension their matching coverage, converges to deterministic values.

First, we have to establish the asymptotic behavior of any given algorithm. Remark III.2.2 hinted that the exact law of our processes is inconvenient to deal with. We provide an alternative dynamic whose generator encodes the asymptotic behavior of criteria despite being simpler to use.

Definition IV.1.1 (Alternative dynamic). Fix a counting measure µ ∈ M F (N). To each i ∈ N * are associated µ(i) buckets of i items. (Buckets and items correspond to nodes and half-edges in the original construction.) So there are b := ⟨µ, 1 N * ⟩ buckets and a total of c = ⟨µ, χ⟩ items. We label the buckets arbitrarily, as 1, ..., b. Denote for any j = 1, ..., b, a(j) the cardinality of bucket j. We also label the items from 1 to c as follows: items 1 to a(1) are the elements of bucket 1, labeled arbitrarily, items a(1) + 1, ..., a(1) + a(2) are the elements of bucket 2, and so on... For any i = 1, ..., c, we let B(i) be the bucket of item i.

We perform the following random experiment, which mimics the original dynamics when the sampling is performed with replacement:

(i) We draw an element, say j, of 1, b , following Φ K (B(1), ..., B(b)) and set I := j, the corresponding bucket. We denote by K = a( I), its cardinality. To differentiate this choice from the one without replacement, we denote its law Φ K1 .

(ii) Then we draw uniformly at random, and with replacement, K items among c, denoted by i 1 , ..., i K . For all ℓ ∈ 1, K we denote by B ℓ = B(i ℓ ), the bucket i ℓ belongs to.

(iii) Following Φ K ′ (B 1 , ..., B ℓ ), one item i K is drawn among c. We also denote by I ′ = B(i K ), the match of I, and by K ′ = a( I ′ ), the cardinality of that bucket. Again, to differentiate this choice from the one without replacement, we denote its law

Φ K ′ (iv) If K ′ > 1,
we draw uniformly at random, and with replacement, K ′ -1 items among c, denoted by i ′ 1 , ..., i ′ K ′ -1 . Then, for all ℓ ∈ 1, K ′ -1 we denote by B ′ ℓ = B(i ′ ℓ ), the bucket i ′ ℓ belongs to.

IV.1. MAIN THEOREM CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

Finally, we can exhibit the measure representation induced by that procedure,

ϑ(µ) = -δ K + δ K ′ + ℓ∈ 1, K-1 δ a( B ℓ ) -δ a( B ℓ )-1 + ℓ∈ 1, K ′ -1 δ a( B ′ ℓ ) -δ a( B ′ ℓ )-1 . (IV.1)
Thus, the approximated dynamic is written as follows,

Lemma IV.1.1. For any counting measure µ such that ⟨µ, χ⟩ > 0 and any f ∈ C b , we have

E µ ϑ(µ), f = LΠ f (µ),
where,

LΠ f (µ) := -Φ K (µ), f + Φ ′ K ′ (µ), f + ⟨µ, χ∇f ⟩ ⟨µ, χ⟩ Φ K (µ), χ -1 + Φ ′ K ′ (µ), χ -1 , (IV.2)
or recalling from equation (III.26) that Φ defines the matching criterion adapted to normalized (instead of counting) measures:

LΠ f (μ) := -Φ K (μ), f + Φ′ K ′ (μ), f + ⟨μ, χ∇f ⟩ ⟨μ, χ⟩ Φ K (μ), χ -1 + Φ ′ K ′ (μ), χ -1 , (IV.3)
where μ is a normalized measure.

Proof. From its very construction above K follows Φ K (µ):

P µ K = k = Φ K (µ)(k).
(IV.4)

And, as the bucket I ′ is drawn following Φ K ′ (µ ′ ) where µ ′ = ℓ∈ 1, K δ a( B ℓ ) the size K ′ of that bucket follows Φ K ′ applied to a K sized sample of the size-biased distribution associated to µ. Hence,

Φ ′ K ′ (µ)(k ′ ) = E µ P µ ′ K ′ = k ′ (IV.5)
IV.1. MAIN THEOREM

CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

Likewise, all r.v.'s a( B ℓ ), ℓ ∈ 1, K -1 and a( B ′ ℓ ), ℓ ∈ 1, K -1 , follow the size-biased distribution associated to µ: conditionally on K = k and K ′ = k ′ > 0, for any l ∈ 1, k and any ℓ ∈ 1, k ′ -1 we clearly have that

P µ a B l = x = xµ (x) ⟨µ, χ⟩ , x ∈ N; (IV.6) P µ a( B ′ ℓ ) = y = yµ (y) ⟨µ, χ⟩ , y ∈ N.
Giving us the desired expression:

E µ ϑ(µ), f = - +∞ k=1 f (k)Φ K (µ)(k) + (k -1)Φ K (µ) +∞ y=1 yµ(y) ⟨µ, χ⟩ (f (y) -f (y -1)) - ∞ k ′ =0 f (k ′ )Φ ′ K ′ (µ)(k ′ ) + (k ′ -1)Φ ′ K ′ (µ) +∞ y=1 yµ(y) ⟨µ, χ⟩ (f (y) -f (y -1)) = -Φ K (µ), f + Φ ′ K ′ (µ), f + ⟨µ, χ∇f ⟩ ⟨µ, χ⟩ Φ K (µ), χ + Φ ′ K ′ (µ), χ = LΠ f (µ).

■

Remark IV.1.1. We draw attention to the fact the alternative construction allows us to essentially make every choice with replacement this time. Hence, every choice function is directly applied either to the base measure or to its perfectly size biased version. Later, we will show that this alternative dynamic stays arbitrarily close to the 'real' dynamic when the graphs get large. For now, it is used to state the main theorem.

But before that, one last definition is needed. condition on the operator L is used (See for example [START_REF] Kurtz | Solutions of ordinary differential equations as limits of pure jump markov processes[END_REF]). Uniqueness of the limiting process in our case is harder to identify, thus we have to enclose it in a definition and allow it to become criteria dependent.

IV.1.1 Convergence of local matching algorithms

The main convergence result is finally stated.

Theorem IV.1.1. Assume that Φ := ( ΦK (.), Φ′ K ′ (.))2 is a well behaved and moment preserving matching criterion that is defined on a subspace M Φ of M. Assume that ( Φ K (.), Φ′ K ′ (.)) is the alternative dynamic associated to Φ. Recall the operator

LΠ f (μ) := -Φ K (μ), f + Φ′ K ′ (μ), f + ⟨μ, χ∇f ⟩ ⟨μ, χ⟩ Φ K (μ), χ -1 + Φ ′ K ′ (μ), χ -1 . (IV.8)
If the sequence of processes (μ n . ) n≥1 is under H0, and L characterizes a measure valued function μ. , then for all f ∈ C b we have the convergence in probability

M n Φ (µ n 0 ) = 1 - I n n n = 1 -μn 1 ({0})•
The result is obtained by merely taking the limit in n.

■

The main convergence result can be viewed as a law of large numbers for the matching coverage. At worst, it is an asymptotic result specific to the configuration model restricted to some constrained degree distributions. However, the constraints make it so IV.1. MAIN THEOREM CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS the configuration model, and the associated algorithms produce matching coverages that are asymptotically equal to that of simple graphs. Hence, we interpret the main result as a prediction of the matching coverage produced by a criterion on a graph drawn uniformly following a given degree distribution.

IV.1.2 Further simulations

We finally complement the simulations given in Chapter II. In this section, we go back to 3-regular graphs, this time using the measure valued representation for the degree sequences. In this case, we readily obtain the degree distributions : By a numerical resolution, we predict the final value μ-1 (0) = 0.1098 (which is the final value of the red curve in Figure IV.1). From this, we deduce the approximate matching coverage which is a very similar to the one obtained for the greedy algorithm in [START_REF] Noiry | Online matching in sparse random graphs: Non-asymptotic performances of greedy algorithm[END_REF]. Again, we compile the evolution of the simulated matching coverage as the graph size n grows but this time we also add the matching coverage predicted by (IV.10). As the figures show, the prediction given by the ODE is fairly accurate. In fact, the exact numbers are more striking when we update the next section to the formal proof of the main theorem.

M greedy (δ 3 , δ 3 ) = 1 -μ- 1 (

IV.2 Proof of the main convergence theorem

The proof of the main theorem is a typical proof of convergence for a Markov process: it is shown that the law of the sequence μn

. is tight (thus relatively compact) in the Skorokhod topology, then it is shown that all the limits are in fact characterized by the given operator L, and finally it follows that since the ODE resulting from L identifies a unique function μ. , the sequence of processes converges to μ. . In summary, for any t ≤ 1 we will establish bounds on each of the terms of

|⟨μ n t , f ⟩ -⟨μ t , f ⟩| = |⟨μ n t , f ⟩ -⟨μ n t , f ⟩ + ⟨μ n t , f ⟩ -⟨μ t , f ⟩| ≤ | ⟨μ n t , f ⟩-⟨μ n t , f ⟩ |+ ⟨μ n 0 , f ⟩ + M f,n t + t 0 Ln Π f (μ n s )ds -⟨μ 0 , f ⟩ - t 0 LΠ f (μ s )ds ≤ | ⟨μ n t , f ⟩ -⟨μ n t , f ⟩ | + | ⟨μ n 0 , f ⟩ -⟨μ 0 , f ⟩ | + |M f,n t | + t 0 Ln Π f (μ n s ) - t 0 LΠ f (μ s )ds , (IV.14)
where we used the fact that

⟨μ n t , f ⟩ = ⟨μ n 0 , f ⟩ + M f,n t + t 0 Ln Π f (μ n s ), (IV.15)
and that μ. is a solution of

⟨μ t , f ⟩ = ⟨μ 0 , f ⟩ + t 0 LΠ f (μ s )ds, 0 ≤ t ≤ 1. (IV.16)
The convergence is established if the right-hand term of (IV.14) goes to 0.

Proof. The first step of the proof is to establish the existence of sub-sequential limits for the sequence of processes.

Part 1: Tightness First, the relative compactness of the laws of the processes (μ n

. ) n≥1 is proven in D([0, 1], (M, τ v )),
where τ v denotes here the vague topology. The relative compactness is simpler to prove in the vague topology. Recalling that the tilde process μn . is the continuous time Markov approximation (with exponential inbetween jumps), we use Prohorov's theorem [START_REF] Parthasarathy | Ii -probability measures in a metric space[END_REF]; [START_REF] Billingsley | The Space D, chapter 3[END_REF]) which equates the relative compactness of (μ n . ) n≥1 with its tighness. Thus, we have to prove the tightness, Proof. Méleard and Roelly [START_REF] Méléard | Sur les convergences étroite ou vague de processus à valeurs mesures[END_REF]) have shown that for (μ n . ) n≥1 to be tight in D([0, 1], (M, τ v )), it is enough that, for any f ∈ C c , the sequence of processes

(⟨μ n . , f ⟩) n≥1 is tight on D([0, 1], R
). Roelly's tightness criterion [START_REF] Roelly-Coppoletta | A criterion of convergence of measure-valued processes: application to measure branching processes[END_REF])

is used to prove the latter:

1. Fix t ≥ 0, for all n we write | ⟨μ n t , f ⟩ | ≤ ∥f ∥| ⟨μ n t , 1⟩ | ≤ ∥f ∥. Hence, (⟨μ n t , f ⟩) n≥1 is a bounded sequence on R, which means that it is tight (since it is relatively compact).

2. Fix n ≥ 1. Recalling (III.34), for t ∈ [0, 1], ⟨μ n t , f ⟩ is rewritten as

⟨μ n t , f ⟩ = M f,n t + V f,n t .
Let δ > 0 and two stopping times S n and T n such that S n ≤ T n ≤ S n + δ. On the one hand, for ϵ > 0 using the Markov inequality we have

P |⟪M f,n ⟫ Tn -⟪M f,n ⟫ Sn | > ϵ ≤ 1 ϵ E |⟪M f,n ⟫ Tn -⟪M f,n ⟫ Sn | .
Remembering the definition IV.34, we write

⟪M f,n ⟫ Tn -⟪M f,n ⟫ Sn = 1 n Tn Sn E μn s (⟨ϑ(μ n s ), f ⟩ 2 )ds = 1 n Tn Sn E μn s      f (K) + f (K ′ ) + I ′ l ∈N (I) f (a k (I ′ l )) -f (a k (I ′ l ) -D I ′ l ) + I l ∈N (I ′ ) f (a k (I l )) -f (a k (I l ) -F I l )    2   ds ≤ δ n (∥f ∥(2 + 4 × o( √ n)) 2 . (IV.
P |V f,n Tn -V f,n Sn | > ϵ ≤ δ ϵ ∥f ∥(2 + 4M ), (IV.20)
proving the tightness in D([0, 1], (M, τ v )).

■

As said at the start of this part, the vague convergence is not enough. Noticing that the processes characterized by L are continuous in time and that continuity of the limiting processes is required, we need a further characterization of the eventual sub-sequential limits.

Lemma IV.2.2. The sequence (⟨μ n . , f ⟩) n≥1 is C-tight3 .

Proof. For all n and t ∈ [0, 1], let (∆ ⟨μ n t , f ⟩) be the jump of ⟨μ n t , f ⟩ at t. ∆ ⟨μ n t , f ⟩ is either 0 or 1 n ⟨ϑ(nμ n t )⟩. But

1 n | ⟨ϑ(nμ n t ), f ⟩ | ≤ 1 n ∥f ∥(2 + 4o( √ n)). (IV.21)
This goes to show that, sup t ∆ ⟨μ n t , f ⟩ n -→ 0, proving that limits are indeed continuous. ■ Hence, we can finally write the tightness in D([0, 1], (M, τ w )) where τ w denotes the weak topology. We stress that the weak tightness is needed since the matching coverage depends on μ. , 1 {0} and whence 1 {0} is a compactly supported function, the associated mass is μt , 1 {0} = ⟨μ t , 1⟩μt , 1 {R + * } and it depends on the non compactly supported function

1 {R + * } .
Corollary IV.2.1. The sequence of processes (μ n . ) n≥1 is tight in D([0, 1], (M, τ w )).

Proof. Following [START_REF] Méléard | Sur les convergences étroite ou vague de processus à valeurs mesures[END_REF]), (μ n . ) n≥1 is weakly tight if it is vaguely C-tight and the mass process (⟨μ n . , 1⟩) n≥1 is tight in D([0, 1], R).

We have yet to prove the tightness of (⟨μ n . , 1⟩) n≥1 in D([0, 1], R). But we can notice that the proof is exactly the same as Lemma IV.2.1 for f ≡ 1.

■ CONVERGENCE THEOREM

CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

So far, we have proven that the sequence of normalized processes admit subsequential limits. We also know that the eventual limits are continuous. Since the processes themselves are described (following Doob) by the equation

⟨μ n t , f ⟩ = ⟨μ n 0 , f ⟩ + M f,n t + t 0 Ln Π f (μ n s ),
for them to be deterministic, we need the martingale part of the description to cancel itself.

Part 2: Cancellation of the martingale part

It is straightforward to write that for all n and t,

E (M f,n t ) 2 = E⟪M f,n ⟫ t ≤ t n (∥f ∥(2 + 4 × o( √ n)) 2 .
And, since the rightmost term goes to 0, Doob's martingale inequality then yields that

P(sup t≤1 |M f,n t | > ϵ) ≤ 1 ϵ 2 t n (∥f ∥(2 + 4 × o( √ n)) 2
goes again to 0. Thus M f,n .

converges in probability to 0. Hence, the convergence in probability implies following equation (IV.15) that when n gets large enough, the behavior of the dynamic is close to that of ⟨μ n 0 , f ⟩ + t 0

Ln Π f (μ n s ). Going forward, the sequence of processes μn

. have been shown to have continuous limits and we have just established that those limits are described by a deterministic equation of the tilde operators. But, the Ln operators do not have an explicit form and, as was shown in section III.3.1 they are not guaranteed to converge themselves. Henceforth, the goal of the next part of the proof to set up L operator as the limit of the tilde operators. We prove that well-behaved, moment preserving matching criteria induce convergent operators.

The identification of the limit is done through a coupling with the alternative dynamic which induces L as a generator.

Part 3: Identifying the Limit Remark IV.2.1. Throughout this section and all the thesis, it is important to remember that the bars¯are associated with normalized objects and that tildes˜are for the continuous time Markov Chain. When there is no accent, we are working directly with counting measures. For example, LΠ f (µ) is a generator associated to counting measures and is M F valued, while Ln Π f (μ n t ) is the generator of the continuous Markov extension and is thus M n valued and LΠ f (μ n t ) is the limiting generator of both the normalized process and its Markov extension. Technically, it is associated with the alternative construction but since it is the limit, we chose not to add the hat superscript. CONVERGENCE THEOREM CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS because I has K neighbors again following the size-biased distribution associated to µ. This, combined with (IV.24) and (IV.25) in (IV.23), yields that

P µ ( T c ) ≤ ⟨µ, χ 2 ⟩ ⟨µ, χ⟩ 2 Φ K (µ), χ 2 + ⟨µ, χ 2 ⟩ ⟨µ, χ⟩ 2 Φ K ′ (µ), χ 2 + ∞ k=2 ∞ k ′ =2 k + k ′ + k ⟨µ,χ 2 ⟩ ⟨µ,χ⟩ ⟨µ, χ⟩ Φ K (µ)(k)(k ′ Φ ′ K ′ (µ)(k ′ )).
Ultimately noticing that ⟨µ,χ 2 ⟩ ⟨µ,χ⟩ ≥ 1, we obtain that

P µ ( T c ) ≤ ⟨µ, χ 2 ⟩ ⟨µ, χ⟩ 2 Φ K (µ), χ 2 + 2 ⟨Φ K (µ), χ⟩ + 2 Φ K ′ (µ), χ 2 .

■

We follow with the intermediary approximation of the generator:

Proposition IV.2.1. Let µ in M n F , the following is true for some constant C > 0:

|LΠ f (µ) -L n Π f (µ)| ≤ C∥f ∥ ⟨µ, χ 2 ⟩ ⟨µ, χ⟩ 2 Φ K (µ), χ 2 + ⟨Φ K (µ), χ⟩ + Φ K ′ (µ), χ 2 .
Proof. Fix a measure µ, and denote the event T (µ) = I and I ′ do not have any self-loops/multiple edges, given that the degree measure is µ .

Throughout this proof, for notational simplicity let us skip the dependence in µ of ϑ, ϑ, T and T . First, as uniform sampling with replacement and conditioned on not drawing twice the same element amounts in law to a uniform sampling without replacement, we get that for any point measure ν,

P µ ϑ = ν | T = P µ (ϑ = ν | T ) .
(IV.26) Also, it is immediate to observe that self-loops and multiple edges occur with a larger probability if draws of half-edges are performed with replacement, with respect to draws CONVERGENCE THEOREM CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS without replacement. Thus we get that P µ (T ) ≥ P µ T , and set

q µ := P µ (T ) -P µ T 1 -P µ T ∈ (0, 1).
Let the M F (N)-valued r.v. θ be drawn from the distribution P µ (ϑ = . | T ) with probability q µ , and independently, from the distribution P µ (ϑ = . | T c ) with probability 1 -q µ , and let us set

ϑ = ϑ1l T + θ1l T c .
So defined, ϑ is a M F (N)-valued r.v. that coincides with ϑ on T , and that has the same distribution as ϑ. To see this, observe that for all v ∈ M p (N),

P µ ϑ = v = P µ ϑ = v | T P µ T + P µ ϑ | T c P µ T c = P µ ϑ = v | T P µ T + P µ (ϑ = v | T ) q µ + P µ (ϑ = v | T c ) (1 -q µ ) P µ T c = P µ (ϑ = v | T ) P µ T + P µ (ϑ = v | T ) P µ (T ) -P µ T + P µ (ϑ = v | T c ) P µ (T c ) = P µ (ϑ = v) ,
where we used (IV.26) in the third equality. Therefore, as T ⊂ { ϑ = ϑ ′ }, we obtain from the definition of the generator and Lemma IV.1.1 that :

|LΠ f (µ) -L n Π f (µ)| = E µ [⟨ϑ, f ⟩] -E µ ϑ, f = E µ ϑ -ϑ, f 1l T c ≤ E µ ϑ -ϑ, f 2 1/2 P µ T c 1/2 ≤ 2E µ ϑ, f 2 + 2E µ ϑ, f 2 1/2 P µ T c 1/2 = 2E µ ⟨ϑ, f ⟩ 2 + 2E µ ϑ, f 2
E µ ϑ, f 2 ≤∥ f ∥ 2 E µ ϑ, 1 2 =∥ f ∥ 2 E µ 2 + 2 K + 2 K ′ 2 ≤ 12 ∥ f ∥ 2 1 + E µ K 2 + E µ ( K ′ ) 2 .
Also, by the same arguments we obtain that

E µ ⟨ϑ, f ⟩ 2 ≤ 12 ∥ f ∥ 2 1 + E µ K 2 + E µ (K ′ ) 2
which concludes the proof using (IV.27) and Lemma IV.2.3. ■ At last, this provides the large graph approximation, Corollary IV.2.2. Let μn . a sequence of M n valued processes associated to a well behaved and moment preserving criterion Φ. Moreover, assume that its initial conditions are under H0. For any bounded f , and any t ≤ 1, we have

LΠ f (μ n t ) -Ln Π f (μ n t ) = o( 1 √ n ).
(IV.28)

Proof. First, we rewrite the definitions of the scaled counterparts of L n and of the matching criteria :

Ln Π f (μ n t ) := L n Π f (nμ n t ) Φ(μ n t ) := Φ(nμ n t ) Proposition IV.2.1 yields that LΠ f (μ n t ) -Ln Π f (μ n t ) ≤ C∥f ∥ ⟨μ n t , χ 2 ⟩ ⟨μ n t , χ⟩ 2 Φ K (μ n t ), χ 2 + ⟨Φ K (μ n t ), χ⟩ + Φ K ′ (μ n t ), χ 2 .
Since the initial moments up to p = 3 are bounded, and the criterion is moment preserving, it follows easily from proposition III.3.1 that, for some C ′ > 0 :

LΠ f (μ n t ) -Ln Π f (μ n t ) ≤ C ′ ∥f ∥ ⟨μ n t , χ 2 ⟩ ⟨μ n t , χ⟩ 2 1/2 .
Again using H0 and the fact that the moments are non increasing, we write ⟨μ n t , χ⟩ = O(n) and also ⟨μ n t , χ 2 ⟩ = O(n). Finally, the approximation is complete :

LΠ f (μ n t ) -Ln Π f (μ n t ) ≤ C ′ ∥f ∥O( 1 √ n ) = O( 1 √ n ). ( IV

■

In summary, we have just now proven that the operator driving the large graph behavior of the limits get arbitrarily close to L. The only thing left is to link all the eventual limits to the solution of the ODE driven by the bar operator. In the final part of the proof, we can finally establish the main theorem.

Part 4: Convergence to the unique solution

To complete the proof, one needs to remember the equation (IV.14) : For all n, t and f as above,

|⟨μ n t , f ⟩ -⟨μ t , f ⟩| ≤ | ⟨μ n t , f ⟩ -⟨μ n t , f ⟩ | + | ⟨μ n 0 , f ⟩ -⟨μ 0 , f ⟩ | + |M f,n t | + t 0 Ln Π f (μ n s ) - t 0 LΠ f (μ s )ds ,
where μ. is characterized by L in the sense that μ. is the unique deterministic function such that for any suitable initial state ν,

⟨μ t , f ⟩ = ⟨ν, f ⟩ + t 0 LΠ f (μ s )ds.
Ultimately, we can use the results we established earlier to show that every term on the right hand side tends to zero and that every converging sub sequence converges to μ.

First, under our premise, for some positive M : --→ 0 and we can use the tilde processes.

Ln Π f ( μn t ) ≤ ∥f ∥(2 + 4M
The convergence of | ⟨μ n 0 , f ⟩ -⟨ν, f ⟩ | to 0 is again immediate since it is required in H0.

As seen in the part 2 of the proof, the martingale part also converges to 0.

For the last term, suppose μϕ (n) . converges in law to μ. along a subsequence ϕ. Skorokhod's representation theorem gives the existence of a common probability space (Ω ′ , F ′ , P ′ ) where X ϕ (n) . are D([0, 1], M Φ ) valued random variables, each X ϕ (n) . has the same law as μϕ(n)

. and X ϕ (n) . converges a.s to X . and X . again has the same

Ln Π f (μ n s ) - t 0 LΠ f (μ s )ds ≤ t 0 | Ln Π f (μ n s ) -LΠ f (μ n s )|ds + t 0 LΠ f (μ s ) -LΠ f (μ n s )ds .
The first term on the RHS goes to zero by the large graph approximation of the semigroup (IV.2.2). For the second term, consider a convergent subsequence μψ(n)

. and let it converge almost surely to some µ * . (by placing ourselves directly in the common probability space). Using the hypothesis that the matching criterion is well behaved and the continuous mapping theorem, we have that LΠ f (μ n s )

n,P --→ LΠ f (μ * s ). Moreover, again by our premises, LΠ f (μ n s ) is bounded. We use the dominated convergence theorem to next assert that

t 0 LΠ f (μ n s )ds n - → t 0 LΠ f (μ * s )ds. Scaling (IV.15) alongside ψ(n) yields that ⟨µ * t , f ⟩ = ⟨ν, f ⟩ + t 0 LΠ f (μ * s )ds.
But L characterizes only μ. and we finally conclude that all the subsequential limits of μn . are in fact equal to μ. . We have therefore shown that sup

t∈[0,1] |⟨μ n t , f ⟩ -⟨μ t , f ⟩| n,P --→ 0, (IV.31)
effectively proving the convergence of μn t to μt , the unique solution of the ODE driven by L. ■ Remark IV.2.2. Our proof uses the same ideas upon which the differential equation method is based [START_REF] Kurtz | Extensions of trotter's operator semigroup approximation theorems[END_REF] or [START_REF] Ethier | Generators and Markov Processes[END_REF]). In both these works, the conditions for a convergence to a deterministic differential equation are given. In our proof, we adapted those arguments and expanded them to abstract matching criteria when required. Similarly to the work of [START_REF] Kurtz | Extensions of trotter's operator semigroup approximation theorems[END_REF] :

The fact that the generator L is the limit of the generators Ln in the sense of Kurtz is ensured by corollary IV.2.2. This corollary depends on the assumption that a chosen criterion is well behaved and moment preserving.

The fact that the limiting generator L defines a semigroup is ensured by the fact that it is simply the generator associated to an alternative Markov construction. Thus, it has to be under the conditions of the Hille Yosida theorem.

IV.3. ILLUSTRATIVE EXAM-PLE : greedy

CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

Finally, in [START_REF] Kurtz | Extensions of trotter's operator semigroup approximation theorems[END_REF] a condition of Lipschitzity was used to ensure that the deterministic differential equation born from L uniquely defined its solutions. In our case, even though Lipschitzity is sufficient, it will prove difficult to establish, especially on measure spaces. For this reason, we reframed that condition in a more abstract formulation.

At long last, we provide an example for the main result using the greedy criterion. It is demonstrated that the greedy algorithm verifies all the hypotheses of the main theorem and thus we are allowed to predict its matching coverage by solving the ODE (as is done in the simulations).

IV.3 Illustrative example : greedy

For this section, we recall that greedy uses a double uniform criterion, where the uniform choice is made over the positive activity vertices. We also set f as a generic function in C b . It is important to remember that the limiting behavior is given by the alternative, simpler dynamic. The greedy algorithm makes its first choice straight on the degree distribution:

Φ greedy K (µ), f = ⟨µ, f 1 N * ⟩ ⟨µ, 1 N * ⟩ , (IV.32)
whilst the second choice is made over the K neighbors which each follow a size biased distribution. We use the computations from (IV.5) apply : where μ. is characterized by the operator L defined by (IV.34) when ⟨µ, 1 N * ⟩ > 0, and LΠ f (µ) = 0 for all f ∈ C b , whenever ⟨µ, 1 N * ⟩ = 0.

Φ greedy K ′ (µ), f = k ′ f (k ′ )P µ ( K ′ = k ′ ) = k k ′ f (k ′ )P µ ( K ′ = k ′ |K = k)P µ ( K = k) = k k ′ f (k ′ ) k ′ µ(k ′ ) ⟨µ,
The convergence for greedy is proven by verifying that both the uniform choice function and the operator it produces verify the conditions of Theorem IV.1.1. To do so, we use the two following sections.

IV.3.1 Proof of Theorem IV.3.1: Well behavedness and moment properties Lemma IV.3.1 (greedy: Well-behavedness and moment preservation). Let µ ∈ M such that ⟨µ, χ⟩ > 0, then the uniform choice function is well behaved in the sense given by Definition III.3.1. Moreover, the greedy criterion preserves moments up to p -1 when p ≥ 2 and ⟨µ, χ p ⟩ ≤ M for some M > 0.

Proof. First, we prove the well behavedness. By definition, the weak topology is the weakest topology such that the functions (Π f (. The same technique is used for evaluating D 2 (x, y, f ) := my My A y -mx Mx A x :

D 2 (x, y, f ) = A y m y M y - m x M x + m x M x [A y -A x ] . (IV.39)
First off :

m y M y - m x M x = M x m y-x + M x-y m x M x M y .
Remembering the definition of A . , we also have that In particular, using f = 1 i , we have z({i}) := ⟨z, 1 i ⟩ and :

z ′ ({i}) = (i + 1) M y -m y M x + m x (V x -M x ) M 2 IV.
|Γ ′ 1 | ≤ M 2 + 3M β 2β 2 + 1 Γ, or |Γ ′ 1 | ≤ C 1 Γ (IV.44)
Afterwards, we have to find a similar majoration for Γ ′ 2 := 1 2 Γ ′ -Γ ′ 1 . First notice for z that :

For the mass m z :

m z ≤ k z k = k k α/2 z k k -α/2 .
Using Cauchy-Schwartz yields

m z ≤ ( k k α z 2 k ) 1/2 ( k k -α ) 1/2 .
Since α > 3.5, it follows that Since the terms outside the sums are multiples of the moments of z, they are to be bounded by Γ 1/2 multiplied by some constant, we can also find bounds for the other terms :

Starting with i i α z({i})(i + 1)y({i + 1}), Cauchy-Schwartz yields again i i α z({i})(i + 1)y({i + 1}) = i i α/2 z({i})(i + 1)i α/2 y({i + 1}) We finally beget :

≤ Γ
|Γ ′ 2 | ≤ C M + C m β Γ 1/2 2M Γ 1/2 + C M Γ 1/2 2M β 2 2M Γ 1/2 + M C M + C m β 2 Γ 1/2 C M + 2M β 2M Γ 1/2 + M β C V + C M β Γ 1/2 2M Γ 1/2 + C m Γ 1/2 2M 2 β 3 2M Γ 1/2 , or |Γ ′ 2 | ≤ C 2 Γ (IV.51)
Together with IV.44, IV.51 is equivalent to IV.36 ending the proof of the the uniqueness up to T β .

Since β is arbitrary and Π 1 N * (µ t ) is continuous in t. We can define :

T 0 = sup β>0 T β (IV.52)
and extend the uniqueness to t ≤ T 0 . But, we have already proven the uniqueness after T 0 . Because for any t > T 0 , the generator is null and the argument at the beginning of this proof applies : µ t = µ T 0 .

Hence, the generator associated to the greedy criterion globally characterizes the solutions of the associated differential equation and the main theorem is true for the greedy criterion. ■ Remark IV.3.1. The well behavedness and the moment preservation are fairly easy to assess for most matching criteria. As an illustrative example, for minres the first choice Chapter V

Notes and conclusion

Ultimately, the purpose of our work was to present an alternative framework to the study of online matching algorithms. In a world where large networks are gaining more and more prominence, our goal was to use the relatively recent tools offered by stochastic processes, queuing networks and random graphs to build efficient matching algorithms.

From a practical perspective, this work offers a way to predict the performances of specific matching policies given a population distribution, simply by (numerically for example) solving an ODE1 . For example, our results can be used to test how well individual matching policies would fare globally into a given population without having to go through extensive surveys. Independently of the population, our work can be extended to the comparison of given policies in a general framework. A relevant question for example would be which policies are better than total randomness? What would be the cost of applying such policies? In any case, The algorithms built in this framework are efficient by themselves. As shown by [START_REF] Aoudi | Markovian online matching algorithms on large bipartite random graphs[END_REF] or alternatively by [START_REF] Noiry | Online matching in sparse random graphs: Non-asymptotic performances of greedy algorithm[END_REF]) the present method, when adapted to bipartite networks already produces better results than the prevailing approach for online matching, even for mere greedy algorithms.

From a theoretical perspective, the present work falls within the scope of the methods that use random networks to emulate large networks and their limiting properties. Specifically, we studied exploration/marking processes on the configuration which we transposed to their measure valued representation. The 'choice functions' used here can be viewed as marking processes as well as favored directions guiding the exploration. Henceforth, the techniques provided here can easily be generalized to problems other than matching on graphs. The properties proved on matching policies are easily applicable to several other questions involving marking. In fact, our work itself follows directly from that of [START_REF] Bermolen | The jamming constant of uniform random graphs[END_REF] on the jamming constant.

CHAPTER V. NOTES AND CONCLUSION

As for the extensions of our work, the most important challenges are twofold. First, we still have to establish a consistent framework for the study of the uniqueness in an abstract policy. Even for the greedy criterion, the usual Cauchy-Lipschitz type conditions for the limits were insufficient. Second, thus far the comparison of given policies is only possible numerically. A theoretical comparison between abstract criteria seems very much out of reach. And even though we suspect a coupling argument to be sufficient, our work has not lead us to the adequate coupling and the optimal criteria we found, we only found numerically. To date, minres is the policy that produces the best matching coverage and a legitimate question to ask is that of the global optimality of minres amongst all criteria.

All things considered, we believe that the present work opens a promising line of research.

Figure I. 2 :

 2 Figure I.2: The marriage problem: When do such bipartite graphs admit a perfect matching?

  Figure I.3: The marriage problem: A solution

II 1 .

 1 Let Ů ⊂ V a collection of nodes, define the following core objects:

Φ

  Figure II.1: Exploring a vertex

  Figure II.3: Explored part of the graph after an iteration

  Figure II.6: Matching I with I ′

  Figure II.7: Matching I with I ′

  Figure II.8: Performance on Poisson Degree Distribution

  1 of both Greedy and Minres). In parallel, we extract (d + , d -) the degree distributions of the graph under consideration, on which we run both Greedy and Minres (the CM version of Section II.2), thereby constructing another (multi-)graph having the same degree distribution. Our results can be summarized in Figure II.10.

Figure

  Figure II.10: Exploration Vs Conf Model

1 )

 1 for all bounded continuous function f ∈ C b (N) (resp. compactly supported functions f ∈ C c (N)). Again C b (N) (resp. f ∈ C c (N)) is endowed with its usual topology, ∥f ∥ = sup x∈N |f (x)|.

Proposition III. 3 . 1 .

 31 Let p ≥ 1, n ≥ 1 and µ n . a sequence of Markov chains under the criterion Φ, such that : 1. Φ is well behaved and it preserves the moments of order p 2. 1 n ⟨µ n 0 , χ p ⟩ n -→ ⟨μ, χ p ⟩ for some μ ∈ M Then, there exists 0 < M < ∞ sup n>0,t>0

Definition IV. 1 . 2 .

 12 Let M Φ a (closed) subspace of M, L a linear operator on C b (M), andµ . : [0, 1] → M. The operator L characterizes µ . on M Φ if, for all t ∈ [0, 1], f ∈ C b and η . such that ⟨η t , f ⟩ = ⟨µ 0 , f ⟩ + t 0 LΠ f (η s )ds, (IV.7) we have η . = µ . .The preceding definition is a placeholder for the fact that the limiting system, characterized by the operator L, has a unique solution. Oftentimes, a Cauchy-Lipschitz type IV.1. MAIN THEOREM CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

1 (

 1 Convergence of the matching coverage). Under the above assumptions, for μn 0 → ν ∈ M Φ , we getM n Φ (μ n 0 ) (n,P) ---→ M Φ (ν) := 1 -μ1 ({0}). (IV.10)Proof. Equation (III.25) provides the matching coverage as a function of the normalized matching process :

  μ+ 0 = δ 3 and μ-0 = δ 3 . (IV.11) s (k) for k = 0, . . . , 3 and s ∈ [0, 1].

Figure IV. 1 :

 1 Figure IV.1: greedy-EDO results for μ+ 0 = μ-0 = δ 3

  0) = 0.8902. (IV.12) Regarding minres, similarly to greedy we deduce the approximate matching cover-

Figure

  Figure IV.2: Matching coverage of greedy as the graph size tends to ∞

IV 1 .

 1 Under the conditions of IV.1.1, the sequence (μ n . ) n≥1 is tight in D([0, 1], (M, τ v )).

  χ⟩ k1 N * (k)µ(k) ⟨µ, 1 N * ⟩ = ⟨µ, χf ⟩ ⟨µ, χ⟩ • (operator L is explicited for greedy. Plugging (IV.32) and (IV.33) into (IV.3) we immediately get thatLΠ f (µ) = -⟨µ, f 1 N * ⟩ ⟨µ, 1 N * ⟩ + ⟨µ, (χ -1 N * )⟩ ⟨µ, 1 N * ⟩ ⟨µ, χ∇f ⟩ ⟨µ, χ⟩ + ⟨µ, χf ⟩ ⟨µ, χ⟩ + ⟨µ, χ 2 -χ⟩ ⟨µ, χ⟩ ⟨µ, χ∇f ⟩ ⟨µ, χ⟩ . (IV.34)Ultimately, the main theorem for the greedy criterion is expressed:Theorem IV.3.1. Assuming that the graphs are under the greedy criterion, if the sequence of processes (μ n . ) n≥1 is under H0 and ⟨ν, ξ 3.5 ⟩ ≤ M , then for f ∈ C b sup t≤1 | ⟨μ n t , f ⟩ -⟨μ t , f ⟩ | (n,P)---→ 0, (IV.35)

  ), f ∈ C b ) are continuous. Notice that f 1 N * is still in C b so that Φ greedy K (µ) = Π f 1 N * (µ) Π 1 N * (µ)is a continuous function on M when Π 1 N * (µ) is non zero : The uniform choice function is well behaved. IV.3. ILLUSTRATIVE EXAM-PLE : greedy CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTSFor this, we start by finding a convenient expression for z ′ ({i}). By the very definition of L any f ∈ C b ⟨z, f ⟩ ′ can be rewritten as⟨z, f ⟩ ′ = LΠ f (x) -LΠ f (y) = ⟨y, f 1 N * ⟩ m y -⟨x, f 1 N * ⟩ m x + (M y -m y ) ⟨y, χ∆f ⟩ m y M y -(M x -m x ) ⟨x, χ∆f ⟩ m x M x 0 (x, y, f ) + D 1 (x, y, f ) + D 2 (x, y, f ). (IV.37)First, expanding the expression of D 1 (x, y, f ) we get thatD 1 (x, y, f ) = ⟨x, χ∆f ⟩ m x M x ⟨y -x, χ -1 N * ⟩ + ⟨y, χ -1 N * ⟩ ⟨y, χ∆f ⟩ m y M y -⟨x, χ∆f ⟩ m x M x = ⟨x, χ∆f ⟩ m x M x ⟨y -x, χ -1 N * ⟩ + ⟨y, χ -1 N * ⟩ ⟨y, χ∆f ⟩ m x M x -⟨x, χ∆f ⟩ m y M y m y M y m x M x = ⟨x, χ∆f ⟩ m x M x ⟨y -x, χ -1 N * ⟩+ ⟨y, χ -1 N * ⟩ ⟨y -x, χ∆f ⟩ m y M y -⟨y, χ∆f ⟩ (m y M y -m x M x ) m y M y m x M x • (IV.38)

A

  y -A x = ⟨y -x, χf ⟩ + y -x, χ 2 -χ ⟨y, χ∆f ⟩ M y + x, χ 2 -χ ⟨y -x, χ∆f ⟩ M y + ⟨y, χ∆f ⟩ ⟨y -x, χ⟩ M y M x . 2 (x, y, f ) is rewritten : D 2 (x, y, f ) = A y M x m y-x + M x-y m x M x M y + m x M x [ ⟨y -x, χf ⟩ + y -x, χ 2 -χ ⟨y, χ∆f ⟩ M y + x, χ 2 -χ ⟨y -x, χ∆f ⟩ M y + ⟨y, χ∆f ⟩ ⟨y -x, χ⟩ M y M x (IV.40)

m

  z ≤ Γ 1/2 C m . (IV.45) where C m > 0 In a similar fashion :M z = k kz k = k k α/2 z k k 1-α/2 PLE : greedy z({i}) (ix({i}) -(i + 1)x({i + 1})) -M z M y -m y M y M x i i α z({i}) (iy({i}) -(i + 1)y({i + 1})) + m x M z -M x m z M y M x i i α z({i})A y({i})m x M x V z -M z M y i i α z({i}) (iy({i}) -(i + 1)y({i + 1}))m z m x M x V x -M x M x M y i i α z({i}) (iy({i}) -(i + 1)y({i + 1})) . (IV.48)

  Its importance as a central tool in algorithms would only get traction later, after both Solovay

	I.3. MODERN DAYS	CHAPTER I. INTRODUCTION
	in algorithms.

  General local matching algorithm for a choice criterion Φ

	II.2. LOCAL MATCHING ON	CHAPTER II. LOCAL
	THE CONFIGURATION MODEL	MATCHING ALGORITHMS
	Algorithm 1 Require: Non-empty graph G = ( Ů, E)
	Matching ← ∅;
	for t < n do
	Pick I following Φ I ( V);
	Discover its neighborhood N ( I) in Ů;
	Ů ← Ů \ I ;
	if N ( I) is empty then
	Do not do anything more
	else
	Pick I′ following Φ
		8)

I′ ( N ( I)); Ů ← Ů \ I′ ; Matching ← Matching ∪ ( I, I′ ); end if t ← t + 1; end for

  the graph gets larger, the fluctuations get smaller and smaller, heuristically showing the concentration of the matching coverage M n Φ (G)/n for both algorithms. Means and standard deviations of the corresponding statistical distributions for M n Φ (G)/n, are given in the table (II.1).

		Graph Size n	200	500	1000	3000	5000
	M n Greedy (G)/n	Mean	0.8904 0.8916 0.8911 0.8897 0.8898
		Std Dev	0.0198 0.0109 0.009 0.0041 0.00311
	M n Minres (G)/n	Mean	0.9356 0.9365 0.9396 0.9378 0.9385
		Std Dev	0.0148 0.0096 0.0052 0.0040 0.0025
		Table II.1: Recap. of Average Matching Size

  Lemma III.2.1. Let a degree sequence {d n = (d n (1), ..., d n (i)); n ∈ N * } and the corresponding point measures {µ n

	III.2. DISCRETE TIME	CHAPTER III. LOCAL
	MARKOV CHAIN	MATCHING ALGORITHMS
		AS MARKOV PROCESSES

  Order for the availability of nodes). Let {µ n ; n ∈ N * } be a sequence of processes satisfying H0. For all k ∈ 0, n , let K µ n k and K ′

	III.2. DISCRETE TIME	CHAPTER III. LOCAL
	MARKOV CHAIN	MATCHING ALGORITHMS
				AS MARKOV PROCESSES
	and we conclude the proof by letting ϵ be arbitrarily small.	■
	Proposition III.2.3 (µ n
				In
	any case we get that
	lim sup n→∞	(d n max ) 2 n	< ϵ,

a contradiction to (III.20). Therefore (d n max ) 2 n is either upper-bounded by ϵ or M/n.

  table (II.1).

	IV.2. PROOF OF THE MAIN				CHAPTER IV. PERFOR-
	CONVERGENCE THEOREM			MANCE PREDICTION AND
					CONCENTRATION RESULTS
		Graph Size n	200	500	1000	3000	5000	M Φ (δ 3 , δ 3 )
	Mn greedy (G)	Mean	0.8904 0.8916 0.8911 0.8897 0.8898	0.8902
		Std Dev	0.0198 0.0109 0.009 0.0041 0.00311
	Mn minres (G)	Mean	0.9356 0.9365 0.9396 0.9378 0.9385	0.9378
		Std Dev	0.0148 0.0096 0.0052 0.0040 0.0025
	Table IV.1: Recap. of Average Matching Size updated with predictions
	Thus, having heuristically confirmed the predictions of the main theorem, we dedicate

  |⟪M f,n ⟫ Tn -⟪M f,n ⟫ Sn | > ϵ III.27) yields that both E(K) < M and E(K ′ ) < M . We follow with

	IV.2. PROOF OF THE MAIN		CHAPTER IV. PERFOR-
	CONVERGENCE THEOREM		MANCE PREDICTION AND
			CONCENTRATION RESULTS
	(|V f,n Tn -V f,n Sn | =	Tn	E μn s (⟨ϑμ n s , f ⟩)ds ≤ δ∥f ∥(2 + 4M ). (IV.19)
		Sn
	Thus,
				17)
	But, under H0 (III.21) is verified, and since max d n = o( √	n) and T n -S n ≤ δ, it
	follows that
	P n -→ 0.	(IV.18)
	On the other hand, since Φ preserves the first moments and we are under H0 ,

  3. ILLUSTRATIVE EXAM-PLE : greedy CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS that 2z({i + 1})z({i}) ≤ z({i + 1}) 2 + z({i}) 2 , we write The first majoration is ended considering that |E x,y | ≤ 2M β + M 2 β 2 + M β :

	Γ ′ 1 ≤	1 2	E x,y	i	i α (i + 1)z({i + 1}) 2 +	1 2	E x,y	i	i α (i + 1)z({i}) 2	(IV.43)
	-	i	i α 1 + i(E x,y +	m x M x	) z({i}) 2
	≤ E x,y	i	i α+1 z({i}) 2 +	1 2	E x,y	i	i α z({i}) 2 -	i	i α z({i}) 2 -(E x,y +	m x M x	)	i	i α+1 z({i}) 2
	≤	1 2	E x,y	i	i α z({i}) 2 -

i i α z({i}) 2 .

  z i iy i ≤ M Γ 1/2 . (IV.50)

	IV.3. ILLUSTRATIVE EXAM-	CHAPTER IV. PERFOR-
	PLE : greedy	MANCE PREDICTION AND
		CONCENTRATION RESULTS
	So that
	(i + 1) 2 i α y 2 i+1 ≤
	i
	We obtain
	i α z i (i + 1)y i+1 ≤ M Γ 1/2	(IV.49)
	i
	The same argument yields
		1/2
	1/2	(i + 1) 2 i α y({i + 1}) 2
	i
		2
		,

.

But i (i + 1) 2 i α y({i + 1}) 2 ≤ i (i + 1)i α/2 y i+1 i i 1+α/2 y i ≤ M. i i α

Referring to the Monte Carlo Casino, where Ulam's uncle would gamble.

In the competitive ratio sense

We are very grateful to Ms Olvera-Cravioto for her ideas on the subject

given the chosen criterion

see Introduction/I.2.2

By leaf, it is meant a degree one node

Graphicality of degree sequence has been extensively studied in the literature, we quickly present a characterization result and a drawing procedure in appendix A.1.4

Konig's theorem states that regular graphs can in fact be viewed as a union of p perfect matchings, thus the margin of error can be approximately known at each step

Second neighbors are simply neighbors of neighbors

By amplitude, we mean the number of half-edges created per iteration

For μ ∈ M, take μn = i≤n ⌈nµ({i})⌉ n δ i

In reality, K and K have the same law

Recall that K and K ′ are the degrees of the vertices picked as extremities of the edge added to the matching

C-tight means the sub-sequential limits are continuous in time

Our code for general/bipartite matching algorithms is available upon request

Acknowledgements

Dedication

To all the dearly beloved, lost. You will always be missed. MANCE PREDICTION AND CONCENTRATION RESULTS

We quantify the error when replacing the real dynamic by the alternative one.

First, let us define the following event in the alternate construction, T (µ) = The buckets I, I ′ , B 1 , ..., B K-1 , B ′ 1 , ..., B ′ K ′ -1 are all distinct .

The event T simply means the local neighborhood under study is tree-like. We deduce the following result :

Lemma IV.2.3. For all µ ∈ M F (N) having finite third moment, we have that

Proof. The event T (µ) c is included in

Consequently,

MANCE PREDICTION AND CONCENTRATION RESULTS

Because the B j 's have the same law, we deduce that

But, for the first term, for all k ≥ 2 conditioning on the size of B 1 , it follows that

Likewise, for the second term, for all k ′ ≥ 3 we obtain that

For the final term, observe that

Then, for all k ≥ 2, k ′ ≥ 2 and d ≥ 1 we get that

⟨µ, χ⟩ , PLE : greedy

CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

For the moment preservation property, assume that Π f (µ n ) → Π f (µ) and that ⟨µ, χ p ⟩ ≤ M , we can write for any positive K

Using the weak convergence and the boundedness of ⟨µ, χ p ⟩, the right hand side can be as small as we wish and we can conclude that the uniform choice function conserves the moments up to order p.

Thus, the first uniform choice Φ greedy K (µ) conserves conserves all the moments of µ. Next, we will apply the same argument to the size biaised of version µ. Recall the size biaised version is written ⟨μ, f ⟩ = ⟨µ, χf ⟩ ⟨µ, χ⟩ .

Since the moments of µ are preserved to order p, it follows that Φ greedy K ′ (µ) preserves the moments of the size biaised version of µ up to p -1.

■

Before proceeding to the next step, we enounce the asymptotic version of Proposition III.2.2, which means the moments of the greedy dynamic stay non increasing.

Corollary IV.3.1 (Boundedness of moments). Let μ. a solution characterized by a generator L with initial distribution ν ∈ M. If for some p > 1 and some M > 0, ⟨ν, χ p ⟩ < M then for all t ≤ 1, ⟨μ t , χ p-1 ⟩ is non increasing. In particular, ⟨μ t , χ p-1 ⟩ < M .

Proof. The proof is immediate by noticing that the function t → LΠ χ p-1 (μ t ), which is the derivative of the p -1th moment is well defined and negative. ■

We can now prove that the operator given by the greedy criterion characterizes the solution of the induced ODE.

IV.3.2 Proof of Theorem IV.3.1: Characterization of the solutions

For this section, assume ν ∈ M is an initial degree distribution with ⟨ν, χ 3.5 ⟩ < M . Using corollary IV.3.1, for any solution μ. , we observe that sup

Lemma IV.3.2 (Uniqueness of the solution characterized by L). Let x . and y . two solutions under the greedy criterion, and characterized by the generator L with x 0 = y 0 = ν. Then, for all t ≤ 1 we have that x t = y t . PLE : greedy

CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

Proof. The proof is split in two parts. We first get rid of the obvious case. When ⟨x 0 , 1 N * ⟩ = ⟨y 0 , 1 N * ⟩ = 0, then LΠ f (x 0 ) = LΠ f (y 0 ). It follows that the solutions are both constant, namely x t = y t = ν for all t.

Else, given β > 0 small, both ⟨x t , 1 N * ⟩ and ⟨y t , 1 N * ⟩ are non increasing in t, hence we define

and we show that any solution is unique for t ≤ T β . Then, we set

and, for some α > 3.5,

We will show that

Using Gronwall's lemma, this would imply that

But Γ(0) = 0 because of the same initial conditions for x . and y . , so this would imply that Γ t = 0 for all 0 ≤ t ≤ T β , which would immediately imply in turn that z t = 0 for all such t, and thereby conclude the proof of uniqueness until T β .

So we are rendered to show (IV.36). For notational simplicity, we drop the dependency in time for all processes. Moreover, for any measure µ, we introduce the following :

The proof amounts to upper-bounding

. PLE : greedy

CHAPTER IV. PERFOR-MANCE PREDICTION AND CONCENTRATION RESULTS

function is the same as that of greedy :

As for the second choice function Φ minres K ′

(µ), it is obtained by taking the minimum of K -1 iid degrees each following the size biaised degree distribution. We write :

And then,

Restricting the space to M Φ minres makes this sum finite and well behavedness (and moment conservation) ensues by the same continuity argument we used for greedy.

The complicated part for most criteria is uniqueness. Although it is suggested by the simulations, we were only able to prove it in trivial cases, or by severely restricting the space of measures under consideration. The authors are currently working on a paper expanding the proof of the uniqueness for other choice functions such as minres.

Appendix A Appendix A.1 The Configuration Model and Degree Sequences

The goal of this section is a brief presentation of the configuration model and a survey of its relevant properties to local matching. We include it for the sake of completeness, although we refer the interested reader to [START_REF] Newman | Networks[END_REF] or van der Hofstad [2016] for more thorough presentations of both its theoretical properties and its practical uses.

Let d := (d(1), ..., d(n)) be a degree sequence associated to a graph (V, E) and let µ := n 1 δ d(i) be its representation as a measure on M F (N). The configuration model is the construction of a (multi-)graph with degree sequence d through the uniform pairing procedure. Any vertex v is given a number of half-edges (also called stubs) equivalent to its degree d(v). So that

is the number of nodes.

is the number of half-edges. The construction of the graph is then done through pairing uniformly stubs into edges. It is immediate that any given configuration is also a representation of a (multi-)graph. Thus, the configuration model can in fact also be viewed as an uniform drawing of a given graph weighted by the number of underlying configurations representing it. Take n buckets of stubs, which sizes are d(1), ..., d(n). At first, the stubs are said to be 'available'.

A.1.1 Algorithmic Construction of a Configuration

Pick a first bucket/node i k between 1, N k , Pair one by one each of the remaining d k (i k ) stubs of i k by sequentially choosing another stub uniformly at random between remaining available half-edges. Set as d k+1 (j) the amount of remaining stubs for the j-th node after pairing, and as N k+1 the number of nodes with remaining stubs. k + 1 → k. end while A.1.2 The CM as an approximation for large simple graphs

Here we provide two propositions that justify the use of the CM as a model for large networks. TION MODEL AND DEGREE SEQUENCES APPENDIX A. APPENDIX Although the underlying configurations are uniformly drawn on the CM, the same can not be said of the resulting graphs. For example, when there are parallel edges, swapping their ending stubs gives rise to different equiprobable configurations while the generated graph is the same. Hence, the same graph would have more weight than any other simple graph (generated by a single configuration). This flaw can be circumvented by noticing that, conditioned on producing a simple graph, the configuration model is an uniform drawing (For example Proposition 7.4 in van der Hofstad [2016]).

Proposition A.1.1 (The CM is a uniform drawing when conditioned to produce simple graphs). Let G a multi-graph with adjacency matrix A and degree distribution d = (d(1), ..., d(n)) (and µ the associated measure). The probability for the CM to produce any given graph

When we restrict the graphs produced to be simple, this probability becomes a uniform drawing on simple graphs G ;

• This property is powerful on its own, but it remains conditional. To justify the use of the CM as an approximation for real networks, we have to complement it with yet another property that guarantees the happening of the condition.

Proposition A.1.2 (CM and simple graphs). Let G a multi-graph with adjacency matrix A and degree distribution d = (d(1), ..., d(n)) (and µ the associated measure). Let ν = ⟨µ,χ 2 -χ⟩ ⟨µ,χ⟩ , we have:

Both those propositions in conjunction ensure that the CM can be conditioned to mimic simple graphs. Afterwards, the graph produced is uniformly drawn.

A.1.3 The Independence Property

In this section, we explore the central property that allows us to build matching algorithms on the configuration. On the CM, the order in which we explore the edges (for example the first edges/nodes in the algorithm) does not influence the final law of the CM.

Proposition A. 1.3 (Independence Property). Recall that m is the set of stubs. The order in which the stubs are completed into edges does not influence the final law of the configuration model. In particular, edges can be created in any order regardless of the vertex they come from as long as the uniform pairing procedure is conserved.

Proof. Let o be an arbitrary reordering of m. We show that any configuration c built using the sequential uniform pairing is uniformly drawn.

For this, notice that c(o( 1)) is still chosen among M -1 other stubs. Then c(o( 2)) is chosen among M -3 choices and so on. All in all, the process still produces (M µ -1)!! configurations which have the same uniform probability 1Mµ-1 . ■

It is also said the uniform pairing process is exchangeable. Exchangeability allows us to build the exact number of edges needed at each step without influencing the macroscopic properties of the CM. Moreover these edges can be built in any order. Effectively, this means that the order in which the graph is built/explored does not bear any influence on its law.

At last, we provide one last macroscopic property of the configuration model which is abundantly used throughout our work Proposition A. 1.4 (Neighboring Degree Distribution). Pick a random node I, the neighbor degree distribution is the degree distribution of a neighbor I ′ . We will call this distribution p µ :

It is a uniform law on all nodes size-biaised by their available stubs oftentimes we simply denote it μ.

Proof. There are kµ(k) -1 d(I)=k stubs coming from degree k nodes over ⟨µ, χ⟩ -1 total stubs to be matched. The distribution above is a reasonable approximation when the number of nodes is large. ■

A.1.4 Graphicality of degree sequences

So far, we have assumed that the sequences of degrees used are graphic, meaning they represent the degrees of a graph. One way to have graphic sequences is to directly take the degrees of a given network. For example, this will be the case for the networks under our study or for surveyed networks. However, one legitimate question to ask when simulating networks is how do to produce graphic sequences (for example from a given probability distribution). In this section, we provide the main characterization result for graphic sequences discovered by Erdos and Gallai which is used to construct graphical sequences. 1)

This test is used on randomly generated degree sequence. Mostly, when the sequence is close to a graphical sequencce, it is 'truncated'. Furthermore, this approach to testing can be perfected using a generalization of the Erdos-Gallai theorem.

Theorem A.1.2 (Aigner and Triesch on the characterization of graphic number sequences).

A finite sequences of nonnegative integers (d( 1), In some contexts such as the truncation of degree sequences, this second result is simpler to use. The idea is to generate a random sequence of numbers (following a given distribution) and then to lower degrees until it becomes graphic.

A.2 Tools for the convergence of processes

This section of the annex is dedicated to the tools used in proving the convergence of processes. Most of the results are stated without proof and can be found in Parthasarathy's book [START_REF] Parthasarathy | Ii -probability measures in a metric space[END_REF]. Again for the sake of completeness, we give structural properties of M F (N) 1 as a reminder.

A.2.1 Topological Properties

Most of our work pertains to subspaces of M F (N). To allege notations, we will only refer to it space as M F . First, we introduce the topologies under study. Since C c (R) ⊂ C b (R), it is immediate that the weak topology is stronger than the vague topology.

Proposition A.2.1. When endowed with the weak topology M F is not separable, while

This proposition is the reason the vague topology is used. Separable spaces are more convenient to use when proving convergence. Moreover, as will be shown hereafter, the weak convergence can easily follow from a vague convergence under sufficent restrictions.

We state yet another important result pertaining to the characterisation of sequences.

Theorem A.2.1 (Prohorov). Let Π be a family of probability measures on a measured space (S, S). If Π is tight, then it is relatively compact Usually, Prohorov's theorem is stated as an equivalence. Here we only state one side of the equivalence since the sufficiency is conditional to completeness and separability.

A.2.2 Characterizing Convergence

We remind the reader that the measures are considered on the Borel sigma algebra. Any time a measure is mentioned on some space E, it is considered on (E, B(E)) where B(E) the sigma algebra generated by the topological open sets. Let D((0, T ), M F ) (resp.C((0, T ), M F ) be the space of right continuous, limited on the left functions (resp. continuous) from (0, T ) to M F endowed with the Skorokhod topology.

The main result of this thesis is a convergence proof for the law of sequence of processes D((0, T ), M F ). Essentially, it boils down to establishing relative compactness (the existence of several sub sequential limits) followed by the identification of the sub sequential limits as one and only process.

Relative compactness of the laws is proven via tightness using Prohorov's theorem. First, vague tightness is proven then it is extended to the weak topology. The following theorem characterizes weak convergence in terms of vague convergence : With this convergence result, we can prove the simpler vague tightness and then generalize it. To do so, we are provided with the following tightness criteria: Theorem A.2.3 (Roelly's tightness criteria [START_REF] Roelly-Coppoletta | A criterion of convergence of measure-valued processes: application to measure branching processes[END_REF]). Let This tightness criteria makes use of the separability of C c (R) and by extension of that of (M F , τ v ) (See [START_REF] Roelly-Coppoletta | A criterion of convergence of measure-valued processes: application to measure branching processes[END_REF]). Thus, it forces us to characterize vague convergence first.

As for the identification of the limit, most of the techniques used are pretty straightforward and directly detailed in the manuscript.