The Quasi-Randomness of Hypergraph Cut Properties
- Series
- Combinatorics Seminar
- Time
- Friday, March 5, 2010 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Asaf Shapira – School of Mathematics, Georgia Tech
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
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.
Please Note: This is joint work with Dr. Yi Zhao.