Algorithms, Combinatorics and Optimization Seminar David Offner
Carnegie Melllon University and Westminster College
Title: Polychromatic Colorings on Hypercubes, Complete Graphs, and Integers

Abstract: Given a set S, and a set T of subsets of S, a coloring of the elements of S is called T-polychromatic if every set in T contains an element of every color. Let poly_T(S) be the largest n for which there is a T-polychromatic coloring of S with n colors. This talk introduces theorems and open problems on the value of poly_T(S) in three settings:

• S is the set of edges of a hypercube, and T is the set of all subgraphs isomorphic to a given graph H.
• S is the set of edges of a complete graph, and T is the set of all spanning subgraphs of a given degree.
• S is the set of integers, and T is the set of translates of a given finite set.

Date: Thursday, December 8, 2016
Time: 3:30 pm
Location: Wean Hall 8220