Daniel Zhu, Princeton University

Abstract

What is the smallest subset of the hypercube {0, 1}^n that intersects every two-dimensional face? What is the largest subgraph of the hypercube graph Q_n that doesn't contain an 8-cycle? These questions are all examples of Turán problems on the hypercube, where we seek the minimum size of a subset (of either vertices and edges) of the hypercube that guarantees the existence of a certain structure. We discuss a framework for tackling such questions and some unexpected connections to structural graph theory and matroids.