The ACO Seminar (2016–2017)

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.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.