Title : Turan problems on the hypercube
Speaker : David Offner
When : 4:30-5:30pm, March 29th
Where : PPB 300
Abstract: Turan’s theorem gives the number of edges possible in an n-vertex graph with no k-clique. Since this result was proved in 1941, numerous generalizatons and variations have been studied. In this talk, we survey some conjectures, problems and results on Turan-type problems where the base graph is a hypercube.
In particular, we define c_d to be the minimum proportion of the edges which must be removed from any hypercube so that it does not contain a d-dimensional subcube as a subgraph, and p_d to be the maximum number of colors with which one can color the edges of any hypercube such that any d-dimensional subcube contains every color. Note c_d < 1/p_d.
We prove the exact value of p_d for every d, and present some observations about c_d.
Includes joint work with Oleg Pikhurko.
