Talks & Seminars

Title: A Ramsey-type Theorem in the Hypercube |

Prof. John Goldwasser, West Virginia University |

Date & Time: August 17, 2010 15:00 |

Venue: Seminar Hall, Old CSE building |

Abstract: We think of the vertices of the n-cube Qn as the set of all subsets of {1,2,3,…,n}, with two vertices joined by an edge if and only if one is contained in the other and their sizes differ by one. We say a subset S of the vertices of Qd is t-cube-Ramsey if for sufficiently large n, whenever the vertices of Qn are colored with t colors there must be a monochromatic copy of S embedded in the Qn. If all sets in S have the same size, then it follows immediately from Ramsey’s theorem that S is t-cube-Ramsey. In general it is quite difficult to determine if a set S is t-cube-Ramsey. A clique in Qd is the set of all subsets of a given size of a fixed subset of {1,2,…,d}. We determine which sets S which are the union of two or three disjoint cliques in Qd are 2-cube-Ramsey. We use the Lovasz Local Lemma and a probabilistic argument to show that no set which is the union of at least 36 disjoint cliques can be 2-cube-Ramsey. We say a t-coloring of the vertices of Qd is layered if all the vertices of the same size get the same color. A key ingredient in our proofs is the following: For each positive integer d, there exists a positive integer N such that for each n greater than N, in every t-coloring of the vertices of Qn there is an embedded copy of Qd with a layered coloring. (With John Talbot, University College, London) |

Speaker Profile: |

# Webmail

# Quick Links

**Open Letter to Companies seeking to recruit CSE graduates**- Sysads/Systems Portal
- IITB mail
- Current Courses
- Time Table
- Department Wiki
- Projects And Resources
- Research Labs
- CSE Departmental Talks
- Faculty Unplugged Seminar Series (FUSS)
- Department Space Inventory
- Telephone Directory
- Join as a Faculty
- people@cse
- FAQ Sitemap