***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Ron Holzman (Technion)
Thursday 5th December, 3:00 in Fine Hall 224.
Title: On 2-colored graphs and partitions of boxes
We prove that if the edges of a graph G can be colored blue or red in such
a way that every vertex belongs to a monochromatic k-clique of each color,
then G has at least 4(k-1) vertices. This confirms a conjecture of Bucic,
Lidicky, Long, and Wagner, and thereby solves the 2-dimensional case of their
problem about partitions of discrete boxes with the k-piercing property.
We also characterize the case of equality in our result.
----------------------------------
Next week: Xiaoyu He
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)