L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.

Dimension VC d'un hypergraphe

Ce sujet comporte six pages et quatre parties.

La partie I introduit la notion de dimension de Vapnik-Chervonenkis, en abrégé dimension

, d'un hypergraphe et établit une borne polynomiale sur la complexité d'un hypergraphe de dimension VC bornée. La partie II étudie l'effet d'une méthode de normalisation d'hypergraphes sur la dimension VC. La partie III détermine la dimension VC de certains hypergraphes définis géométriquement en établissant au préalable quelques résultats classiques de géométrie convexe. La partie IV examine un algorithme d'approximation d'un hypergraphe géométrique de dimension VC non bornée.

Les notions introduites en partie I sont utilisées dans les parties II et III. La partie IV s'appuie sur certains résultats de la partie III. Les résultats d'une question pourront être admis dans la suite du sujet.

Pour tout ensemble

on note

l'ensemble des parties de

, c'est-à-dire :

Un hypergraphe de sommets

est un sous-ensemble de

. Si

est un hypergraphe de sommets

alors on appelle hyperarête de

tout élément de

. Par exemple si

alors

est un hypergraphe de sommets

l'ensemble

est une hyperarête de

Pour tout ensemble fini

on note

son cardinal, c'est-à-dire son nombre d'éléments. En particulier, quand

est un hypergraphe,

désigne le nombre d'hyperarêtes de

Tout au long du sujet,

désignent des entiers strictement positifs. Pour tous entiers

on note

le nombre de sous-ensembles distincts de cardinal

d'un ensemble de cardinal

. En particulier

pour tout

Partie I. Dimension VC d'un hypergraphe

Question 1 Soit

l'ensemble des entiers compris entre 0 et

.
a. Quel est, en fonction de

, le nombre maximum d'hyperarêtes que peut avoir un hypergraphe de sommets

? On justifiera la réponse.
b. Combien d'hypergraphes de sommets

différents existe-t-il? On justifiera la réponse.
c. Démontrer :

est un hypergraphe de sommets

est un sous-ensemble de

, on définit la trace de

sur

, notée

, par :

Question 2 Soient

un ensemble fini,

un hypergraphe de sommets

.
a. Donner un exemple de

pour lesquels

.
b. Démontrer que pour toutes hyperarêtes

, on a :

c. En déduire que

Soit

un hypergraphe de sommets

. On dit qu'un sous-ensemble

est pulvérisé par

. Si

est fini, on définit la dimension

, notée dimvc

, comme le cardinal maximum d'un sous-ensemble

pulvérisé par

, augmenté de 1 :

On ne définit pas de notion de dimension VC pour les hypergraphes dont l'ensemble de sommets est infini.

Question 3 Dans cette question on suppose

.
a. Soient

un ensemble de

réels deux à deux distincts et

l'hypergraphe de sommets

défini par

. Calculer

.
b. On note

. Soit

un sous-ensemble de

de cardinal

. On définit :

est donc un hypergraphe de sommets

. Calculer

Question 4 Soient

un ensemble fini de cardinal

un hypergraphe de sommets

.
a. Montrer que si

alors

.
b. Soit

. On définit deux hypergraphes de sommets

Montrer que

.
c. On considère à nouveau les hypergraphes

définis à la question

. Montrer que

et que

.
d. Montrer que si

, alors :

e. Donner, pour tout

, un exemple d'hypergraphe à

sommets pour lequel l'inégalité de la question

devient une égalité. On justifiera la réponse.

Partie II. Compression d'hypergraphe et dimension VC

Soit

un hypergraphe de sommets

. Pour tout

, on définit l'hypergraphe décalé de

par

, noté

, par :

Par exemple, si

, alors :

Dans le reste de cette partie on suppose que

et que

est un hypergraphe de sommets

Question 5 Montrer que pour tout

on a

. Indication : on pourra chercher à expliciter une bijection entre

Question 6 Soient

.
a. Montrer que si

alors

.
b. Montrer que si

alors

Question 7 Montrer que pour tout

on a

Question 8 Pour tout

on note

le reste de la division entière de

par

, c'est-à-dire que

est l'unique entier

tel qu'il existe

satisfaisant

. On considère la suite

d'hypergraphes définie par :

a. Démontrer qu'il existe un entier

et un hypergraphe

de sommets

tel que :

b. Démontrer que

.
c. En déduire une nouvelle preuve de l'identité établie à la question

ù

Partie III. Dimension VC d'hypergraphes géométriques

On munit l'espace vectoriel

du produit scalaire usuel :

et on rappelle que

muni de ce produit scalaire est un espace euclidien. Un ensemble

est dit convexe si et seulement si :

Par convention, l'ensemble vide est convexe. On définit l'enveloppe convexe d'un ensemble

, notée

, comme l'intersection de tous les sous-ensembles convexes de

qui contiennent

On note

l'ensemble des sous-ensembles convexes de

Question 9

a. Montrer que toute intersection de sous-ensembles convexes de

est convexe.
b. Démontrer que pour tout sous-ensemble

les trois propositions suivantes sont équivalentes :
(1)

est convexe,
(2)

,
(3)

tels que

.
c. Démontrer que pour tout sous-ensemble

on a :

Un sous-ensemble

est un demi-espace fermé (resp. demi-espace ouvert) s'il existe

tels que

(resp.

). On note

l'ensemble des demi-espaces fermés de

Question 10

a. Montrer que tout demi-espace fermé de

est convexe.
b. Montrer que pour tout sous-ensemble

et tout demi-espace fermé

Une partition d'un ensemble

en deux parties est un ensemble

de sous-ensembles de

qui sont disjoints et dont l'union égale

Question 11 Soient

des vecteurs deux à deux distincts.
a. Montrer que si

alors il existe

réels

non tous nuls tels que

.
b. En déduire que si

alors l'ensemble

admet une partition en deux sous-ensembles non-vides

tels que

est non vide.

Question 12 Soit

un sous-ensemble fini de

et soit

l'hypergraphe de sommets

défini par

. Montrer que

Question 13 Soit

. Soit

où

sont des vecteurs de norme 1 deux à deux distincts. Calculer la dimension VC de l'hypergraphe

de sommets

défini par

. On justifiera la réponse.

Partie IV. Approximation d'une famille d'hypergraphes géométriques

Dans cette partie,

désigne un réel strictement compris entre 0 et 1 .

Soient

un ensemble de cardinal

un ensemble (éventuellement infini) de sous-ensembles de

. Un ensemble

est

-fin pour

relativement à

Les ensembles

-fins jouent un rôle important dans les algorithmes d'approximation en géométrie algorithmique. Quand la dimension VC de l'hypergraphe

est bornée indépendamment de

, il existe toujours un ensemble

-fin de petite taille et des méthodes simples et générales permettent d'en calculer un efficacement. Dans le cas

, la dimension VC de cet hypergraphe n'est pas bornée indépendamment de

(cf question 13) et il faut recourir à des méthodes spécialisées. L'objectif de cette partie est d'étudier l'une de ces méthodes.

Question 14 Soient

.
a. On suppose que

et que pour tout sous-ensemble

de cardinal

, l'ensemble

est non vide. En déduire que l'ensemble

est non-vide.

Indication : on pourra fixer, de manière arbitraire, pour tout

, un vecteur

et utiliser la question 11 (b).
b. Montrer que si

et que pour tout sous-ensemble

de cardinal

, l'ensemble

est non vide, alors l'ensemble

est non-vide.

Question 15 Soit

un ensemble de cardinal

. Un point central de

est un élément

(pas nécessairement dans

) tel que tout demi-espace fermé contenant

contient au moins

éléments de

.
a. Montrer qu'un vecteur

est un point central de

si et seulement si

appartient à tout demi-espace ouvert

contenant strictement plus de

vecteurs de

.
b. On définit

c'est-à-dire que les éléments de

sont les enveloppes convexes de sous-ensembles de

contenus dans un demi-espace ouvert

contenant strictement plus que

vecteurs de

. Montrer que pour tous

l'intersection

est non-vide.
c. Montrer que tout ensemble fini

de cardinal

admet un point central.

Un principe général de construction d'un ensemble

-fin relativement à

est le suivant :

Entrée : un sous-ensemble fini $S \subseteq \mathbb{R}^{2}$ et $0<\varepsilon<1$.
Sortie : $T \subseteq \mathbb{R}^{2}$ qui est $\varepsilon$-fin pour $S$ relativement à $\mathcal{C}_{2}$.
$T \leftarrow \emptyset$
Tant qu'il existe $C \in \mathcal{C}_{2}$ tel que $|C \cap S| \geq \varepsilon|S|$ et $C \cap T=\emptyset$,
| Calculer un point central $c$ de $C \cap S$
| Ajouter $c$ à $T$
Retourner $T$.

Soit

un ensemble de cardinal

et soit

un point central de

. On suppose que

. Un triangle de

est un sous-ensemble de

de cardinal 3 . On dit qu'un triangle

entoure un vecteur

. La profondeur simpliciale d'un vecteur

par rapport à

est le nombre de triangles de

qui entourent

Question 16 On admet le résultat suivant.
Lemme de sélection : si

est de cardinal

est un point central de

alors la profondeur simpliciale de

par rapport à

est supérieure ou égale à

. Montrer que la méthode

termine et majorer le cardinal de l'ensemble

retourné.