Combinatorics Seminar

When: Sunday, June 5, 10am Where: Schreiber 309 Speaker: Robert Johnson, Queen Mary, Univ. of London Title: Intersection graphs of discrete subcubes

Abstract:

Consider the discrete $d$-cube $\{0,1\}^d$ and let $A_1,\dots,A_n$ be subcubes of it (a subcube is a set of points of the cube formed by fixing $k$ coordinates and allowing the remaining $d-k$ to vary freely). We can form the intersection graph of these subcubes by taking vertex set $[n]$ and joining $i$ to $j$ if the subcubes $A_i$ and $A_j$ intersect. In this talk we will describe some questions and results on intersection properties of subcubes which are naturally expressed as Tur\'an and Ramsey type problems in the intersection graph.

The questions are loosely inspired by some issues in social choice theory although our main motivation is that they are mathematically natural.

This is joint work with Klas Markstr\"om (Umea).