Plans projectifs, cliques et enveloppes convexes
Institution:
Aix-Marseille 2Disciplines:
Directors:
Abstract EN:
We study in this work different types of convex hull of subsets of vertices of the unit cube. We characterize the convex hull of the projective planes of order 2 considered as a subset of the set of the 35 triples of the set with 7 elements. In one second part, we study the neighbourlicity of the k-cliques polyhedron of the complete graph. We show that this polyhedron is 3-neighbourly, we make the conjecture that the same polyhedron defined on the complete r-uniform hypergraphs is (2r - 1)-neighbourly. We describe an integer programming modell which allows us to verify this hypothesis in some particular cases.
Abstract FR:
Dans ce travail nous étudions différents types d'enveloppes convexes de sous-ensembles de sommets du cube unité. Nous caractérisons l'enveloppe convexe des plans projectifs d'ordre 2 en tant que sous-ensembles de l'ensemble des 35 triples de l'ensemble à 7 éléments. Dans une seconde partie, nous étudions la connectivité du polyèdre des k-cliques du graphe complet. Nous montrons que ce polyèdre est 3-neighbourly, nous conjecturons que ce même polyèdre défini sur les hypergraphes complets r-uniformes est (2r - 1)-neighbourly. Nous décrivons un modèle de programmation en nombres entiers qui nous permet de vérifier cette conjecture dans quelques cas particuliers