Jean-François Maurras

Title:
On the k-cliques polyhedra

Abstract:
In this paper we study the neighbourlicity of the polyhedron $P_{k n}^2$ of the
$k$-cliques of the complete graph $K_n$ with $n$ vertices. We
prove that this polyhedron is $3$-neighbourly. Following a remark
of Pierre Duchet we generalize partially this result to the
$k$-clique polyhedra of $r$-uniforme complete hypergraphs,
$P_{kn}^r$. We study a linear programming model which give the
neighbourlicity of a given $P_{kn}^r$, $2^{r}-1$ in each studied case.
We are thus able to give an
upper bound of neighbourlicity of any $P_{kn}^r$. The proof of
this result uses an interpretation of a minimum set of cliques non
defining a face of $P_{kn}^r$ in term of a particular maximum
stable set of the edge graph of the unit hypercube in $(r+1)$
dimensions.