2016/10/12 by Annie Raymond, Raymond, Annie
Arts and Humanities · Business, Management and Accounting · Computer Science · Mathematics · #Advanced Graph Theory Research #Archaeology and Historical Studies #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Language, Linguistics, Cultural Analysis #Law, logistics, and international trade #Limits and Structures in Graph Theory #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.1610.03873
openalex publication_date 2016/10/12 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28
The Turán hypergraph problem asks to find the maximum number of r-edges in a r-uniform hypergraph on n vertices that does not contain a clique of size a. When r=2, i.e., for graphs, the answer is well-known and can be found in Turán's theorem. However, when r≥ 3, the problem remains open. We model the problem as an integer program and call the underlying polytope the Turán polytope. We draw parallels between the latter and the stable set polytope: we show that generalized and transformed versions of the web and wheel inequalities are also facet-defining for the Turán polytope. We also show clique inequalities and what we call doubling inequalities are facet-defining when r=2. These facets lead to a simple new polyhedral proof of Turán's theorem.