Date:
Mon, 28/04/202511:00-13:00
Location:
Ross 70
Title: Turan densities for hypercubes and daisies, and related problems.
Abstract: The vertex-Turan problem for hypercubes asks: how small a family of vertices F can we take in {0,1}^n, in such a way that F intersects the vertex-set of every d-dimensional subcube? A widely-believed folklore conjecture stated that the minimal measure of such a family is (asymptotically) 1/(d+1), which is attained by taking every (d+1)th layer of the cube. (This was proven in the special case d=2 by Kostochka in 1976, and independently by Johnson and Entringer.) In this talk, we will outline a construction of such a family F with measure at most c^d for an absolute constant c<1, disproving the folklore conjecture in a strong sense. We will explain the connection to Turan questions for 'daisies', and discuss various other widely-believed conjectures, e.g. on forbidden posets, that can be seen to fail due to our construction. Several open problems remain, including the optimal value of c above. Based on joint work with Maria-Romina Ivan and Imre Leader.
Abstract: The vertex-Turan problem for hypercubes asks: how small a family of vertices F can we take in {0,1}^n, in such a way that F intersects the vertex-set of every d-dimensional subcube? A widely-believed folklore conjecture stated that the minimal measure of such a family is (asymptotically) 1/(d+1), which is attained by taking every (d+1)th layer of the cube. (This was proven in the special case d=2 by Kostochka in 1976, and independently by Johnson and Entringer.) In this talk, we will outline a construction of such a family F with measure at most c^d for an absolute constant c<1, disproving the folklore conjecture in a strong sense. We will explain the connection to Turan questions for 'daisies', and discuss various other widely-believed conjectures, e.g. on forbidden posets, that can be seen to fail due to our construction. Several open problems remain, including the optimal value of c above. Based on joint work with Maria-Romina Ivan and Imre Leader.