Estudamos o problema de famílias intersectantes extremais em um subconjunto aleatório da família dos subconjuntos com exatamente k elementos de um conjunto dado. Obtivemos uma descrição quase completa da evolução do tamanho de tais famílias. Versões semelhantes do problema foram estudadas por Balogh, Bohman e Mubayi em 2009, e por Hamm e Kahn, e Balogh, Das, Delcourt, Liu e Sharifzadeh de maneira concorrente a este trabalho. / We studied the problem of maximal intersecting families in a random subset of the family of subsets with exactly k elements from a given set. We obtained a nearly complete description of the evolution of the size of such families. Similar versions of this problem have been studied by Balogh, Bohman and Mubayi in 2009, and by Hamm and Kahn, and Balogh, Das, Delcourt, Liu and Sharifzadeh concurrently with this work.

We consider a general preferential attachment model, where the probability that a newly arriving vertex connects to an older vertex is proportional to a (sub-)linear function of the indegree of the older vertex at that time. We provide a limit theorem with rates of convergence for the distribution of a vertex, chosen uniformly at random, as the number of vertices tends to infinity. To do so, we develop Stein's method for a new class of limting distributions including power-laws. Similar, but slightly weaker results are shown to be deducible using coupling techniques. Concentrating on a specific preferential attachment model we also show that the outdegree distribution asymptotically follows a Poisson law. In addition, we deduce a central limit theorem for the number of isolated vertices. We thereto construct a size-bias coupling which in combination with Stein’s method also yields bounds on the distributional distance.

Real systems are often represented by so-called complex networks. These networks have a specific connectivity structure given by the specifics of the studied systems. Since often insufficient or inaccurate data are available, a common approach is to model these systems at the level of this connectivity using random networks replicating specific prop- erties such as ease of connectivity, modularity or specific sparsity. The representation of these properties in basic complex network models is a widely explored area. However, if the presence of edges is controlled by a specific distributions or if an element of the dynamics of the overall graph is added to the model, the analysis of such models be- comes more complex. This thesis aims to investigate the properties of such dynamically dependent random models. 1

[pt] Na primeira parte dessa tese, estudamos o desvio no número de triângulos com respeito à média em ambos os modelos de grafos aleatórios G(n,m) e G(n, p). Focamos no caso em que o grafo aleatório é esparso, no qual a densidade de arestas vai para zero quando o número de vértices cresce para o infinito. Nosso foco também reside no caso de desvios moderados, i.e., aqueles cuja ordem está entre o desvio padrão e a média. Além disso, também derivamos o mesmo tipo de resultado para cerejas (caminhos de comprimento dois). Na segunda parte dessa tese, estudamos a desigualdade de Freedman. Essa desigualdade fornece limitantes para a probabilidade de desvio de um martingal limitado usando sua variância condicional. No nosso trabalho, obtemos uma versão mais forte da desigualdade de Freedman, impondo condições adicionais de simetria nos incrementos do processo martingal. / [en] In the first part of this thesis, we study the deviation of the number of triangles with respect to its mean in both the random graph models G(n,m) and G(n, p). We focus on the case where the random graph is sparse, in which the edge density goes to zero as the number of vertices increases to infinity. Also, our focus is in the case of moderate deviations, i.e., those of order in between the standard deviation and the mean. In addition, we derive the same kind of results for cherries (paths of length two). In the second part of this thesis, we study Freedman s inequality. This inequality gives bounds on the probability of the deviation of a bounded martingale using its conditional variance. In our work, we obtain a strengthening of Freedman s inequality, under additional symmetry conditions on the increments of the martingale process.

No description available.

A central problem in neuroscience is to understand how memories are formed as a result of the activities of neurons. Valiant’s neuroidal model attempted to address this question by modeling the brain as a random graph and memories as subgraphs within that graph. However the question of memory capacity within that model has not been explored: how many memories can the brain hold? Valiant introduced the concept of interference between memories as the defining factor for capacity; excessive interference signals the model has reached capacity. Since then, exploration of capacity has been limited, but recent investigations have delved into the capacity of the Assembly Calculus, a derivative of Valiant's Neuroidal model. In this paper, we provide rigorous definitions for capacity and interference and present theoretical formulations for the memory capacity within a finite set, where subsets represent memories. We propose that these results can be adapted to suit both the Neuroidal model and Assembly calculus. Furthermore, we substantiate our claims by providing simulations that validate the theoretical findings. Our study aims to contribute essential insights into the understanding of memory capacity in complex cognitive models, offering potential ideas for applications and extensions to contemporary models of cognition.

Random graph processes are basic mathematical models for large-scale networks evolving over time. Their systematic study was pioneered by Erdös and Rényi around 1960, and one key feature of many 'classical' models is that the edges appear independently. While this makes them amenable to a rigorous analysis, it is desirable, both mathematically and in terms of applications, to understand more complicated situations. In this thesis the main goal is to improve our rigorous understanding of evolving random graphs with significant dependencies. The first model we consider is known as an Achlioptas process: in each step two random edges are chosen, and using a given rule only one of them is selected and added to the evolving graph. Since 2000 a large class of 'complex' rules has eluded a rigorous analysis, and it was widely believed that these could give rise to a striking and unusual phenomenon. Making this explicit, Achlioptas, D'Souza and Spencer conjectured in Science that one such rule yields a very abrupt (discontinuous) percolation phase transition. We disprove this, showing that the transition is in fact continuous for all Achlioptas process. In addition, we give the first rigorous analysis of the more 'complex' rules, proving that certain key statistics are tightly concentrated (i) in the subcritical evolution, and (ii) also later on if an associated system of differential equations has a unique solution. The second model we study is the H-free process, where random edges are added subject to the constraint that they do not complete a copy of some fixed graph H. The most important open question for such 'constrained' processes is due to Erdös, Suen and Winkler: in 1995 they asked what the typical final number of edges is. While Osthus and Taraz answered this in 2000 up to logarithmic factors for a large class of graphs H, more precise bounds are only known for a few special graphs. We close this gap for the cases where a cycle of fixed length is forbidden, determining the final number of edges up to constants. Our result not only establishes several conjectures, it is also the first which answers the more than 15-year old question of Erdös et. al. for a class of forbidden graphs H.

In this work we study two random procedures in cubic graphs with large girth. The first procedure finds a probability distribution on edge-cuts such that each edge is in a randomly chosen cut with probability at least 0.88672. As corollaries, we derive lower bounds for the size of maximum cut in cubic graphs with large girth and in random cubic graphs, and also an upper bound for the fractional cut covering number in cubic graphs with large girth. The second procedure finds a probability distribution on independent sets such that each vertex is in an independent set with probability at least 0.4352. This implies lower bounds for the size of maximum independent set in cubic graphs with large girth and in random cubic graphs, as well as an upper bound for the fractional chromatic number in cubic graphs with large girth.

Cette thèse est consacrée à l'étude du comportement asymptotique de grands graphes et arbres aléatoires. Le premier modèle étudié est un modèle de graphe aléatoire inhomogène introduit par Bo Söderberg. Un chapitre de ce manuscrit est consacré à l'étude asymptotique de la taille des composantes connexes à proximité de la fenêtre critique, en le reliant à la longueur des excursions d'un mouvement brownien avec dérive parabolique, étendant les résultats obtenus par Aldous. Le chapitre suivant est consacré à un processus de graphes aléatoires proposé par Itai Benjamini, défini ainsi : les arêtes sont ajoutées indépendamment, à taux fixe. Lorsqu'un sommet atteint le degré k, toutes les arêtes adjacentes à ce sommet sont immédiatement supprimées. Ce processus n'est pas croissant, ce qui empêche d'utiliser directement certaines approches usuelles. L'utilisation de limites locales permet de montrer la présence (resp. l'absence) d'une composante géante à certaines étapes dans le cas k>=5 (resp. k<=3). Dans le cas k=4, ces résultats permettent de caractériser la présence d'une composante géante en fonction du caractère surcritique ou non d'un processus de branchement associé. Dans le dernier chapitre est étudiée la hauteur d'un arbre de Lyndon associé à un mot de Lyndon choisi uniformément parmi les mots de Lyndon de longueur n, prouvant que cette hauteur est approximativement c ln n, avec c=5,092... la solution d'un problème d'optimisation. Afin d'obtenir ce résultat, nous couplons d'abord l'arbre de Lyndon à un arbre de Yule, que nous étudions ensuite à l'aide de techniques provenant des théories des marches branchantes et des grandes déviations. / This thesis is dedicated to the study of the asymptotic behavior of some large random graphs and trees. First is studied a random graph model introduced by Bo Söderberg in 2002. One chapter of this manuscript is devoted to the study of the asymptotic behavior of the size of the connected components near the critical window, linking it to the lengths of excursion of a Brownian motion with parabolic drift. The next chapter talks about a random graph process suggested by Itai Benjamini, defined as follows: edges are independently added at a fixe rate. Whenever a vertex reaches degree k, all adjacent edges are removed. This process is non-increasing, preventing the use of some commonly used methods. By using local limits, in the spirit of the PWIT, we were able to prove the presence (resp. absence) of a giant component at some stages of the process when k>=5 (resp. k<=3). In the case k=4, these results allows to link the presence (resp. absence) of a giant component to the supercriticality (resp. criticality or subcriticality) of an associated branching process. In the last chapter, the height of random Lyndon tree is studied, and is proven to be approximately c ln n, in which c=5.092... the solution of an optimization problem. To obtain this result, we couple the Lyndon tree with a Yule tree, then studied with the help of branching walks and large deviations

Diese Habilitationsschrift richtete auf zwei diskrete Strukturen aus: planare Strukturen und zufällige Graphen-Prozesse. Zunächst werden zufällige planare Strukturen untersucht, mit folgende Gesichtspunkte: - Wieviele planare Strukturen gibt es? - Wie kann effizient eine zufällige planare Struktur gleichverteilt erzeugt werden? - Welche asymptotischen Eigenschaften hat eine zufällige planare Struktur mit hoher Wahrscheinlichkeit? Um diese Fragen zu beantworten, werden die planaren Strukturen in Teile mit höherer Konnektivität zerlegt. Für die asymptotische Enumeration wird zuerst die Zerlegung als das Gleichungssystem der generierenden Funktionen interpretiert. Auf dem Gleichungssystem wird dann Singularitätenanalyse angewendet. Für die exakte Enumeration und zufällige Erzeugung wird die rekursive Methode verwendet. Für die typischen Eigenschaften wird die probabilistische Methode auf asymptotischer Anzahl angewendet. Des Weiteren werden zufällige Graphen-Prozesse untersucht. Zufällige Graphen wurden zuerst von Erdos und Renyi eingeführt und untersucht weitgehend seitdem. Ein zufälliger Graphen-Prozess ist eine Markov-Kette, deren Zustandsraum eine Menge der Graphen mit einer gegebenen Knotenmenge ist. Der Prozess fängt mit isolierten Konten an, und in jedem Ablaufschritt entsteht ein neuer Graph aus dem aktuellen Graphen durch das Hinzufügen einer neuen Kante entsprechend einer vorgeschriebenen Regel. Typische Fragen sind: - Wie ändert sich die Wahrscheinlichkeit, dass ein von einem zufälligen Graphen-Prozess erzeugter Graph zusammenhängend ist? - Wann erfolgt der Phasenübergang? - Wie groß ist die größte Komponente? In dieser Habilitationsschrift werden diese Fragen über zufällige Graphen-Prozesse mit Gradbeschränkungen beantwortet. Dafür werden probabilistische Methoden, insbesondere Differentialgleichungsmethode, Verzweigungsprozesse, Singularitätsanalyse und Fourier-Transformationen, angewendet. / This thesis focuses on two kinds of discrete structures: planar structures, such as planar graphs and subclasses of them, and random graphs, particularly graphs generated by random processes. We study first planar structures from the following aspects. - How many of them are there (exactly or asymptotically)? - How can we efficiently sample a random instance uniformly at random? - What properties does a random planar structure have, with high probability? To answer these questions we decompose the planar structures along the connectivity. For the asymptotic enumeration we interpret the decomposition in terms of generating functions and derive the asymptotic number, using singularity analysis. For the exact enumeration and the uniform generation we use the recursive method. For typical properties of random planar structures we use the probabilistic method, together with the asymptotic numbers. Next we study random graph processes. Random graphs were first introduced by Erdos and Renyi and studied extensively since. A random graph process is a Markov chain whose stages are graphs on a given vertex set. It starts with an empty graph, and in each step a new graph is obtained from a current graph by adding a new edge according to a prescribed rule. Recently random graph processes with degree restrictions received much attention. In the thesis, we study random graph processes where the minimum degree grows quite quickly with the following questions in mind: - How does the connectedness of a graph generated by a random graph process change as the number of edges increases? - When does the phase transition occur? - How big is the largest component? To investigate the random graph processes we use the probabilistic method, Wormald''s differential equation method, multi-type branching processes, and the singularity analysis.