Un graphe est un ensemble de noeuds, ensemble de liens reliant des paires de noeuds. Avec la quantité accumulée de données collectées, il existe un intérêt croissant pour la compréhension des structures et du comportement de très grands graphes. Néanmoins, l’augmentation rapide de la taille des grands graphes rend l’étude de tous les graphes de moins en moins efficace. Ainsi, il existe une demande impérieuse pour des méthodes plus efficaces pour étudier de grands graphes sans nécessiter la connaissance de tous les graphes. Une méthode prometteuse pour comprendre le comportement de grands graphes consiste à exploiter des propriétés spécifiques de structures locales, telles que la taille des grappes ou la présence locale d’un motif spécifique, c’est-à-dire un graphe donné (généralement petit). Un exemple classique de la théorie des graphes (cas avérés de la conjecture d'Erdos-Hajnal) est que, si un graphe de grande taille ne contient pas de motif spécifique, il doit alors avoir un ensemble de noeuds liés par paires ou non liés, de taille exponentiellement plus grande que prévue. Cette thèse abordera certains aspects de deux questions fondamentales de la théorie des graphes concernant la présence, en abondance ou à peine, d’un motif donné dans un grand graphe : - Le grand graphe peut-il être partitionné en copies du motif ? - Le grand graphe contient-il une copie du motif ? Nous discuterons de certaines des conjectures les plus connues de la théorie des graphes sur ce sujet: les conjectures de Tutte sur les flots dans les graphes et la conjecture d'Erdos-Hajnal mentionnée ci-dessus, et présenterons des preuves pour plusieurs conjectures connexes - y compris la conjecture de Barát-Thomassen, une conjecture de Haggkvist et Krissell, un cas particulier de la conjecture de Jaeger-Linial-Payan-Tarsi, une conjecture de Berger et al, et une autre d'Albouker et al. / A graph is a set of nodes, together links connecting pairs of nodes. With the accumulating amount of data collected, there is a growing interest in understanding the structures and behavior of very large graphs. Nevertheless, the rapid increasing in size of large graphs makes studying the entire graphs becomes less and less efficient. Thus, there is a compelling demand for more effective methods to study large graphs without requiring the knowledge of the graphs in whole. One promising method to understand the behavior of large graphs is via exploiting specific properties of local structures, such as the size of clusters or the presence locally of some specific pattern, i.e. a given (usually small) graph. A classical example from Graph Theory (proven cases of the Erdos-Hajnal conjecture) is that if a large graph does not contain some specific pattern, then it must have a set of nodes pairwise linked or not linked of size exponentially larger than expected. This thesis will address some aspects of two fundamental questions in Graph Theory about the presence, abundantly or scarcely, of a given pattern in some large graph: - Can the large graph be partitioned into copies of the pattern? - Does the large graph contain any copy of the pattern?We will discuss some of the most well-known conjectures in Graph Theory on this topic: the Tutte's flow conjectures on flows in graphs and the Erdos-Hajnal conjecture mentioned above, and present proofs for several related conjectures -- including the Barát-Thomassen conjecture, a conjecture of Haggkvist and Krissell, a special case of Jaeger-Linial-Payan-Tarsi's conjecture, a conjecture of Berger et al, and another one by Albouker et al.

Cette thèse se concentre sur trois aspects très différents de l'éducation mais qui affectent chacun la qualité de son offre. Dans le premier chapitre, nous étudions le comportement stratégique adopté à la fois par l'université et par les professeurs, afin pour les uns d'attirer les meilleurs universitaires et pour les autres d'accéder aux meilleures positions, en faisant un compromis entre salaires élevés, sécurité de l'emploi et possibilités de mobilité ascendante. Dans un deuxième chapitre, nous étudions comment la répartition des revenus dans les districts scolaires affecte la qualité des écoles publiques, par la voie des votes locaux et de la fiscalité. En effet, un district scolaire avec une polarisation de revenu plus élevée conduit à un vote pour une faible taxation et donc de plus basses dépenses pour l'école publique impliquant une moins bonne qualité de cette dernière. Enfin, dans un dernier chapitre, nous montrons que les attentes des garçons et des filles concernant leurs futures carrières ainsi que les antécédents scolaires sont façonnés par des stéréotypes de genre. Par exemple, le stéréotype selon lequel les hommes sont meilleurs en mathématiques crée un stéréotype négatif sur les aptitudes des filles en mathématiques. Les stéréotypes représentent l'explication principale dans les différences entre les garçons et les filles en matière de confiance en soi et ont des conséquences importantes sur les chemins qu'ils suivent tout au long de leur vie. / This thesis focuses on three very different aspects of education but which all affect in their way the quality of its provision.In the first chapter, we investigate the strategic behavior adopted by both the university and the professors, in order, for the first to attract the best academics, and for the second to access the best positions making a trade-off between high salaries, job security and upward mobility possibilities. We question the efficiency of such system in attracting, but also in keeping, the best academics. In a second chapter, we investigate how the income distribution of school districts affects the quality of public schools through the channel of local votes and taxation. In fact, an income polarized school district (more poor and rich at the expense of the middle class) leads to a vote for low taxation and thus low expenditure toward public school and a poorest quality of school. The mechanism being that the richest households send their children to private schools and thus are not concerned by public school quality while poorest households can not afford a too high taxation.Finally, in a last chapter we show how boys' and girls' career expectations and educational background are shaped by gender stereotypes. For instance, the stereotype that men are better at mathematics creates a negative stereotype on girls aptitudes in mathematics. Stereotypes represent the main explanation in boys and girls differences in self-confidence, and have important consequences on the paths they take throughout their lives.