Combinatorics Seminar

When: Sunday, December 30, 10am
Where: Schreiber 309
Speaker: Noga Alon, Princeton University/Tel Aviv University
Title: Product dimension and Sperner Capacity

Abstract:

The product dimension of a graph $G$ is the minimum possible number of proper vertex colorings of $G$ so that for every pair $u,v$ of non-adjacent vertices there is at least one coloring in which $u$ and $v$ have the same color. What is the product dimension $q(r,s)$ of the vertex disjoint union of $r$ cliques, each of size $s$? Lovász, Nešetřil and Pultr proved in the 70s that for $s=2$ it is $(1+o(1))\log_2r$ and asked what happens for larger values of $s$. The same problem arises in recent work of Kleinberg and Weinberg about prophet inequalities for intersection of matroids. We show that for every fixed $s$, as $r$ grows the answer is still $(1+o(1))\log_2r$, but the problem of determining the asymptotic behaviour of $q(r,s)$ when $s$ and $r$ grow together remains open. The proof combines linear algebra tools with the ideas of Gargano, Körner and Vaccaro on Sperner capacities of directed graphs.

Joint work with Ryan Alweiss.