Linkage involves finding a set of internally disjoint paths in a graph with specified endpoints. Given graphs G and H, we say G is H-linked if for every injective mapping f:V(H) -> V(G) we can find a subgraph H' of G which is a subdivision of H, with f(v) being the vertex of H' corresponding to each vertex v of H. We describe two results on H-linkage for small graphs H.
(1) Goddard showed that 4-connected planar triangulations are 4-ordered, or in other words C_4-linked. We strengthen this by showing that 4-connected planar triangulations are (K_4-e)-linked.
(2) Xingxing Yu characterized certain graphs related to P_4-linkage. We use his characterization to show that every 7-connected graph is P_4-linked, and to construct 6-connected graphs that are not P_4-linked.
This is joint work with Michael D. Plummer and Gexin Yu.
Stability methods are often used in extremal graph theory, Ramsey theory and similar areas, where an extremal problem is to be solved and
- we have a conjecture about the structure of the conjectured extremal configurations and according to our conjecture, it has some given property \mathcal P;
- we can prove that all the almost extremal structures are near to the property \mathcal P, in some sense;
- if we knew that if a structure is near to the property \mathcal P and is extremal, then it is already the conjectured structure.
Of course, stability methods can also be used in other cases, but we restrict ourselves to the above two areas.
In my lecture I will give an introduction to the applications of the stability methods in extremal graph theory, describe cases in extremal graph theory, extremal hypergraph theory, in the Erdos-Frankl-Rold (= generalized Erdos-Kleitman-Rothschild theory) ...
In the second part of my lecture I shall describe the application of this method to the Erdos-Sos conjecture. This is part of our work with Ajtai, Komlos and Szemeredi.
This is joint work with Dr. Yi Zhao.