
arXiv: 1610.03873
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\ge 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 that 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.
Extremal problems in graph theory, Extremal graph theory, extremal graph theory, Integer programming, Hypergraphs, facets, \(n\)-dimensional polytopes, Turán, Optimization and Control (math.OC), polytope, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Optimization and Control
Extremal problems in graph theory, Extremal graph theory, extremal graph theory, Integer programming, Hypergraphs, facets, \(n\)-dimensional polytopes, Turán, Optimization and Control (math.OC), polytope, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics - Optimization and Control
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
