Qualifying Exam

Speaker:  Pablo Castilla, University of Kentucky

Title:  Understanding the Túran polytope with cutting planes

Abstract:

For a 3-regular hypergraph with n vertices, what is the most number of edges it can have without having a 4-clique as a subgraph? Túran posed this problem in 1941 and constructed what he conjectured was optimal, but to date the question remains open. 

While it has had great deal of attention combinatorially, recently Raymond has taken a polytopal approach, formulating the problem as an integer linear program. The convex hull of the admissible hypergraphs, known as the Túran polytope, is combinatorially interesting in its own right, having many correspondences with the stable set polytope. 

We propose to further understand the Túran polytope using cutting planes, a technique from integer linear programming. By observing cutting plane algorithms applied by software to solve the integer program, we can discover more of the Túran polytope’s facet structure and make progress on proving Túran’s conjecture.