Colloquia, Seminars, and Conferences
Monday, April 20th, 2015 at 11 AM, NS 333
(Refreshments afterwards in room 334)
"Monochromatic cycle partitions"
Abstract: Say that a graph G has property L if in every 2-coloring of the edges, there exists a red cycle C1 and a blue cycle C2 having the property that C1 and C2 are vertex disjoint and the union of their vertex sets is equal to the vertex set of G (for simplicity, we allow for cycles on 1 and 2 vertices). Which graphs on n vertices have property L? Does there exist any graph on n vertices with property L?
Lehel conjectured that for all n, the complete graph on n vertices has property L. Over the next 30 years there were many partial results ultimately leading to a proof by Bessy and Thomasse in 2009. In this talk, we will explore various strengthenings of Lehel's conjecture. That is, we will see some sufficient conditions and some necessary conditions for G to have property L. Along the way, we will discuss the regularity-blow-up method, the absorbing method, expanders, and (pseudo)random graphs.
Based on joint work with Deepak Bal and Luke Nelsen.
The following research seminars meet weekly in the Natural Sciences Building. Everyone is welcome to attend. For more information, please contact corresponding coordinators.
Louisville, Department of Mathematics. Copyright 2006. All rights
Comments to mailto:firstname.lastname@example.org. |