Login
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:
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback