A recursive theta body for hypergraphs (Q6081405)

Let \(G=(V,E)\) be a (simple) graph. Its theta body \(\text{TH}(G)\) is a compact convex subset of \(\mathbb{R}^{V}\) which contains the independent set polytope \(\text{IND}(G)\) of \(G\), i.e. the convex hull of all characteristic functions of independent sets in \(G\). As an independent set intersects a clique in at most one vertex \(\text{IND}(G)\subseteq QIND(G)=\{f\in \text{IND}(G): f(C)\leq 1\text{ for any clique}\; C\}\). \(\text{TH}(G)\) is defined to be \(\{f\in \mathbb{R}^{V}: \exists F\in \mathbb{R}^{V \times V}\text{ such that }f=\text{diag}(F), F(x,y)=-0 \; \text{if}\; xy\in E \text{ and }R(F)\text{ is positive semidefinite}\}\) where for a symmetric \(n\times n\) matrix \(A\) \(R(A)\) is the symmetric \((n+1)\times (n+1)\) block matrix whose first row is 1 followed by the diagonal of A, with the transpose of that row as the first column and \(R(A)_{ii}=A_{(i-1)(i-1)}\) for \(2\leq i\leq n+1\). We have \(\text{IND}(G)\subseteq \text{TH}(G)\subseteq \text{QIND}(G)\). A key point about \(\text{TH}(G)\) is that, whereas computation in \(\text{IND}(G)\) or \(\text{QIND}(G)\) is known to be difficult, linear functions over \(\text{TH}(G)\) can be maximised in polynomial time. The Lovász theta function \(\theta(G)\), which satisfies the inequalities \(\alpha(G)\leq \theta(G)\leq \chi(\overline{G})\) where \(\overline{G}\) is the complement of \(G\), is \(\max\{ 1^{T}f: f\in \text{TH}(G)\}\): the fact that this can be computed in polynomial time is of importance in approximating the (generically much less tractable) quantities \(\alpha(G)\) and \(\chi(\overline{G})\).\par The aim of the paper under review is to generalise this circle of ideas to \(r\)-uniform hypergraphs \(H=(V,E)\). An independent set is now one that contains no hyperedge and we can then define \(\text{IND}(H)\) as before. The revised definition of \(\text{QIND}(H)\) is the functions whose value on any clique (set where all \(r\)-element subsets are hyperedges) is at most \(r-1\), as now an independent set contains at most \(r-1\) vertices of any hyperedge. For the new definition of \(\text{TH}\), say first that for an \(r\)-uniform hypergraph \(H\) and \(x\in V(H)\) the link is the \((r-1)\)-uniform hypergraph \(H_{x}\) with vertex set \(V_{x}=\{y\in V\backslash \{x\}: \exists e\in E(H) \text{ with }e\supseteq \{x,y\}\) and hyperedges those \(r-1\) element subsets of \(V_{x}\) whose union with \(x\) is a hyperedge of \(H\). For a function \(f\) use \(f[U]\) to mean \(f\) restricted to the subset \(U\) and for a matrix \(A\in \mathbb{R}^{V\times V}\) and \(x\in V\) use \(A_{x}\) to mean the \(x\)th row of \(A\) so that \(A_{x}(y)=a(x,y)\). Now we define \(\text{TH}(H)\) recursively by saying that for \(r=1\) \(\text{TH}(H)=\text{IND}(H)\) and for \(r\geq 2\) \(\text{TH}(H)=\{f: \exists F\in \mathbb{R}^{V\times V} \text{such that}f=\text{diag}(F), F_{x}[V_{x}]\in F(x,x)\text{TH}(H_{x})) \forall x\in X \text{ and }R(F)\text{ is positive semidefinite}\)\}. Here we adopt the convention that if a link \(H_{x}\) is empty no constraint is imposed on the row \(F_{x}\). When \(r=2\) (i.e. the hypergraph is a simple graph) we recover the theta body for a graph as above. Again we have that \(\text{IIND}(H)\subseteq \text{TH}(H)\subseteq \text{QIND}(H)\) and that linear functions over \(\text{TH}(H)\) can be optimised in linear time.\par For graphs, the fractional chromatic number \(\chi_{\text{frac}}(\overline{G})\) of \(\overline{G}\), a relaxation of the integer programme defining \(\chi(\overline{G})\), satisfies \(\alpha(G)\leq \theta(G)\leq \chi_{\text{frac}}(\overline{G})\leq \chi(\overline{G})\). The authors show that a similar result holds for the hypergraph world.\par If \(G\) is a \(d\)-regular graph with smallest (adjacency) eigenvalue \(\lambda\) then we have \(\alpha(G)\leq \theta(G) \leq-n\lambda/(d-\lambda)\) where the rightmost quantity is called the Hoffmann bound. Again the authors show that the hypergraph version \(\theta(H)\) is a better upper bound on the independence number than the hypergraph version of the Hoffmann bound. \par The authors also give an alternative proof of Mantel's theorem (the triangle case of Turán's theorem) using their ideas and give a closed formula for the \(\theta\) number of the 3-uniform hypergraph over the Hamming cube (hypercube) whose hyperedges are three vertices of the Hamming cube, each pair at the same Hamming distance, thus bounding above the size of a set of vertices which does not contain any such triangles.