Subgraphs of Oriented Graphs
|
Tue, 14/10/2008 16:00 |
Simon Griffiths (Cambridge) |
Combinatorial Theory Seminar  |
L3 |
| How can one guarantee the presence of an oriented four-cycle in an oriented graph G? We shall see, that one way in which this can be done, is to demand that G contains no large `biased. subgraphs; where a `biased. subgraph simply means a subgraph whose orientation exhibits a strong bias in one direction. Furthermore, we discuss the concept of biased subgraphs from another standpoint, asking: how can an oriented graph best avoid containing large biased subgraphs? Do random oriented graphs give the best examples? The talk is partially based on joint work with Omid Amini and Florian Huc. | |||