Structure d'incidence

Tout graphe (pas nécessairement simple ; éventuellement avec boucles et arêtes multiples ) est une structure d'incidence uniforme avec deux points par droite. Dans ces exemples, les sommets du graphe forment l'ensemble de points, les arêtes du graphe forment l'ensemble de droites et l'incidence signifie qu'un sommet est une extrémité d'une arête.

Les structures d'incidence sont rarement étudiées dans leur pleine généralité; il est plus usuel d'étudier les structures d'incidence qui satisfont certains axiomes supplémentaires. Par exemple, un espace linéaire partiel est une structure d'incidence qui satisfait les deux conditions suivantes :

1. Deux points distincts sont incidents à au plus une même droite commune, et
2. chaque droite est incidente à au moins deux points.

Si le premier axiome est remplacé par l'axiome plus fort :

1. Deux points distincts sont incidents à exactement une même droite commune,

la structure d'incidence est appelée un espace linéaire[4].

Un exemple plus spécialisé est un k-réseau ; c'est une structure d'incidence dans laquelle les droites sont réparties en k classes parallèles, de sorte que deux droites de la même classe parallèle n'ont pas de point en commun, mais deux droites de classes différentes ont exactement un point en commun, et chaque point appartient à exactement une droite de chaque classe parallèle. Un exemple de k-réseau est l'ensemble des points d'un plan affine avec k classes parallèles de droites affines.

Les sept points sont des éléments de sept droites dans le plan de Fano.

Tout hypergraphe ou famille d'ensemble peut être considéré comme une structure d'incidence dans laquelle l'ensemble universel joue le rôle des "points", la famille d'ensembles correspondante joue le rôle de "droites" et la relation d'incidence est l'appartenance ensembliste "∈". Inversement, chaque structure d'incidence peut être considérée comme un hypergraphe en identifiant les droites avec les ensembles de points qui y sont incidents.

Un plan en blocs est, en toute généralité, composé d'un ensemble X et d'une famille de sous-ensembles de X (un sous-ensemble peut y figurer plusieurs fois). Normalement, un plan en blocs doit satisfaire des conditions de régularité numérique. En tant que structure d'incidence, X est l'ensemble des points et F est l'ensemble des droites, généralement appelées blocs dans ce contexte (les blocs répétés doivent avoir des noms distincts, donc F est en fait un ensemble et non un multiensemble). Si tous les sous-ensembles de F ont la même taille, le plan en blocs est appelé uniforme. Si chaque élément de X apparaît dans le même nombre de sous-ensembles, le plan de bloc est dite régulier. Le dual d'un plan de bloc uniforme est un plan régulier et vice-versa.

On considère le plan de bloc (ou hypergraphe) donné par:

${\displaystyle P=\left\{1,2,3,4,5,6,7\right\}}$ ,

${\displaystyle D=\left\{\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}\right\}}$ .

Cette structure d'incidence est appelée le plan de Fano. En tant que plan en bloc, il est à la fois uniforme et régulier.

Dans l'étiquetage donné, les droites sont précisément les sous-ensembles constitués de trois points dont les étiquettes s'additionnent à zéro en utilisant l'addition nim. De façon équivalente, chaque nombre, lorsqu'il est écrit en binaire, peut être identifié avec un vecteur non nul de longueur trois sur le corps binaire GF(2). Trois vecteurs qui génèrent un sous-espace vectoriel forment une droite; dans ce cas, cela équivaut à ce que leur somme vectorielle soit le vecteur nul.

La matrice d'incidence d'une structure d'incidence (finie) est une matrice binaire dont les lignes sont indexées par les points {p_i } et les colonnes indexées par les droites {d_j }, et où l'entrée i,j est un 1 si p_i I d_j et 0 sinon[5]. Une matrice d'incidence n'est déterminée de manière unique seulement par l'ordre choisi sur les points et les lignes[6].

La structure d'incidence non uniforme donnée ci-dessus (exemple numéro 2) est définie par:

P = {A, B, C, D, E, P}

D = { l = {C, P, E}, m = {P}, n = {P, D}, o = {P, A}, p = {A, B}, q = {P, B} }.

Une matrice d'incidence pour cette structure est:

${\displaystyle \left({\begin{matrix}0&0&0&1&1&0\\0&0&0&0&1&1\\1&0&0&0&0&0\\0&0&1&0&0&0\\1&0&0&0&0&0\\1&1&1&1&0&1\end{matrix}}\right)}$

qui correspond à la table d'incidence :

I	l	m	n	o	p	q
A	0	0	0	1	1	0
B	0	0	0	0	1	1
C	1	0	0	0	0	0
D	0	0	1	0	0	0
E	1	0	0	0	0	0
P	1	1	1	1	0	1

Si une structure d'incidence C a une matrice d'incidence M, alors la structure duale C^∗ a comme matrice d'incidence la matrice transposée M ^T (et elle est définie par cette matrice).

Une structure d'incidence est auto-duale s'il existe un ordre sur les points et les droites pour lesquels la matrice d'incidence est symétrique.

Avec les étiquettes données dans l'exemple numéro 1 ci-dessus et avec les points ordonnés A, B, C, D, G, F, E et les lignes ordonnées l, p, n, s, r, m, q, le plan de Fano a la matrice d'incidence :

${\displaystyle \left({\begin{matrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\1&0&0&0&0&1&1\\0&1&0&1&0&1&0\\0&1&0&0&1&0&1\\0&0&1&1&0&0&1\\0&0&1&0&1&1&0\end{matrix}}\right).}$

Comme la matrice est symétrique, le plan de Fano est une structure d'incidence auto-duale.

Une représentation figurative d'une structure d'incidence est construite en représentant les points de la structure par des points dans un plan et les droites par un des moyens visuels adapté pour joindre les points[6]. Les points peuvent être placés de manière arbitraire, sans restriction sur les distances entre les points ou les relations entre les points. Dans une structure d'incidence, les concepts de point situé entre deux autres points ou d'ordre d'alignement de points sur une droite ne sont pas définies. Par opposition, la géométrie ordonnée a une notion d'entre-deux (betweenness). Les mêmes observations peuvent être faites à propos des représentations des droites. En particulier, les droites ne sont pas nécessairement représentées par des segments de droite (exemples 1, 3 et 4). Comme dans la représentation figurative des graphe (mathématiques discrètes)s, le croisement de deux droites en un lieu autre qu'un point n'a pas de signification en termes de structure d'incidence; ce n'est qu'un effet de la représentation. Ces figures d'incidence peuvent parfois ressembler à des graphes, mais ce ne sont pas des graphes, à moins que la structure d'incidence ne soit un graphe.

Les structures d'incidence peuvent être modélisées par des points et des courbes dans le plan euclidien avec la signification géométrique habituelle de l'incidence. Certaines structures d'incidence admettent une représentation par des points et des droites rectilignes. Ces structures peuvent être appelées réalisables. Le plan de Fano (exemple 1 ci-dessus) n'est pas réalisable car il nécessite au moins une ligne courbe. La configuration Möbius-Kantor (exemple 4 ci-dessus) n'est pas réalisable dans le plan euclidien, mais elle l'est dans le plan complexe[7] Les exemples 2 et 5 ci-dessus sont réalisables et les figures d'incidence données le démontrent. Ernst Steinitz, dans sa thèse de 1894[8] a montré qu'une n₃-configuration (une structure d'incidence avec n points et n droites, trois points par droites et trois droites passant par chaque point) soit est réalisable, soit nécessite l'utilisation d'une seule ligne courbe dans leur représentation. Le plan de Fano est l'unique 7₃-configuration et la configuration de Möbius-Kantor est l'unique 8₃-configuration.

Graphe de Heawood avec un étiquetage

À chaque structure d'incidence C correspond un graphe biparti appelé graphe d'incidence ou graphe de Levi de la structure. Comme tout graphe biparti est bicoloriable, les sommets d'un graphe de Levi peuvet être colorés en noir et blanc par exemple, les sommets noirs correspondant aux points et les sommets blancs correspondant aux droites de C. Les arêtes de ce graphe correspondent aux drapeaux (paires incidentes point—droite ) de la structure d'incidence. Le graphe de Levi original est le graphe d'incidence du quadrilatère généralisé d'ordre deux (exemple 3 ci-dessus) mais le terme a été étendu par H. S. M. Coxeter pour désigner le graphe d'incidence de toute structure d'incidence[9].

Graphe de Levi de la configuration Möbius-Kantor (# 4)

Le graphe de Levi du plan de Fano est le graphe de Heawood. Ce graphe est connexe et sommet-transitif, et il existe un automorphisme (tel que celui défini par la réflexion autour de l'axe vertical dans la figure du graphe de Heawood) qui échange des sommets noirs et blancs. Ceci montre que le plan de Fano est auto-dual.

La représentation particulière du graphe de Levi de la configuration Möbius-Kantor (exemple 4 ci-dessus) illustre qu'une rotation de ${\displaystyle \pi /4}$ autour du centre (soit dans le sens horaire soit dans le sens antihoraire) du diagramme échange les sommets bleu et rouge et envoie les arêtes sur les arêtes. Autrement dit, il existe un automorphisme de ce graphe qui échange les couleurs. Par conséquent, la structure d'incidence connue sous le nom de configuration Möbius-Kantor est auto-duale.