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.
Gratuit
Disciplines