Graphes Lies aux Espaces Polaires

Europ. J. Combinatories (1984) 5,255-290

Graphes Lies aux Espaces Polaires

FRANc;OIS ZARA

Let G be II simple graph. Let '€ be the set of cliques of G: i.e, of maximal complete subgraphsof G. We study the graphs G satisfying the following two axioms:Al 3reN such that VCe '€ , Ic l= r,A2 3/ e N such that VC e '€ and for each vertex x of G not in C, x is adjacent to exactly / verticesof C.

Infinite classes of such graphs are known, for instance the collinearity graphs of polar spaces.But sporadic examples also exist: let us mention the graph related to MacLanghlin group.

We establish some general properties of graphs satisfying AI and A2. We characterize thoserelated to polar spaces and classify graphs with parameter t equal to 0, r-I and r-2.

I. INTRODUCTION

Le graphe de collinearite G d'un espace polaire jouit des proprietes suivantes:Al Toutes les cliques de G ont Ie meme cardinal r.A2 Si C est une clique et x un sommet de G n'appartenant pas a C, alors x est adjacenta exactement t elements de C, ou test independant du couple (C, x).

Ce travail est consacre a l'etude des graphes simples G satisfaisant Al et A2.Les espaces polaires ne sont pas les seules geometries associees ade tels graphes. Nous

en presentons les exemples connus au paragraphe 2.Dans Ie paragraphe 3, nous montrons que si Ie graphe G satisfait aAl et A2 et est

fortement regulier, alors c'est un graphe pseudogeometrique,Dans Ie paragraphe 4, nous etudions les graphes G satisfaisant aA I et A2 tels que G

ne soit pas connexe. Nous en deduisons en particulier que quelque soit Ie couples d'entiers(r, t) verifiant t~ ;-1, il existe une infinite de graphes G satisfaisant aAI, A2 et ayant(r, r) comme parametres.

Dans Ie paragraphe 5, nous introduisons une operation sur la classe de tous les graphessimples: les m-extensions. Cette operation nous permet de caracteriser les espaces polairesparmi tous les graphes qui verifient Al et A2.

Dans Ie paragraphe 6, no us etudions les proprietes de G lorsque G est connexe. II esta remarquer que les proprietes de regularite ainsi trouvees pour le graphe G ont eteobtenues par A. Blokhuis, T. Kloks et F. Peters (cf. [8]). Nous utilisons ces resultats pourcaracteriser les epaces polaires par leurs parametres.

Dans Ie paragraphe 7, nous classifions tous les graphes satisfaisant aAI, A1 et t = r - 2.Lorsque G est connexe, G est fortement regulier et les seules possibilites pour G sont,pour r;;' 4, les complementaires des graphes latticiels L2( r) et triangulaire T(2r). Lorsquer=3, nous obtenons les 3 quadrangles generalises de type (3,2) [=~(3)], (3,3) [=T(6)]et (3, 5).

Entin, nous montrons que si G satisfait aAI, A2 et si t ~ 2r - I et G est connexe, alorsG est une m-extension d'un graphe du type precedent [L2 ( r) ou T(2r), r;;' 5].

2. EXEMPLEs

Dans tout ce travail, les graphes sont tinis, non diriges sans boucles ni aretes multiples.

NOTATIONS 2.1. Soit Gun graphe dont I'ensemble des sommets est V(G). Si Festun sous-ensemble de V( G), on pose:

2550195-668X /84/030255 +36 S02.00/0 © 1984 Academic Press Inc . (London) Limited

256 F. Zara

.1(F)={a /aE V(G) et VbE F, {a, b} est une arete de G},

r(F)={alaE V(G) et VbEF, {a , b} n'est pas une arete de G}.

On appelle G(F) Ie graphe induit sur F et on pose G F = G(.1(F».Si a et b sont des sommets de G, on pose .1(a) = .1({a}), rca) = r({a}), .1(a, b) =

.1({ a, b}); G; = G{a}, Gab = G{ab}' Une clique est un sous-graphe complet maximal de G.Si m est un entier, on pose:

rim= {CIG( C) est un sous-graphe complet de G, Ici = m},

ri = {cIG( C) est une clique de G}.

Si G(F) est un sous-graphe complet de G, on pose :

ri ( F ) = {CIC E ri, Fe C}-on a ri(0) = ri.

Entin G denote Ie graphe complementaire de G.

AXIOMEs. On appelle (H) les hypotheses suiuantes sur Ie graphe G:

(H){ A I 3rEN*telqueVCEri,ICI=r.A2 3tEN tel que VCE ri, VXE V(G)-C, 1.1(x) 11 cl= t.

On dit que le triple (I V( G)I; r, t) est Ie systeme de parametres de G, ou que les parametresde G ·sont (I V( G) I; r, r). Dans la terminologie de Neumaier (ef [6]), toutes les cliques sontdites regulieres, de nexus t, si G satisfait a (H).

REMARQUES. (I) Un graphe complet G verifie trivialement (H): on a r = IV( G)I et test indetermine, (2) Un graphe discret verifie (H). Ses parametres sont (I V( G)I; 1,0).

. EXEMPLEs. (a) Graphes lattieiels L2(n). On pose n = {l, 2, . . . , n}, E = n x n. On metune structure de graphe G sur E par (a, b) - (e, d) si a ;i= e et b;i=d.

Le graphe G est fortement regulier et verifie (H). Ses parametres sont (n 2; n, n -2).

On a Aut G = s.JC2•

(b) Graphes triangulaires T(2n). On pose 2n = {I , 2, . .. , 2n}, E = {ala e2n, lal = 2}.On met une structure de graphe G sur E par {a, b} est une arete de G si a 11 b = 0 .

Le graphe G est fortement regulier et verifie (H). Ses parametres sont (n(2n -I);n, n -2). On a Aut G= 52"'

(c) Espaees polaires. Soient K un corps fini et V une espace vectoriel de dimensionm sur K, m ;;':3.

Soient ,8 EAut K verifiant ,82= I et K o= {A IA E K, ,8(A) = A}. Si ,8 = I, K o= K. On poseIKol = q, alors, si ,8;i= I, IK I= q2. Soit 4J: V x V ~ K une forme ,8-sesquilineaire nondegeneree, reflexive et tracique (resp. Q : V ~ K une forme quadratique telle que Ia formebilineaire associee 4J soit non degeneree). On pose E = {(a) la E V - {O} et a isotrope (resp.singulier)} ; {(a) , (b)} est une arete de G si 4J(a, b)=O et (a);i=(b).

Une clique est I'ensemble des droites d'un sous-espace isotrope (resp. singulier)maximal de V.

Le graphe G est fortement regulier et verifie (H).L'espace polaire est de rang u dans Ies cas suivants:

. (I) Sp(2u, q),

(4) 0_(2u +2, q),

(2) 0(2u +I, q),

(5) U(2u, q 2),

(3) 0+(2u, q),

(6) U(2u + I, q2).

Graphes lies aux espaces polaires

Posons a = IKI: a = q dans les cas (1)-(4) et a = qZ dans les cas (5) et (6).On a

257

aU-Ir=-

a-I'

avec pour valeur de b:

a u - l -I

a -I ' (a U I)n = -- (I +ba U

-Z)

a-I

Cas : (1) (2) (3) (4)

b a a 1 aZ

(5) (6)a liZ a31 Z

(d) Quadrangles generalises. lis verifient (H) avec t = 1 et aucun sommet n'est lie atous les autres.

(e) Soient V un espace vectoriel de dimension 2m sur Ie corps IFz et Q= V~lFz uneforme quadratique telle que la forme bilineaire alternee associee cf>: V x V ~ IFz soit nondegeneree,

On pose E ={xjx E v, Q(x) = l} et on definit une structure de graphe G sur E par: {x, y}est une arete de G si x ~ y et cf> (x, y) = O.

Alors G est fortement regulier et verifie AI: toutes ses cliques sont de cardinal r = 2m-

I.

Si Q est d'indice maximal et seulement dans ce cas, G verifie Al et A2 et ses parametressont:

(2m-

I(2m -I); 2m-

I, 2m

-z).

(f) Soient V un espace vectoriel de dimension 2m sur Ie corps IFq et Q: V ~ IF q uneforme quadratique d'indice maximal.

On definit une structure de graphe G sur V par: {x, y} est une arete de G si x ~ y etQ(y - x) = O. Alors G est fortement regulier, verifie (H) et ses parametres sont(qZm; «. qm-l).

Si G 1 est Ie groupe des isometrics de Q et Gz le groupe des translations de V, on aGz ><l G, c Aut G.

Les cliques de G sont les sous-espaces singuliers maximaux et leurs translates.On appelle un tel graphe un 'graphe affine orthogonal'. Nous donnons maintenant des

exemples de graphes verifiants (H) 'sporadiques'.(g) Soit 8={1,2,3,4,5,6, 7,8}. On pose E={(a,~)I(a,~) est une partition de 8 en

deux sous-ensembles de cardinal 4}.On dit que (a, a') E Ex E, a = (a, ~), a' = (a', ~') est de type 1 si la (J a'i = 2 (alors on

a 2 = la (J a'i = la (J ~'I =I~ (J a'i = I~' (J a'l) et que (a, a') est de type 2 si la (J a'i =1.Sur E on met une structure de graphe G par: {a, a'} est une arete de G si (a, a') est

de type 2. Alors G est fortement regulier et verifie (H); ses parametres sont (35; 5, 2).II est remarquable que Ie graphe cornplementaire G verifie aussi (H) de parametres

(35; 7, 3) [cf. Ie graphe associe a0+(6, 2) dans (c)]. On a Aut G = 58.(h) Soient V un espace vectoriel de dimension 6 sur 1F 3 et cf>: V x V ~ 1F3 une forme

bilineaire symetrique non degeneree. On suppose que V admet une base orthonormale.On appele E I'ensemble des droites de V portant des vecteurs de longueur I. Sur E

on definit une structure de graphe G par: {a, b} est une arete de G si cf> (a, b) = O. AlorsG est fortement regulier et verifie (H); ses parametres sont (126; 6, 2).

(i) Le graphe G construit par MacLaughlin est fortement regulier et verifie (H); sesparametres sont (275; 5, 2).

3. PROPRIETES DE REGULARITE: PARAMETRES

Dans tout ce paragraphe G est un graphe qui verifie (H), de parametres (n; r, t). Onappelle points les sommets de G.

258 F. Zara

PROPOSITION 3.1.(1) Si C 1 et C2 sont deux elements distincts de C(;, on a ICI n c 2 1~ t.(2) Toute clique de G est determinee par t + 1 de ses points.(3) Si t ~ 1, Ie diametre de G est 2 et G est connexe.

PREUVE. (1) C[ n C2 = {at> a2, ... , au} et si b e C2 - Ct> b est adjacent a a, (1~ i ~ u)qui sont des elements de C[, done, d'apres A2 on a u ~ t et ICI n c 2 1~ t.

(2) On a d'abord t + 1~ ret, si on se donne t + 1 points d'une clique G( C), d'apresIe (1), il n'y a que C qui Ies contient.

(3) Soient a E V( G) et b e rca). II existe une clique G( C) qui contient a. D'apres A2,il existe c E ..1 (b) n C car t ~ 1. Done c est adjacent a a et b, mais a et b ne sont pasadjacents, ce qui montre que Ie diametre de G est 2.

La condition t ~ 1 est necessaire et suffisante pour que G soit connexe, comme Iemontre Ia proposition suivante que caracterise les graphes G verifiant (H) avec t = O.

PROPOSITION 3.2. Soit G un graphe qui oerifie (H), de parametres (n; r,O). Alors Gest fortement regulier et non connexe. Reciproquement, soit E un ensemble qui admet unepartition en sous-ensembles tous de meme cardinal r. On met une structure de graphe G surE par: a est adjacent ab si a et b sont distincts et dans un meme ensemble de la partition.Alors G cerifie (H), de parametres (lEI; r,O).

PREUVE. Elle n'offre pas de difficultes,

Nous donnons maintenant deux proprietes fondamentales des graphes G qui satisfonta (H): les propositions 3.3 et 3.5.

PROPOSITION 3.3. [C-Decomposition de V(G)]. Soient CEC(; et ~(C)(=~)=

{DID E C(;, Ic n DI = t}. Alors(1) On a la partition de V( G): V( G) = C U(LJDE~ (D - C)).(2) Si D, et D 2 sont deux elements distincts de ~, D[ n D 2 c C.(3) r-tln-ret 1~1=(n-r)/(r-t).

PREUVE. (1) Soit a E V( G) - C; alors a est adjacent a t points de C et, si D estl'unique clique qui contient a et ..1(a)n C, on a D E~, done V( G) = C U(UDE~ (D- C)).

(2) Soient D, et D 2 deux elements de ~. Si (D, n D 2 ) - C ¥- 0, soit a E tD, n D 2 ) - C.Alors a est adjacent aux t points de D I n C et aux t points de D 2 n C. Comme G verifieA2, on obtient D I n C = D 2 n C, mais alors {a} u (DI n C) determine un unique elementD de ~ et D = D I = D 2•

Done, si D I ¥-D 2 , on a (DI n D 2 ) -r-: C = 0 et D I n D 2 c C.II en resulte que V( G) = C U (LJDE~ (D - C)).(3) D'apres ce qui predede, comme pour chaque D dans ~, ID - ci = r - t, on obtient

n=r+I~I(r-t)d'ou les resultats: r-tln-r et 1~1=(n-r)/(r-t).

NOTATIONS 3.4. Soit m un entier. Si FE C(;m, on pose

A(F)=I.1(F)1 et a(F)=A(F)-(r~m).r-t

PROPOSITION 3.5. Soient m un entier et FE C(;m' Alors, ou bien GF est complet, ou bienGF oerifie (H), de parametres (A(F); r- m, t - m).

G F est complet si et seulement si a(F) = O.

Graphes lies aux espaces polaires 259

PREUVE. Deux points b, et b2 de .1(F) sont adjacents dans G F si et seulement si ilssont adjacents dans G. Soit G( C 1) une clique de GF , alors G(F u C 1) est un sous-graphecomplet de G et il existe C E cg tel que F u C 1 C C. On a C I C C - Fe .1(F). CommeG( C - F) est un sous-graphe complet de GF, d'apres le caractere maximal de C h onobtient C t = C - F; done GF verifie AI, le cardinal d'une clique etant r - m.

Si GF est complet, on .1(F) = Ch done A(F) = r- met a(F) =0. Si a(F) =0, A(F) =r - m, done, d'apres ce qui precede, GF est complet. Supposons maintenant GF noncomplet. Alors .1(F).,e Ct. Soit b e .1(F) - Ct. Comme C, u peg, comme b ~ C1 U F, bestadjacent a t points de C, u F et, parmi ces t points, il y a tous les points de F, done best adjacent a t - m points de GF ( Cd et GF verifie A2; ses parametres sont (A(F); r - m,t-m).

PROPOSITION 3.6. Soient C E cg et mEN, m e: t. On pose K m = LFcC,!FI=m A(F). Alors

PREUVE. On a x; = LFCC,IFI~m 1.1(F) - ci+(~)(r- m).

Si x E V( G) - C et si 8m(x) est le nombre des sous-ensembles de cardinal m de .1(x) n C,on a 8m (x ) = (~) et

L 1.1(F)nCI= L 8m(X)=( t)(n_r);Fcc,IFI~m XEV(G)-C m

d'ou

Comme

on a la formule indiquee,

COROLLAIRE 3.7. Soient a E V( G), b e .1(a) et C Erca).(1) Si G est regulier, on a

k = 1.1 (a)1 = r -1 +.!(n - r), 1= lr(a)1 = (r - t)(n - r) .r r

(2) Si G est fortement regulier, on a:

t(t-I) ktA=I.1(a,b)l=r-2+ ( )(n-r),IL=I.1(a,c)I=-.

r r-I r-I

PREUVE. (1) Si G est regulier, par definition, il existe un entier k tel que Vx E V( G),k = 1.1(x)l, done, avec les notations de la proposition 3.6:

Comme

Kt=rk=t(n-r)+r(r-l),t

d'ou k=r-I+-(n-r).r

I=n-k-l, ana I=(r-t)(n-r).r

260 F. Zara

(2) Le meme raisonnement que ci-dessus montrer que si G est fortement regulier on a:

t( t - I)A=r-2+ ( )(n-r)

r r-I

et, comme /-LI=k(k-A-I), on obtient /-L=kt/(r-I).

COROLLAIRE, 3.8.(I) Si G est regulier alors rln.(2) Si G est fortement regulier, alors rln, (r-I)lk et si s=k/(r-I). A=(r-2)+(s-l)(t-I) , /-L =st et n = r[1 +(r-I)(s-I)/t].

Autrement dit, G est un graphe pseudogeometrique.

PREUVE. (I) On suppose que G est regulier. Soit C E cg; on a la partition de V( G):

V( G) = C U ( LJ (D - C))DEqj)

Soit a E C, on a r(a) = (r(a) n C) U (LJDEqj) «D - C) n r(a))). On fait une partition de~: ~I ={DIDE~, a E D}, ~2= ~-~I' Si DE ~2' alors Dn C c .1(a) et Dn.1(a) = DnC puisque ces deux ensembles sont de cardinal t et D n C n .1(a) = D n C cD n .1(a).Done D - C c Ft;a). On a aussi Ft; a) n C = 0. Si D E ~ l s a e D - C, done D - C c .1(a)et (D - C) n r(a) = 0 . II en resulte que r(a) = LJDEqj)2(D - C) et 1= lr(a)1 = (r- t)I~21;done 1~21 = I/(r- r) = (n/ r) -I est un entier, d'ou rln.

(2) Si G est fortement regulier et si a E V( G), Ga est regulier, done r-Ilk et, en posants = k/(r-I), on obtient les valeurs annoncees,

Si G est fortement regulier, on a les conditions suivantes necessaires pour l'existencede G :

doit etre un carre: ici

(A - /-L? +4(k - /-L) = (r - t + s - I?

Le spectre de G doit etre:k = s(r-I) de multiplicite I,r=r-t-I de multiplicite/=r(r-I)s(s-I)/t(r-t+s-I),S= - s de multiplicite n - I - f,done r(r-I)s(s -I)/t(r- t +s -I) do it etre entier.

La condition de Krein donne (s-l)(r-2t)~(r-2)(r-t)2.Si r~2t, cette conditionest automatiquement satisfaite. Par contre, en utilisant la '/-L-bound' de Neumaier (cf,[7]) on a aussi la condition:

s-I~(r-t?(2t-I).

REMARQUE. Si r > 2 t + I, on a

(r-2)(r- t? 2s-I~ ~(r-t) (2t-l).

r-2t

4. CONNEXITE DE G; PROPRIETES GENERALES

Dans ce paragraphe, nous etudions les proprietes de G lorsque G n'est pas connexe.


DEFINITION 4.1. Soit G une graphe. On appelle 'radical de G' et on note R(G), l'ensemble des sommets a de G qui sont adjacents a tous Ies autres sommets de G:

R(G)={alaE V(G), V(G)=41(a)u{a}}.

Soit Gun graphe et soit V( G) = A uB une partition de V( G) qui possede Ia propriete:Be 41(A). Alors G(A) et G(B) sont tous Ies deux des reunions de composantes connexesde G.

Soient G I et Gz des graphes. On suppose que V( G I ) et V( Gz) sont disjoints. SurE = V( G I ) u V( Gz) on met une structure de graphe G de Ia maniere suivante:(a) G, est une sous-graphe de G pour i = 1,2.(b) Vai E V( GJ (i = 1,2), {al> az} est une arete de G.II est clair que G I (resp. Gz) est une reunion de composantes connexes de G. Dans cesconditions, on pose G = G I V Gz (GI union Gz).

La generalisation a p facteurs n'offre pas de difficultes,

PROPOSITION 4.2. Soient G, (i = 1,2) des graphes et G = G I V Gz. Alors:(I) G oerifie Al si et seulement si G j oerifient Al (i = 1,2). Dans ce cas, si r (resp. rl> resp.rz) est Ie cardinal d'une clique de G, (resp. GI> resp. Gz), on a r = rl + rz.(2) (a) Si pour i = 1, 2, G, verifie (H), de parametres (n j ; rj , tJ avec rl - rl = rz - tz, alorsG terifie (H), de parametres (n l + nz; rl + rz, rl + tz).(b) On suppose qu'aucun des G, n' est un graphe complet et que G oerifie A.2. Alors, pouri = 1, 2, G j oerifie (H),' de parametres (n i ; ri, ti)' rl - t, = rz - tz et G uerifie Al avecr = rl + rz, t = rl + tz = rz + t..(3) Si G oerifie A2 et est regulier, alors G oerifie Al et pour i = 1, 2, G, oerifie (H) et estregulier. On a les relations, avec les notations eoidentes:

~ =!!.! = nzr rl rz

(4) On pose, dans ce numero, si d est un graphe:

Cfiz(d) = {Fld(F) sous-graphe complet de d, IFI = 2}.

Les conditions suivantes sont equitalentes:(a) G oerifie (H) et 3A E f:\J, V FE Cfiz( G), A(F) = A.(b) pour i = 1, 2, a, oerifie (H) et 3A j E f:\J, V FE Cfiz( GJ, A(F) = Ai,avec les relations Al + nz = Az+ n l = k, + kz.

Si ces relations sont oerifiees, on a r - t = rl - tl = rz - tz = 1.

PREUVE. (1) Soit G(C) une clique de G. On pose Cj=Cn V(GJ (i=I,2). II estclair que G j ( Ci ) est une clique de G, (i = 1,2). II en resulte que G verifie Al avec r = rl + rz-

(2) (a) Soient G( C) une clique de Get a E V( G) - C. On pose Cj = C n V( GJ (i = 1,2).Si a E V( G I) , a est adjacent a tl + rz points de C. De meme si a E V( Gz), a est adjacenta tz + rl points de C. Comme rl - t, = "z - tz a est adjacent at = tl + rz = tz + rl points deC et G verifie (H) d'apres Ie (I).

Comme r = rl + rz, on obtient r - t = rl - tl = r2 - t2.(b) On suppose que G verifie A2. Soit G( C) une clique de G. On pose C, = C n V( G i )

(i = 1,2). Par hypothese, Va E V( G) - C, a est adjacent a t points de C. Si a E V( G 1) , aest adjacent a tous les points de Cz et on a t=I41 I(a)nC11+ICzl. Si on fait varier Czparmi toutes Ies cliques de G2, on trouve ICzl = t -141I(a) n CII. Comme t et 141 I(a) n cilsont independants de Cz, Iczl est independant de la clique Gz(Cz) de Gz, done G z verifieAl Ie cardinal des cliques de G2 etant r-.

262 F. Zara

On a alors 1.1(a) n cil = t - r2.Comme le second membre de cette egalite est independantde la clique GI(C I ) de G lo G I verifie A2 avec t l = t r rs-

Par symetrie, nous voyons que G, verifient (H) (i -1,2) et t = rl + t2= r2+ t l, d'ourl - t, = r2 - t2 •

Dans ces conditions, d'apres Ie (1), G verifie Al avec r = rl + r2 et r - t = rl - t l = r2- t2.(3) Si G est regulier et verifie A2, d'apres ce qui predede G verifie Al et, pour i = 1,

2, G, verifie (H) et est regulier. On a, dans ces conditions k = k , + n2= k2+ nlo n = nl + n2,donc

(n l - rl ) (n2- r2) (n - r)1=11=12=(r,-tl) -r-I- =(r2- t2) -r-2- =(r-t) -r-·

Comme r - t = rl - t l = r2 - t2, nous obtenons n] r = nil rl = n21"z-(4) Remarquons d'abord que si un graphe G verifie (H), de parametres (n; r, t) et si

3A EN tel que VFE cg2' A(F) = A alors G est regulier, En effet, soit a E V( G). Pour toutb dans .1(a), nous avons A= 1.1(a) n.1 (b )1. D'apres le corollaire 3.7, nous avons:

(t -1)A=(r-l)-I+ - (1.1(a)I-(r-l»r-l

donc

(r - l )1.1(a)l= - (A+t+l-r)t-l

quantite independante de a: G est regulier.Ceci donne un sens ala relation du (4) (b): Al + n2 = A2+ n l = k, + k2 •

(i) Supposons la condition (a) satisfaite. Soient a et b deux points de V( GI), b e .1(a).On a: .1(a,b)=(.1(a,b)nV(GI»uV(G2), d'ou A=j.1(a,b)nV(GI)I+n2; 1.1(a,b)nV( G,)I = A- n2 et le second membre de cette egalite est independant de l'arete {a, b} deG lo done VFE cg2( GI), AI(F) est constant egal a Al = A- n2.

En echangeant les roles de GI et G 2, on voit que A= Al + n2 = A2+ nl. Si a E V( GI) etb e V( G 2 ) , alors .1(a, b) =.1 1(a) U .12(b), d'ou A= k, + k2 • La condition (b) est satisfaiteavec les relations:

AI + n2 = A2+ nl = k, + k2.

(ii) Si la condition (b) est satisfaite, il est clair, d'apres ce qui precede, que la condition(a) est satisfaite.

(iii) Des relations AI + n2 = A2+ nl = k, + k2, nous tirons: n2- k2= k, - AI et nl - k, =k2 - A2. Remplacons k; et Ai par leur valeur:

d'ou, apres simplification:

(n2-r2)(r2-t2) tl(rl-tl)(nl-rl )

r2 rl(rl-1)(nl-rl)(rl-t l ) t2(r2-t2)(n2- r2)

rl rir2-1)

De ces relations, nous tirons: 1=[t2/(r2-1)][td(r,-l)]. Comme t2~r2-1, t,~r,-l,

nous obtenons t2= r2- 1 et t l = rl -1. Dans ces conditions t = r -1.

PROPOSITION 4.3. Soient G; (i = 1,2) des graphes et G = GI V G 2. On a R( G) = R( GI) V

R(G2 ) .


PREUVE. Elle est immediate.

263

PROPOSITION 4.4. Soit G un graphe qui verifie (H). On suppose qu'il existe une partitionde V(G)=AuB telle que Bc.1(A). Alors G=G(A)vG(B) et G(A), G(B) oerifient(H), ou bien I'un des deux est complet et l'autre oerifie (H).

PREUVE. Si G(A) et G(B) ne sont pas des graphes complets, on applique la proposition 4.2. Comme G n'est pas un graphe complet, G(A) et G(B) ne peuvent pas etre to usles deux complets. Si G(B) est complet, alors G(A) n'est pas complet et verifie (H). Siles parametres de G sont (n; r, t), les parametres de G(A) sont (n -IBI; r -IBI, t -IBI).

PROPOSITION 4.5. Soient Gun graphe qui oerifie (H) et A une composante connexe deG. Alors G = G(A) v (G( V( G) - A).

PREUVE. Comme A est une composante connexe de G, on a V( G) - A c .1(A). Nousappliquons la proposition 4.2.

La proposition 4.2 montre comment renverser la procedure de la proposition 4.5. Enparticulier, nous avons:

PROPOSITION 4.6.(I) Soient G un graphe qui oerifie (H), de parametres (n; r, t) et E un ensemble de

cardinal e disjoint de V( G). Soit G(E) le graphe complet construit sur E. Alors G v G(E)oertfie (H), de parametres (n+e; r+e, t+e) etEcR(GvG(E)).

(2) Soit (r, t) un couple d' entiers uerifiant t ~ r - l. Alors il existe une infinite de graphesG qui oerifient (H), ayant r, t parmi leurs parametres.

PREUVE. (I) Elle est immediate d'apres ce qui precede.(2) Soit G 1 un graphe qui verifie (H), de parametres (!V( G1)1; r - t, 0). Soit E un

ensemble de cardinal t disjoint de V( G 1) . On appelle G(E) le graphe complet construitsur E. Alors le graphe G = G(E) V G1 verifie (H), de parametres (I V( Gt)1+ t; r, t). Commeil y a une infinite de choix pour GJ, il existe une infinite de graphes G repondant a laquestion.

Par exemple, il existe au moins un graphe G ayant comme parametres(95;5,2):IR(G)I=2 et le graphe G(V(G)-R(G)) verifie (H) de parametres (93;3,0).

II semble que le probleme soit ouvert de savoir s'il existe un graphe G fortementregulier, verifiant (H) et de parametres (95; 5, 2).

PROPOSITION 4.7. Soit Gun graphe qui uerifie (H), de parametres (n; r, t). On supposeque l' on a la decomposition de G:

(I)

ou chaque Gi est connexe (I ~ i~ u). Alors:(a) Pour I ~ i ~ U, G. oerifie (H), de parametres (n i ; ri , tJ.(b) On pose ~= IR(G)I. On a les relations:(i) ut=(u-l)r+(L::~ tJ+~,

(ii) si u ;=.: 2, r~ (u / u - I) t, r~ 2 t et u ~ r/ r - t.(c) La decomposition (I) de G est unique.

264 F. Zara

PREUVE. (a) La decomposition (1) de G est unique puisque c'est Ie decompositionde G en union de ses composantes connexes, G(R ( G» etant la reunion de toutes lescomposantes connexes de G, de cardinal I.

(b) D' apres la proposition 4.2, nous avons les relations:

t =(iIU ri ) + ~ +{,.=1i,<j

et pour I ~ i ~ u, r, - t, = r - t.De (3), nous deduisons

(2)

(3)

done, en tenant compte de (2) :

U(t-{)=(u-l)(r-{)+(J~ ~) .

De la nous obtenons (i ):

(

j - U )

ut= (u-l)r+{+ j~1 tj •

De (i) il resulte aussitot que ut;;;'(u -I )r, d'ou r~[u/(u-I)]t si u;;;.2. De plus [u/ (uI)]~2, done r~2t et enfin u~r/(r-t ).

COROLLAIRE 4.8. Soit G un graphe qui oerifie (H ), de parametres (n; r, t) et R( G) = 0 .Alors si r;;;' 2t + I, G est connexe.

PREUVE. C'est clair d'apres ce qui precede.

Nous avons maintenant assez de resultats pour classifier les graphes G qui verifient(H) , de parametres (n; r, r -I).

PROPOSITION 4.9. Soit Gun graphe qui oerifie (H), de parametres (n; r, r-I). SoitC = {a], . . . , ar } E eg. Pour I ~ i ~ r, on pose Ai = r(a;) u {ail. Alors G(A;) est discret etG =G(A]) V G(A2) v : .. v G (A r ) .

Reciproquement, soient E un ensemble et '1fJ une partition de E. On munit E d 'une structurede graphe G par: a et b sont adjacents s' ils sont dans des ensembles dis tincts de la partition.Alors G oerifie (H), de parametres (lE I; r, r - I) si r = 1'1fJ1 .

PREUVE. (a) Soient i un entier verifiant I ~ i~ ret a un element de Ai-{aj. Nousavons .1(a ) nC=C-{aj puisque t=r-l. Si bEAi-{aj, bo=a et si bE.1(a), alorsG ((C-{ai} )u{a,b}) est un sous-graphe eomplet de G de cardinal r+I, ee qui estimpossible, done b e r (a ) et G (A i ) est un sous-graphe diseret de G. On a Ia partitionde V( G ): V( G) : V( G ) = LJI ". i ". r A, En effet, si b e V( G ) - C, 1.1( b) n ci = t = r-I doncil existe un unique a dans C tel que C = {a} u (.1( b) n C ). Comme be C, b e T(a ).

Soient maintenant i 0= j, b e A i> C E Aj • Nous pouvon s supposer que b et c ne sont pasadjacents. Nous avons C= {a j=C n.1 (b ), done D={b} u (C-{aj)E ~(C) et a; ED.


Comme 1.1(c)n D I= r - : et aje.1 ( c), nous voyons que bE.1 (c )nD:bE.1 (C) et G=G(A 1) v G (A 2 ) v ' .. v G (A. ).

La reciproque est claire.

COROLLAIRE 4.10. Soit Gun graphe qui oerlfie (H), de parametres (n; r, r-I).(a) G est regulier si et seulement si 3s E N tel que Vi, IAil= s. Dans ces conditions, G estfortement regulier (si r > 2).(b) Les deux conditions suivantes sur G sont equioalentes:(i) G est regulier et Vi, IAil = s.(ii) G uerifie (H), de parametres (n; s,O).

PREUVE. (a) Si G est regulier, alors Vi(1:s; i:s; r), Va E A i:

k = 1.1 (a)1 = I IAJl~J:!Gr

j#"i

II en resulte imrnediatement qu'il existe un entier s tel que, Vi, IAil = s: on a s = n] r.Supposons qu'il existe un entier s tel que Vi, jAil= s. Si a E Ai, alors 1.1(a)1=

L ""j ""r. j >'i IAjl, donc 1.1 (a )1 = (r -I)s qui est independant de a, done G est regulier.Supposons G regulier. Le meme raisonnement que ci-dessus montre que si a E V( G),

b e .1(a) alors 1.1(a, b )1 = (r-2)s.Enfin si c E .1(a ), alors .1(a, c) = .1(a ) = .1(c ) et k = 1-', done G est fortement regulier.

(b) C' est imrnediat, grace aux propositions precedentes.

Les graphes G verifiant (H), de parametres (0 ; r, t) avec t E {O, r -I} seront ditsdegeneres.

Les resultats precedents motivent la definition suivante:

DEFINITION 4.11. Soit Gun graphe qui verifie (H).(1) On dit que 'G est irreductible' si G( V( G) - R ( G)) est connexe.(2) On dit que 'G est fortement irreductible' si G est connexe.II est clair que si G est fortement irreductible, alors G est irreductible.

5. LES m-ExTENSIONS

Soit G Ie graphe de collinearite d 'un espace polaire. Soient a et b deux elementsadjacents de G. Dans l'espace vectoriel associe, nous avons: (a, b)l. = (a, b)EB l¥, ou West un sous-espace vectoriel non degenere. Soit c une droite quelconque ~ a de (a, b). II

-est clair que (a, b)=(a, c), done .1(a)n (.1 (b)u{b})=.1(a)n (.1 (c )u{C}):CER(.1(a, b)).

Pour pouvoir analyser la situation precedente, nous nous placons tout d'abord a' l' etageau-dessus ': si a E V( G ), nous etudions R( Ga ) .

(A) ETUDE DE R( Ga )

DEFINITION ET NOTATION 5.1. Soient Gun graphe et a un sommet de G. On posea=R(Ga)u{a}. Les elements de a s'appellent les 'associes' de a.

LEMME 5.2. Avec les hypotheses et notations precedentes, on a

b E a~r(b) c r(a ).

266 F. Zara

PREUVE. Si b=a, on a r(b)=r(a) . Si bER(Ga) alors bE.:1(a) et'v'c E.:1 (a)-{b} ,c E .:1 (b), done .:1(a) - {b} c .:1(b). II en resulte aussitot que .:1 (a) u {a} c .:1(b)u {b}, doner(b) c r(a) .

Supposons que b e V(G ) verifie r(b)cr(a). Alors .:1 (a )u{a}c.:1(b)u{b}. Si b » a,aE.:1(b ), done bEL1(a) et, si cE.:1(a)-{b}, cE.:1(b), done bER(Ga): b e ii.

II est clair, d'apres ce qui precede, que , pour tout sommet a de G, R( G) c ii .Le but de ce qui suit est de montrer que si G verifie (H) et R( G) = 0 , alors la relation

d'association est une relation d'equivalence. Ensuite, nous montrerons que si G estfortement irreductible, toutes les classes d'equivalence ont Ie rneme cardinal, ce qui nouspermettra de caracteriser les espaces polaires.

N OTATION 5.3. Soit Gun graphe qui verifie (H), de parametres (n; r, t). Si a E V( G),b e r(a), on pose F(a, b) = {FIF E Cf.6, et Fe .:1 (a, bn.

LEMME 5.4. Avec les hyotheses et notations 5.3, F( a, b) est I'ensemble des supports descliques de G(.:1(a, b)) et G(.:1(a, b)) oerifie AI.

PREUVE. Soit G(F) une clique de G(.:1(a, b)). Comme Fe .:1(a ), 3C E Cf.6 (a ) tel queFe C. On a Fe C (\ .:1 (b) car Fe .:1 (b), done IFI = t et FE F(a, b) .

Soit F E F(a, b) , alors IFu {a}l = t + let G(Fu {an est complet done 3! C E Cf.6 tel queFu {a} c C. On a Fe C (\ .:1 (b ) et, comme IFI = Ic(\.:1(b)1 = t, on obtient F= C (\ .:1(b):G (F ) est une clique de G(.:1 (a, b)).

PROPOSITION 5.5. Soit G un graphe qui oerifie (H) . Soient a E V( G) et b e r(a). Ondefinit une application:

Pab : Cf.6(a )~F(a,b): C~C (\.:1(b) .

Alors:(a) Pab est une bijection.(b) Wab = p;;~ 0 Pab : Cf.6 (a) ~ Cf.6 (b) est une bijection.(c) 'v' E composante connexe de 6, il existe un entier e tel que 'v'x E E, ICf.6 (x) I= e.

On appe//e Wab : Cf.6( a) ~ Cf.6 (b) la bijection canonique.

PREUVE. (a) Sipab( C1) = Pab(C2 ) = C1 (\ i1(b) = C2 (\ .:1 (b), alors {a}u Pab(C1) c C. (\C2 et I{a}u Pab(C1)1 = t + I, done C. = C2 et Pab est injective.

Soient FE F( a, b) et G( C) la clique de G contenant a et F. On a F = C (\ .:1 (b), donePab( C ) = F et Pab est surjective: Pab est une bijection.

(b ) et (c). C'est clair d'apres ce qui precede.

PROPOSITION 5.6. Soit G un graphe qui oerifie (H) et R(G)= 0 . Alors la relationd' association est une equivalence: a et b sont associes dans G si et seulement si F( a) = F( b).

PREUVE. Soient a E V( G) et b e ii. On a r(b) c r(a), et, comme R( G) = 0 , r(b) ¢ 0 .Soit x E F( b), alors x E F (a ) et, d'apres la proposition 5.5, il passe autant de cliques deG par a que par b. Comme toutes les cliques de G contenant a contiennent b, on aCf.6 (a ) = Cf.6( b ), done .:1(a)u{a}=.:1(b)u{b} et alors aEb:r(a) =r(b); la relationd'association est une equivalence.


DEFINITION 5.7. Soit G un graphe. On dit que G est un 'graphe en marguerite' s'ilpossede la propriete:

Va E V( G) - R( G), 3! G( C(a)) clique de G telle que a E C(a) et L1(a) = C(a) -{a}.

(M)Si IC(a)1 est independant de a dans V(G)-R(G), on dit que G est un 'graphe enmarguerite symetrique'. Dans ce cas si r = IC(a)l, n = IV( G)I et t = IR( G)I, on dit que Gest de type (n; r, t).

PROPOSITION 5.8. (1) Soit G un graphe en marguerite symetrique de type (n; r, t). AlorsG terifie (H), de parametres (n; r, t) et Ie nombre de cliques de G est (n - t)/(r - t).

(2) Soit G un graphe qui oerifie (H) de parametres (n; r, t). Si FE ce" Ie grapheG( F u L1 (F» est un graphe en marguerite symetrique, de type (A (F) + t; r, t).

(3) Si G est un graphe en marguerite symetrique de type (n; r, t), on a Aut G=s, x[Sr_t JSn-t/r-,].

PREUVE. Elle n'offre pas de difficultes.

La proposition suivante caracterise les graphes en marguerite symetrique parmi lesgraphes qui verifient (H).

PROPOSITION 5.9. Soit G un graphe qui oenfie (H), de parametres (n; r, t). Les condi-tions suioantes sur G sont equivalentes: .(I) G est un graphe en marguerite symetrique :(2) 3aE V(G), G a est un graphe complet;(3) 3aE V(G), 1L1(a)l=r-l;(4) 3aE V(G), 3bErca), G(L1(a, b» est complet;(5) 3aE V(G), 3bErca), 1L1(a,b)I=t.

PREUVE. Nous faissons la preuve selon Ie schema suivant:

(1)=>(2)¢:> (3)

'fl' V,(5)¢:> (4)

(1) Supposons la condition (1) verifiee. Comme t est determine, G, n'est pas complet.Soit a E V( G) - R( G). Par definition a est contenu dans une unique clique G( C) de Get L1(a) = C -{a}, done G; est complet.

(2) Montrons que les conditions (2) et (3) sont equivalentes, Si G; est un graphecomplet, cela signifie que L1 (a) u {a} est contenu dans une clique G( C) de G, doneC = L1(a) u {a}, d'ou 1L1(a)1 = r-1. Si 1L1(a)1 = r-l, soit C E ceCa). Nous avons C -{a} cL1(a) et Ic - {a}1 = r -1, done C - {a} = L1(a): G; est un graphe complet.

(3) Supposons la condition (2) verifiee. Si b e rca), comme L1(a, b) c L1(a)/ G(L1(a, b»est complet. La condition (4) est verifiee,

(4) Montrons que les conditions (4) et (5) sont equivalentes. Soient a E V( G), b e rca)tels que G(L1(a,b» soit complet. D'apres Ie Lemme 5.4, 1L1(a,b)l=t. Si 1L1(a,b1I=t,toujours d'apres le Lemme 5.4, it est clair que G(L1 (a, b)) est complet.

(5) Nous supposons que les conditions (4) et (5) sont verifiees. Soient a E V( G),bE rca) tels que G(L1(a, b» soit complet. Posons R = L1(a, b). D'apres Ie (4), IRI= t.

Nous savons que R u {a} est contenu dans une unique clique G( Ca ) de Get R = Ca nL1 (b). Montrons que par a il passe une unique clique. Soit C E ce(a), alors C n L1 (b) c R,done comme ces deux ensembles ont la meme cardinalite, C n L1 (b) = R. Comme {a} u

268 F. Zara

R e C, d'apres Ia remarque initiale C = Ca. Pour Ia meme raison, par b il passe uneunique clique notee Cb. Si {Ca, Cb} = Cf6, clairement, G est un graphe en margueritesymetrique,

Supposons que Cf6,r. {Ca, Cb}. Soit DE Cf6 = {Ca, Cb}. Nous montrons que ReD, ce quimontrera que R e R( G). Comme IRI = t, G( V( G) - R) verifie (H), de parametres (nt; r- t, 0): c'est une reunion disjointe de cliques, done G est un graphe en marguerite.

L'ensernble (.:1(a) n D) u {a} est contenu dans une unique clique de G, done (.:1(a) nD) u {ale Ca et .:1(a) n Dc Ca. Nous venons de montrer que DE 9.0 (Ca). Comme CbE9.0 (Ca), puisque Ca nCb = R, d'apres Ia proposition 3.3, D nCb e Ca done D <c, e R,mais, comme ci-dessus .:1 (b) n Dc Cb donc.:1(b) n Dc Cbn Dc R. Comme IRI = 1.:1(b) nDI, nous obtenons R = .:1 (b) n D et ReD.

PROPOSITION 5.10. Soient Gun graphe qui oerifie (H), de parametres (n; r, t) et a unsommet de V( G).

(I) On suppose que G n' est pas un graphe en marguerite,(a) sia eR(G), lal";;;inf(t,r-t);(b) si a e RiG), a=R(G) et lal,,;;;t.

(2) On suppose que G est un graphe en marguerite,(a) si a e R (G), IaI= r;(b) si a e Rt G), lal=t.

PREUVE. (1) G n'est pas un graphe en marguerite. Soient a E V( G) - R( G) et C E

Cf6( a), alors a e C. II existe, par hypothese, b e .:1 (a) - C, alors be a et a e .:1 (b) n C, done,comme 1.:1(b)nCI=t, nous obtenons lal,,;;;t.

Si a E R( G), T(a) = 0, done, par definition a/ E a si et seulement si a ' E R( G), nousobtenons ainsi a = R( G) et IR( G)I,,;;; t. Supposons que a n'est pas dans R( G): il existec dans T(a); alors an .:1 (c) = 0 et 1.:1 (c) n ci = t, done ae C -(.:1(c) n C) et lal,,;;; r- t,d'ou Ie resultat: lal";;;inf(t, r-t).

(2) Si G est un graphe en marguerite, nous avons IR( G)I = t, done si a E R( G), lal = t.Si a e RiG), a est contenu dans une unique clique G(C) de Get si bEL'-{a},

be R( G), T(b) = T(a) = V( G) - C; si b e R(G), T(b) = 0 e T(a) nous obtenons ainsia= C dans ce cas et Ia1= r.

PROPOSITION 5.11. Soit Gun graphe qui uerifie (H) et R( G) = 0. Les deux conditionssuivantes sur G sont equioalentes:(a) 3a E V( G), Ga est un graphe en marguerite;(b) VaE V(G), Ga est un graphe en marguerite.

PREUVE. II est clair que (b)~(a).

Supposons que Ia condition (a) satisfaite et que Ies parametres de G sont (n; r, t). Sit = 0, d'apres Ia structure de ces graphes, il est clair que (b) est satisfaite.

Supposons done t> O. Soit a E V( G) tel que Ga soit un graphe en marguerite. Si a/ E a,comme R( G) = 0, .:1 (a) u {a} = .:1 (a') u {a'], done Ga, est un graphe en marguerite. Soitb e .:1(a) - a. D'apres Ia structure de Ga, best contenu dans une unique clique de Ga,done G(.:1(a, b)) est complet. On a a E .:1 (b). Soit x E T( a) n.:1 (b) qui est non vide puisqueb e ii ; alors G(.:1(b)n.:1(a,x)) est cornplet puisque .:1(b)n.:1(a,x)e.:1(a, b), done,d'apres Ia proposition 5.9. Gb est un graphe en marguerite.

Comme t ~ I, G est connexe; on a Ie resultat d'apres ce qui precede.

Nous pouvons maintenant demontrer un des resultats important de ce travail.


THEOREME 5.12. Soit G un graphe qui oerifie (H) et fortement irreductible. Alors i1existe a E N* tel que Va E V( G), lal = a. De plus a dioise IV( G)I r et t.

PREUVE. Soient (n; r, t) les parametres de G. Si G est un graphe en marguerite,comme G est connexe, nous devons avoir t = 0 et dans ce cas a est de cardinal r pourtout a de V( G). Dans toute la suite, nous supposons que G n'est pas un graphe enmarguerite. Soient a E V( G) tel que lal soit minimum: Vx E V( G), lal~ 14

Posons a = lal. Si a = t, d'apres la proposition 5.10 et le choix de 'a, nous voyons queVx E V( G), Ixl= t et le resultat est vrai. Dans toute la suite nous supposons que a < t.Toute clique de Ga est determinee par la donnee de t - a +1 de ses points.

Soit b s: r(a), qui n'est pas vide puisque R( G) = 0. Soit G(A) un sous-graphe completde G(J(a, b», de cardinal Ltl> t-a+1. Comme a et b sont dans J(A),GA n'est pascomplet, done GA verifie (H), de parametres (A(A); r- t +a -1, a -1). Par a, il ne passedans GA qu'une seule clique (remarque precedente), Comme b e r(a) n J(A), a e R( GA),done, d'apres la proposition 5.9, GA est un graphe en marguerite. Soit c E A. PosonsA'=A-{c} qui n'est pas vide puisque a<t. Considerons GA':GA , verifie (H), deparametres (A(A'); r- t +a, a).

Montrons que GA, n'est pas un graphe en marguerite. Nous avons c E J (A'), A = A' u{c}, {a,b}cJ(A) et b e Tt ai, done, par c, dans GA, il passe au moins deux cliques etGA , n'est pas un graphe en marguerite.

Nous avons ac J(A') et si a l et a2 sont deux elements de a, ils sont associes dans GA ,

puisque r(a 1) = r(a2) implique r(al) n J(A') = T(a2) n .1(A'). Comme an R( GA ,) = 0,car b e r(a') n .1(A') pour tout a' de a, et comme la u R( GA)I ~ a (proposition 5.10),nous obtenons R( GA ,) = 0 et a est l'ensemble des associes de a dans GA ,. D'apres laproposition 5.11, Vx E J(A'), G(J(A') n .1(x» est un graphe en marguerite. En particulier,l'ensemble des associes de x dans GA , est de cardinal a.

Maintenantb E J(A'), 5c J(A') et tous les elements de 5 sont associes dans G A,. Onobtient ainsi Ibl~ a. D'apres Ie choix de a dans V( G), a ~ IhI. d'ou l'egalite Ibr= a.Comme G est connexe, nous avons Ie resultat.

L'ensemble V( G) est reunion de ses classes de conjugaison pour la relation d'association; comme elles sont toutes de cardinal a, nous obtenons a II V( G)I.

Soit G( C) une clique de G. Si a E C, il est clair que ac C done C est reunion declasses de conjugaison et air.

Soit x E V( G) - C, alors 1.1(x) n ci = t. Si a E J(x) n C, on a ac J(x) n C, done J(x) nC est reunion de classes de conjugaison et a It.

(B) LES m-ExTENSIONS

Nous allons maintenant definir un concept qui permettra d'analyser la structure de Ga

lorsque G est un espace polaire.

DEFINITION ET NOTATIONS 5.13.Soient Gun graphe et m un entier > 1. A tout a de V( G), on associe un ensemble Xa

et on suppose que:(1) VaE V(G), IXal=m.(2) Si a et b sont deux sommets distincts de G, X, n X b = 0. Sur l'ensemble U aE V(O) X a,

on met une structure de graphe de la maniere suivante: on dit que x et y sont adjacentssi x,e y et(a) aE V(G), {x,y}cXa ;

(b) x E X a , Y E X b et a et b sont adjacents dans G.Le graphe ainsi construit s'appelle la 'm-extension' du graphe G et se note mG.

270 F. Zara

Nous avons des applications c/J: G ~ mG : c/J (a) E X a, Va E V( G); c/J est un morphismeinjectif de graphes; t/J: mG ~ G: t/J(x) = a si x E X a; alors t/J est un morphisme surjectifde graphes: t/J est la projection canonique. II est clair que t/J 0 c/J = I Go On a aussi uneapplication 7]:~(V(G»~~(V(mG»:la m-extension; a Ac V(G), on associe mA=U a E A x, = 7](A).

PROPOSITION 5.14. Soient m un entier ~ I et G un graphe.(I) G est connexe si et seulement si mG est connexe.(2) G est regulier si et seulement si mG est regulier.(3) Si Get mG sontfortement reguliers, G n'est pas connexe.(4) Soient ml et m2 des entiers ~ I. On a miml G) = m2ml G.

PREUVE. (I) Supposons G connexe. Soient x et Y deux sommets adjacents de mG.Distinguons deux cas:I er cas: it existe a dans V( G) tel que {x, y} C X a. Comme G est connexe, il existe b E T (a)et, si Z E XI>, on a {x, y} c Ft z).2eme cas: x E X a, Y E X; et b e .1(a). Comme G est connexe, il existe une suite ao=a, at. ... , au = b d'elements de V( G) tels que a, E r(ai+ l ) pour O~ i~ u -1. Soient Xi E

X a,(1~ i~ u -I), alors, pour O~ i~ u -I Xi et Xi+l ne sont pas adjacents dans mG. Nousvoyons ainsi que mG est connexe. Si mG est connexe, comme t/J(mG) = Get comme t/Jest un morphisme de graphes, il est clair que G est connexe.(2) Supposons G regulier de valence k. Si x est un sommet de mG, il existe a dans V( G)tel que XEXa • Alors x est adjacent a tous les points de Xa-{x} et, si bE.1(a), x estadjacent a tous les points de XI>, done x est adjacent a m - I + km points et mG estregulier de valence m - I + km. Supposons mG regulier, de valence ko. Soit x E V( mG):it existe a E V( G) tel que x E X; D'apres ce qui precede, .1(x) = (X, -{x}) U b E .1( a ) XI>,done ko = m -I +ml.1(a)1 et 1.1(a)1 = (ko - m + 1)/ m: G est regulier.(3) Soient x et Y deux elements adjacents de mG. Distinguons deux cas:ler cas: aE V(G), {x,y}cXa; alors .1(x, y) = (Xa-{x,y}) U b E .1 (a ) X b d'ou 1.1(x,Y)I=m-2+ml.1(a)l·2eme cas: XEXa , yEXb et bE.1(a); alors

.1(x,y)=(Xa-{x})U(Xb-{y}) U XcCE.1(a,b)

d'ou !.1(x, y)1= 2(m - I) +ml.1(a, b )1.Nous en deduisons que dans G, qui a comme parametres n, k, I, A, f-L, k = A+1. De la

relation f-LI = k( k - A- I) nous deduisons f-L = 0 et G n' est pas connexe.(4) C'est clair.

Appliquons ce qui precede aux graphes qui verifient (H).

PROPOSITION 5.14. Soient m un entier > I et G un graphe.(I) G cerifie (H) si et seulement si mG oerifie (H). Si les parametres de G sont (n; r, t),ceux de mG sont (nm; rm, tm).(2) Si G est un graphe en marguerite symetrique, mG est un graphe en marguerite symetrique.(3) Si G est un graphe discret, mG oerifie (H) avec Ie parametre t = 0 et rectproquementtout graphe qui oerifie (H) avec t =0 est une r-extension d'un graphe discret.

PREUVE. (I) Pour montrer Ie (1), montrons plus generalement le resultat suivant:

LEMME 5.16. Avec les hypotheses et notations precedentes, l'application 7] induit unebijection entre ~(G) et ~(mG).

Graphes lies aux espaces po/aires 271

PREUVE. Soit C = {al' ... ' ar } un element de ee(G). Nous avons 77( C) = U' '''j '''r X a i•

II est clair que 77( C) est un sous-graphe complet de mG. Si y E V(mG) est adjacent atous les elements de 77( C), et si l/J(y)= b, b est adjacent a tous les elements de C. CommeCE ee(G), c'est impossible; done 77(C)E ee(mG) et 77 induit une application, notee ijentre ee(G) et ee(mG).

Comme pour tout C E ee(G), l/Jij( C) = C, ij est injective.Montrons maintenant que ij est surjective. Soient DE ee(mG) et xED. Posons l/J(x) = a

et montrons que X a c D. Supposons Ie contraire: soit y E X; - D, alors y est adjacent atous les points de X; n D et si ZED - X a , Z est adjacent a x, done si l/J( z) = b, bestadjacent a a dans G et alors y est adjacent a z. Dans ces conditions z est adjacent a tousles points de D. Comme DE ee(mG) nous avons une impossibilite et X; c D. PosonsD = U\ ';; j,", v X a, de telle sorte que si C = {al> ... ' av }, G(C) est un sous-graphe completde G. Si a est adjacent a tous les points de C et si z E Xm alors z est adjacent a tous lespoints de D, mais comme mG(D) est une clique de mG, c'est impossible. II en resulteque G( C) est une clique de G et ij( C) = D: ij est surjective: c'est une bijection.

Du lemme precedent resulte aussitot que G verifie Al si et seulement si mG verifieAI. Si les cliques de G sont de cardinal r, celles de mG sont de cardinal mr.(2) (a) Supposons que G verifie A2: 3t EN tel que VC E ee(G), Va E V( G) - C, 1.1(a)ncl= t. Soient C E ee(G), C ={al> ' Ur }, D= ij(C) =Ut",j",r X; .. Soient XE V(mG)-Det b e l/J(x). A10rs L1(b)n C = {al> ' at} par exemple, done L1(x) n D = U1",j,;;tX a i : mGverifie A2 et VDE ee(mG), Vx E V(mG) - D, 1L1(x) n DI = mt.

(b) Supposons que mG' veri fie A2: 3 toEN tel que VDE ee(mG), Vx E V( mG) - D,1L1(x) n DI = to.

Soient C E ee( G), C ={al> ... , ar } et b e V( G) - C. Si x E X b, alors X; n ij( C) = 0 etx est adjacent ~ to points de ij( C), car mG verifie A2, par exemple x est adjacent a tousles points de X a" 1:0;; i:o;; t. Dans ces conditions b est adjacent a al>... , at ou mt = to, etuniquement a ces points la de C, done G verifie A2.

(3) II est clair que G est un graphe en marguerite symetrique si et seulement si Gverifie (H), de parametres (n; r, t) et IR( G) I = t. Comme il est non moins clair que sia E R( G), alors X, E R(mG), nous avons IR(mG) 1= mt. D'apres ce qui precede, mG estun graphe en marguerite symetrique,(4) Si G est discret, no us avons deja remarque que G verifie (H), de parametres(I V( G)I; 1,0). Une r-extension rG de G verifie (H), de parametres (r] V( G)I; r,O).

La reciproque est claire.

EXEMPLES. Graphes de collinearite des espaces polaires. Si la dimension de I'espaceprojectif est d et si Ie corps de base est de cardinal q, Va E V( G), G, est une q-extensiond'un espace polaire dont l'espace projectif associe est de dimension d - 2.

Nous faisons maintenant Ie lien de ce qui precede avec la premiere partie de ceparagraphe.

PROPOSITION 5.17. Soit Gun graphe qui uerifie (H), de parametres (n; r, r). On supposequ'il existe un entier n;;;' I tel que Va E V( G), lal = m. Alors:(1) Sur V={ala E V( G)} on met une structure de graphe 0 de la maniere suivante:

a et b sont adjacents si a;6 bet b e L1(a).

(2) Le graphe 0 verifie (H), de parametres (nlm; rim, tim) et G= mO.

REMARQUE. 0 est efIectivement un quotient de G au sens ou I' a defini Aschbacherdans [1].

272 F. Zara

PREUVE. (1) Nous avons a ' E ii si et seu1ement si r(a) = r(a ') et T: V(G)~~(V(G»est une application, on peut done lui associer une relation d'equivalence 9ll! et 1esclassesd'equivalences sont les ii, a E V( G). On a V = V( G)I R.

Soient a E V( G), a ' E ii, b e V( G), b' E b. Si b e .:1(a), alors b e .:1 (a) u {a} = .:1 (a ') u {a'}.Comme aE.:1(b), de la meme maniere, on obtient b'E.:1(a ')u{a '}. Done si bE.:1(a),ii ;i:. b, alors Va' E ii, Vb' E b, on a b' E.:1 (a ') et la relation ii et b sont adjacents dans Vestbien definie, II est clair que Ivi = n] m.

(2) L'application 7T: a ~ ii: V( G) ~ V induit un morphisme surjectif de graphes:

7T(a) E.:1(7T(b»~a E .:1(b),

7T(a) E r(7T(b»~aE r(b).

II est clair que les cliques de G sont les images par 7T des cliques de G, elles ont donetoutes le meme cardinal rlm et G verifie AI.

Enfin la verification de A2, pour G n'offre pas de difficultes: G verifie (H), de parametresinl m ; rim, tim).

COROLLAIRE 5.18. Soit G un graphe qui oerifie (H) et fortement irreductible. Soita E V( G). On suppose que liil = m. Alors:(1) Vx E V( G), Ixl = m.(2) II existe un graphe G 1 qui oerifie (H) et fortement irreductible tel que G = mG 1•

De plus si y E V( G 1) , on a Lvi = 1.

PREUVE. Cela resulte immediatement du theoreme 5.12 et de la Proposition 5.17.

Nous pouvons maintenant donner une caracterisation des graphes de collinearite desespaces polaires, Plus generalement un graphe G est un T-espace, au sens de Higman,s'il existe une famille .2 de sous-graphes complets de G, telle que la propriete suivantesoit satisfaite:

V/E.2, VaE V(G)-I, 1.:1(a) nil E{O, 1, Iii}.

G est un espace polaire (abus de Iangage pour G est le graphe de collinearite d'un espacepolaire) si G est un T-espace tel que V/E.2, VaE V(G)-I, In.:1(a);i:. 0.

LEMME 5.19. Soient Gun graphe qui uerifie (H), a E V( G) et b e .:1(a).(1) Si IiiI= I, b I E R ( Ga,b)~ .:1 (a, b) u {a, b} = .:1 (a, b ') u {a, b '}.(2) Si liil = IbI = 1, R( Ga,b) = R( Gb,a)'

PREUVE. (1) Soit b ' E R( Ga,b)' Comme R( G a) = 0, nous avons .:1 (a) n (.:1 (b) u {b}) =.:1(a)n(.:1(b')u{b'}), done .:1 (a, b)u{a, b}=.:1(a, b')u{a, b'}. Soit b'E V(G)-{a, b} telque (1): .:1(a, b) u {a, b} = .:1 (a, b ') u {a, b'}. Comme b' e {a, b}, b ' E .:1 (a, b) et (1) s'ecrit:

.:1(a) n (.:1(b) u {b}) = .:1(a) n (.:1 (b ') u {b'}), done b' E R( Ga,b)'(2) Soit b' E R( Ga,b)' Comme liil = I, nous avons

.:1 (a, b) u {a, b} = .:1 (a, b ') u {a, b '},

done .:1 (a, b)u{a, b}c (.:1(b)u {b}) n (.:1(b')u {b'}) = .:1(b, b')u {b, b'}. Nous en tirons.:1 (b) n (.:1(a) u {a}) c .:1 (b) n (.:1 (b ') u {b'}). Comme R( Gb) = 0, nous obtenons.:1(b) n (.:1 (a) u {a}) = .:1 (b) n (.:1 (b') u {b '}), d'ou .:1 (b, a) u {b, a} =.:1(b, b') u {b, b '}: b' ER( Gb,a)' Par symetrie, nous avons aussi R( G b.a) C R( Ga,b), d'ou l'egalite R( Ga,b) =R( Gb,a)'


THEOREME 5.20. Soit G un graphe qui verifie (H), de parametres (n; r, t). On supposequ'il existe un graphe G, oerifiant (H) de parametres (n\; rio t\) et R( G\) = 0 et un entierm ~ 2 tels que Va E V( G), Ga soit isomorphe aune m-extension de G\.

Si a e V(G), bE<1(a), on pose L(a, b)={a, b}uR(Ga,b) et2={L(a,b)\{a,b} estunearete de G}. Alors:(1) (G, 2) est un r-espace.(2) On a t,,;;;; r\ et m e (r\-I)/t\.(3) On a l'equicalence des deux conditions:(a) t = r l

(b) (G, 2) est un espace polaire.Si ces conditions sont satisfaites, (G, 2) n' est pas degeneree, ni un quadrangle generalise

et m est une puissance d'un nombre premier.

PREUVE. (I) VaE V(G), G; est une m-extension, done VbE<1(a), IR(Ga,b)l=m-Iet on obtient IL(a, b)1 = m + 1. On a R( G I ) = 0, done Vx E V( G), R( Gx ) = 0.

D'apres Ie Lemme 5.19 nous avons L(a, b) = L(b, a) et si c E L(a, b) -{a, b}, <1 (a, b) u{a, b} = <1 (a, c) u {a, c}. Si x E L( a, b) - {a, b, c}, <1 (a, b) u {a, b} = <1 (a, x) u {a, x} =<1 (a, c) u {a, c} donc x E R( Ga,c)c L(a, c).

Nous obtenons ainsi L( a, b) c L( a, c) et, comme ces deux ensembles ont m + I elements,L( a, b) = L( a, c). Si c et d sont deux elements distincts de L( a, b), alors L( a, b) = L( a, c) =L(c, a) = L(c, d). Doncsi x est adjacent adeux points de L(a, b), on a L(a, b) c <1(x)u {x},d'ou Ia relation:

Vx E V( G) - L(a, b), 1<1(x) n L(a, b)1 E {O, 1, m + I}.

Par definition d'un r-espace, (G, 2) est un r-espace.

(2) Soient a e V(G) et CE C€(a). On a

C = {a}u ( igl

(L(a, bJ -{a})

ou {b 1o •• • , brJ est un systeme de representants des classes d'associes contenues dans C.Soit x e Tt as; on a 1<1(x)nCI=t et ViIL(a,bJn<1(x)I";;;;I, done t e.r.. Comme t=

mt, + 1, nous obtenons m e (r\ - 1)/ t l •

(3) Si t = r10 il est clair que Vi, IL(a, bJ n <1(x)1 = 1, done, par definition, (G, 2) est unespace polaire.

Si (G, 2) est un espace polaire, Vi.IL(a, bJ n <1(x)1 = I, done t = rio Comme R( G I ) = 0,Va E V( G), R( Ga) = 0 et, dans ces conditions R( G) = 0: (G, 2) est non degenere.

D'apres Ia classification des espaces polaires de rang ~3, nous savons que m = IKI ouK est Ie corps sous-jacent, donc m est une puissance d'un nombre premier. (Dans lesespaces polaires de rang 2, on a t = 1).

REMARQUES 5.21.(I) Avec les hypotheses et notations precedentes, nous avons 2,,;;;;m";;;;(rl-l)/t1o donerl ~ 2t l + I. D'apres Ie corollaire 4.8, 0 1 est connexe.(2) De meme, comme r=rlm+l, t=tlm+l, nous avons r-2t+l=m(r\-2t\) doner-2t + I ~ m ~2 et r~2t + 1. Comme R(G) = 0, 0 est connexe.(3) Nous allons voir dans la proposition suivante comment diminuer les hypotheses duTheoreme 5.20.

EXEMPLE. Soit G un graphe affine orthogonal de parametres (qZm; qm, qm-I) avecq>2.

274 F. Zara

Si a E V( G), par exemple 0, alors Go a comme ensemble de sommets l'ensemble deselements singuliers de E - {O}, x et y E .1(0) etant adjacents si et seulement si ils sontdistincts et orthogonaux. Dans ces conditions il est clair que Go est une (q -I)-extensiondu graphe G1 assode a l'espace polaire correspondant a la forme quadratique Q.

Les parametres de G 1 sont:

(q m_I)(qm-I + I). qm -1 qm-I_l) _ .

...:..-=------'-..:....:...--~, , - (nl' rl> tl)'q-l q-l q-l

Ici nous avons t = «:' < rl = (qm -I)/(q -I), done G est un r-espace qui n'est pas unespace polaire.

Terminons ce paragraphe par une generalisation du Theoreme 5.20.

PROPOSITION 5.22. Soit G un graphe qui oerifie (H ) etfortement irreductible. On supposequ'il existe un entier m~ 2, a E V( G) et bE .1(a ) tels que(a) lal = 1(b) IR(Ga,b)!=m-1.Alors les conclusions du Theoreme 5.20 sont vraies.

PREUVE. D'apres Ie Theoreme 5.12, Vx E V( G), Ixl = let VCE .1(a ), IR( Ga,c)!= m-1.D'apres le lemme 5.19, VC E .1(a), R( Ga.c) = R( G c.a)' Soient x E V( G) et y E .1(x).

Si x E .1(a), d'apres les remarques precedentes, IR (Gx.~)I= m - I, done, comme Ixl == 1,IR( Gx,y)I= m -1.

Si x E r(a), comme G est de diarnetre 2, 3 C E .1(a, x), done

11 en resulte aussitfit que Vx E V( G), G; est une m-extension. Nous pouvons doneappliquer Ie Theorerne 5.20.

6. CONNEXITE DE 0 ET REGULARITE

Le but de ce paragraphe est de donner les relations qui existent entre la connexite deo et la regularite de G.

THEOREME 6.1. Soit G un graphe qui oerifie (H) et fortement irreductible. Alors, pourtout sommet a de G, G; est irreductible.

PREUVE. Soient (n; r, r) les parametres de G. On choisit G fortement irreductibleavec un plus petit t possible tel que la conclusion soit fausse:

3aE V(G), Ga n'est pas irreductible,

11 existe done des so us-ensembles AI et A 2 de .1(a) qui possedent les proprietes:(a) .1(a)=R(Ga)uA1uA2•

(b) A2 e .1(A 1) • .

(c) G j= G(A j ) verifient (H), de parametres ('Ail; r; tJ et R(GJ= 0 (i= 1,2).Nous arrivons aune contradiction en quelques etapes.

(A) VXE V(G), Ixl= 1;

En effet, com me 0 est connexe, Vx E V( G), Ixl = lal = IR( Ga)1 +1. D'apres la Proposition 5.17, G est une /al-extension d'un graphe G. qui verifie (H), de parametres(I V( G)lIlal; r/lal, tllal) et 0 1 est connexe. Nous avons un morphisme de graphes 4>: G~


G. : x -.+ x et cP(.1(a» = .1(cP(a)) . Nous obtenons .1(cP(a)) = cP(A.)v cP(A2), G.(cP(A»n'est pas complet pour i= I, 2 et cP(A2)c .1(cP(A.».

D'apres Ie choix de G, nous avons une impossibilite si tllal< t done lal = I, d'ou tousles resultats,

(B) Nous avons les relations:

'='. +'2+ I,

(C) Soit C E cera) alors C = (C n A.) u (C n A2 ) v {a} ou G( C n AJ est une cliquede G, pour i = I, 2.

Reciproquement, si G(CJ est une clique de Gj(i=I,2), alors C={a}vClvC2 estun element de ee(a).

(0) Soit b e Ftai. II existe des entiers aj (i= 1,2) tels que si G(Cj) est une clique deG; on ait 1.1(b) n cjl = aj et a. +a. = t.

Comme G est connexe, R (G) = 0, done r( a) ,e 0 et il existe bien un element b dansr(a).

Soit, pour i=l, 2, G(Cj ) une clique de G j • Comme b e Tt a), beC={a}vC.vC2,1.1(b)nCI=I.1(b)n(CluC2)1=1.1(b)nC.I+I.1(b)nC21 Posons aj=I.1(b)nCjl (i=1,2). II est clair que a. + a2= t. Nous avons a2= t - ah done, lorsque G( C2) varie dansl'ensemble des cliques de G2,1.1(b)nC21 ne depend pas de C2:al et a2 ne dependentque de b.

(E) Pour i = I, 2, tj + 1< a j< 'j. Nous montrons d'abord que a, < 'i-(E1) Nous procedons par l'absurde et nous supposons par exemple que a. =

,. :Clc.1(b). D'apres le (0), pour toute clique G.(C;) de Ch nous avons C ;c.1(b),done, comme A. est la reunion de toutes les cliques qu'il contient, Al c .1(b).

Nous avons montre Ie resultat suivant:

Soit x E Ft a), les conditions suivantes sont equi valentes:

(a) AI c .1(x); (**)

(b) 3 C I E ee(G.) tel que C I c .1(x) .

(E2) Toutes les cliques de G(.1(a, b» sont de cardinal t et nous avons Al C .1(a, b).Nous obtenons ainsi une partition de .1(a, b): .1(a, b) = Al U (A2n .1(a, b»), toutes lescliques de G(A2n.1(a,b)) etant de cardinal t-'2=tl+1. Soit G(E) une clique deG(.1(a, b)). Posons E I = E n Ah E2= E n A 2{] .1(a, b). Pour des raisons de cardinalite,il est facile de voir que G(E.) est un clique de G. et que G(E2) est une clique deG(.1(a, b)nA2).

(E3) .1(b) v {b} cAl U .1(A I ) .

Soient y E .1(b) - A. et G(D) une clique de G contenant b et y. Alors a e D puisquea e Fibv: de plus G(.1(a)nD) est une clique de G(.1(a,b)), done, d'apres (E2) ,G(.1 (a, b») contient une clique de G. et y est adjacent a tous les points de cette clique.

Si y E .1(a ), alors yEA2c.1(A.).Si y E r( a), (**) montre que AI c .1(y), ou encore que y E .1(AI)' Nous venons de

montrer que .1(b)-Alc.1(A I ) . Comme bE.1(AI ) , nous avons Ie resultat .1(b)v{b} cAl U .1(AI ) .

(E4) G(.1(AI)) verifie (H), de parametres (1.1(AI)I; ' 2+1 , t2+1), et G(Alv.1(A.))

verifie (H), de parametres (IAII +1.1(A.)I;" t).Soient G(D I ) une clique de G(.1(A.)) et G( C t ) une clique de G(AI ) , alors D I c.1( C.),

done G( C. u D.) est un sous-graphe comp1et de G et il existe une clique G( C) de Gcontenant C. v D 1•

276 F. Zara

Si C. u D , ¥- C, il existe x E C - (CIU D.).Si x=a, alors aEL1(A I ) , D.cL1(a), mais G(D.) est une clique de G(L1(A,)), done

a E D. contradiction.Si x E L1 (a), comme x e AI dans ce cas puisque G. verifie AI et C. C L1 (x), nous avons

x E A2C L1(A.), c'est impossible pour la meme raison que ci-dessus,Si x E rea) (**) montre que x E J(Ad et c'est impossible, toujours pour Ia meme raison.Done C = C\ U D I et to utes les cliques de G(L1(A I ) ) sont de cardinal r- rl = r2+ 1.De plus, il est clair, d'apres ce qui precede que G(A I u J(A2) verifie AI, toutes ses

cliques etant de cardinal r.Soient maintenant x E L1(A.) et G(D.) une clique de G(J(A.)) ne contenant pas x.Si G( CI) est une clique de GI, alors C = C. U D 1E r5, x e C, c, c J(x) /l C, !J(x) /l ci =

t, done IDI n L1(x)1= t - r l = t2+ I: G(L1(AI)) verifie A2.II est clair d'apres ce qui precede que G(A Iu L1(A I» verifie (H), de parametres

(IAII+1L1(AI)I; r, t).(E5) V( G) = AI U L1 (AI)' autrement dit, 0 n'est pas connexe.Supposons Ie contraire: V( G) ¥-AI U L1(AI). Soit G( C) une clique de G(A. U L1(A I),

qui ne contient pas a. Nous avons C = C. u DI, ou G( Cd est une clique de G I et G(D,)une clique de G(L1(A,)). De plus CI C L1(a). Soit x E V( G) - (AI U L1(A.)). Comme{a} U L1(a) c A, u L1(A.), nous avons x E rca).

Si C. c L1(x), d'apres (**), x E J(AI) contrairement au choix de x, done C t ¢ L1(x). Enparticulier J(x)/lC¥-L1(a)/lC. Soit dE(L1(X)/lC)-(J(a)/lC). Nous avons d er(a)/lL1(C.), done, d'apres (E3), {d}uJ(d)cAluJ(A.). Nous obtenons xEA.uJ (A. )-contradiction.

II en resulte aussitot que V( G) = A. U L1(A I). Mais alors 0 n'est pas connexe, contradic-tion. Done a, < ri (i = 1,2).

(E6) Nous avons a.+a2=tI, al<r.=t-t2-1=a.+a2-t2-1 done a2>t2+1.Nous voyons de meme que al> t, + I.(F) Pour i = I, 2, L1(a) u {a} = Ai u L1(A;). En effet, d'apres (E), pour toute clique

G( C;) de Gj (i = 1,2), nous avons L1( C;) c {a} u L1(a). Ceci implique en particulier, quepour i = 1,2, Aju L1(A;) c L1(a) u {a}.

D'un autre cote A2c J(A I ) et a E L1(A I ) , done J(a) u {a} = {a} u AI u A2cAl u J(AI ) ,

d'ou l'egalite L1(a) u {a} = AI U L1(A.)= A2U L1(A2) par symetrie.(G) Pour i = 1,2, OJ est connexe. Decomposons O. et O2 en leurs composantes

connexes:

Alors, comme R(Gj)=0, i=I, 2, nous avons, pour I",;,i",;,u:G(B;) verifie (H), deparametres (IBil; r:, t:) et R(G(B;)) = 0. Si nous posons B; =U2,.;j,.;uBj, alors toutes Iesproprietes demontrees dans Ies etapes precedentes pour (AI, A 2 ) sont valables pour Iecouple (B., B;). Soit b e Ft; a), alors, d'apres (E), L1 (b) n B I ¥- 0, car si C. E r5( G( B.»,nous avons t; + 1< IC t n L1(b)1 < r;.

Soit G( C.) une clique de G(B1) . Posons E = C./l J(b) et lEI =,8. Alors G E n'est pascomplet car a et b sont des sommets de GE , done GE verifie (H), de parametres (A(E);r-,8, t-,8).

Montrons que OE est connexe. Soit d Ia composante connexe de OE contenant a.Nous avons b e sd. Chaque O(Bj ) est connexe et, d'apres (E), pour 2",;, i",;, u, il existeajEBj/lr(b) done aiEd et Hjcd. Nous avons L1(b)n(L1(E)nB.)=0. En effet, siCE L1(E) n BI, alors E u {c} est contenu dans une clique G( CD de G(B.), 1L1(b) /l c;1 =,8,EcC;nL1(b) et IEI=,8, done ceL1(b)/lC':CEr(b). Nous obtenons ainsi L1(E)/lB)cr(b), done L1(E)/lB.cd. Nous venons de montrer que L1(a)/lL1(E)cd. Si xe


.d(E) - .d(a), alors x E r(a), done x e sd. Comme .d(E) = {a} u (.d(a) n .d(E)) u(r(a) n .d(E)), .d(E) = d et GE est connexe.

Nous avons a E .d(E). Considerons .d(a) n .d(E): nous avons .d(a) n .d(E) =(HI n .d(E)) U (LJ2";j";u B j), et chaque Hj est une composante connexe de G(.d(a) n.d(E)). De plus G(BI n .d(E)) est ou bien complet, ou bien une reunion de composantesconnexes de G(.d (a) n (E)). D'apres Ie choix de G, u = 2 et G(BI n .d(E)) est complet.Comme u = 2, nous obtenons B I = A I, B2 = A 2 et Gj est connexe pour i = I, 2.

(H) Contradiction finale. Nous gardons les notations precedentes: b e r(a); soit C I E

~(GI)' 1.d(b)nC.I=al' Posons E=.d(b)nCI. Dans la partie (G) nous avons montreque GE verifie (H), de parametres (>..(E), r-a., I-a,) et que GE est connexe.

Comme IEI=a,>11+1, .J(E)nAI=C(-E et .d(a)n.J(E)=(CI-E)uA2. II enresulte aussitot que R( G(.d (a) n .d(E))) = C I - E, done a a comme associes, dans G E,

outre lui-meme, tous les elements de CI- E.Posons a={a}uR(G(.d(a)n.d(E))). Nous avons lal=rl-al+1. D'apres le

Theorerne 5.12, GE est une (rl - al + I)-extension et (r- al)/(rl - al + 1)E~, (I - at)/(r] al+I)E~. Comme t=rl+t2+1 et r=rl+r2+1 nous obtenons r-al=r]-al+r2+1,I-a) = rl-al +t2+I, done

etrl

-----'-- E ~.

rs: a2 +1(1)

Comme Al et A 2 jouent Ie meme role, par syrnetrie:

et (2)

Soit maintenant G( C2 ) une clique de G2, alors C = {a} u CIu C2 est une clique de Gcontenant a et E. Posons .d(b)nC2=F, alors IFI=a2 et Fc.d(E). Comme GE est une(rl - at + I)-extension, Fest une reunion disjointe de classes d'equivalences pour larelation d'association dans GE, done a2/(r] - a] + I) E~.

Tenant compte de (1), nous voyons que (r2-a2)/(rl-a] +I)E~. Par symetrie nousobtenons:

ri : a2-"----=-- E ~ etrl-al + 1

(3)

Posons Zj = rj - a, (i = 1,2), alors h] = Z]/(Z2 + I) et h2= Z2/(ZI + I) sont des entiers nonnuls. En exprimant Zl en fonction de h, et h2 nous trouvons (1-h]h2)ZI=h](h2+ I ).Comme Ie deuximeme membre de cette egalite est >0, Ie premier membre l'est aussi:done 1- bih»>°et h lh2< 1. Comme h., h2E~*-nous avons une contradiction.

COROLLAIRE 6.2. Soient G un graphe que oerifie (H) etfortement irreductible et G(E)un sous-graphe complet de G. Alors GE est irreductible ou bien est complet.

PREUVE. Par recurrence sur lEI = e. Si e = I, c'est Ie Theoreme 6.1. Supposons e~ 2et la propriete vraie pour les sous-graphes complets G(E') de G verifiant IE'I~ e -1: G E ,

est irreductible s'il n'est pas complet.Soient G(E) un sous-graphe complet de G tel que GE soit non complet et a un element

de E. Posons E 1= E - {a}, alors GE , est un sous-graphe non complet de G et G E , verifie(H). Par hypothese de recurrence GE , est irreductible,

Si a E R( GE ,) , alors GE est irreductible.Si a ~ R( G E , ) , nous appliquons Ie Theoreme 6.1 a G(.d(E') - R( GE ,) ) pour voir que

GE est irreductible.

278 F. Zara

Nous allons maintenant retrouver des resultats obtenus par Blokhuis, Kloeks et Peter.

LEMME 6.3. Soit G une graphe qui oerifie (H), de parametres (n; r, t). Soient x et ydes sommets non adjacents de G, G (C) et G(D) des cliques de G qui oerifient:(a) yEC,XED;(b) IC n DI = t.On pose a=(n-r)/(r-t), 0J(C)={D;jI:O;:;:j:O;:;:a}, D=Dh 0Jy = {DjID jE 0J(C ), yED;}et 0J~ = 0J(C) - 0Jy- Alors:(a) 1.1(x)1 = r-I +L2.. i .. a (t -ID] n DiD·(b) 1.1 (x, y)1 = t +LDj€ !?iJy(C ) (t-ID1n D;D·

PREUVE. (a) Nous avons V(G)=Cu(lJ, .. j",a(Dj-C», done .1(x) =(.1(x) n C) U (lJ1 .. i e:« (.1(x) n (D;- C))). Comme.1(x) n C = C n D 1 par Ie ehoix de Cet D et eomme D1-{x}e Li(x), nous obtenons:

.1(X)=(DI-{X})UC..~a (.1(X)n(D j-C»).

D'un autre cote, eomme D;=(DjnC)u(D;-C) (1:O;:;:i:O;:;:a), nous avons .1(x)nDj=(.1(x)nDjnC)u(.1(x)n(Dj-C». Mais .1(x)nC=D1nC et .1(x)nCnD;=D1n

C n D;. Comme D 1 n D, e C, nous obtenons .1(x) n C n D; = D I n D; done .1(x) n(D; - C) = (.1(x) n Dj) - (D 1 n D j ) . II en resulte que:

.1(x) = (D1 - x) u( 0 [(.1(x) n D;) - (D1 n D;)]) (1)2 'lS;; I :Sia

d'ou1.1(x)1 = r-I + L (t -ID1 n DiD.

2~ i:S:;Q

(b) En utilisant la formule (1), nous obtenons:

.1(x, y) = (.1(y) n (D.-{x}»uC..Qa (.1( y) n [(.1(x) n D;) - (D I n Djm).

Soh D jE0Jy(C), nous avons .1(y)nDj=Dj-{y} car yED;, done, eomme XEny), .1(x) n .1(y) n D, = .1(x) n D;

Soit D; E 0J~(C), nous avons C n D, e .1(y) n D, car C -{y}e .1(y) et y n'est pas dansD; Comme Icn Djl = t = 1.1(y) n Djl, nous avons l'egalite C n D, = .1(y) n D; d'ou

.1(x) n .1(y) n D, = .1(x) n C n D, = D 1n D, d'apres le (a)

Nous obtenons:

.1(y) n [(.1(x) n D j ) - (D1n D;)] = .1(y) n .1(x) n D, - (D1 n D;) = 0

done:

d'ou1.1 (x, y)1 = t + L (t -ID1 n Djl).

D j € !?iJy(C )

COROLLAIRE 6.4. Soient mEN, (m < t), FE C(5m et F I E C(5m + 1 tels que Fe Fl. On poseF]=Fu{a}. SiaeR(GF ) , ona:

a(F.):o;:;: (a(F) - 1)(t - m) .r-t


PREUVE. Comme a e R( GF ) , G F n'est pas un graphe complet, done G F verifie (H),de parametres (A(F) ; r- m, t - m). Soient C E <e(F) tel que a e C et D 1E <e(F) tel quea e D1 et Ic II D.I = t. Nous appliquons Ie Lemme 6.3 a GF et aux cliques G( C - F) etG(D-F) de GF • Nous avons 1.1(a)II.1(F)I=A(F.)=(r-m)-I+Lz"'j",a(F)((tm) -I(D. II DJ- FI) et nous obtenons

a (FI

) =A(F.) - (r - m - I) :s:; (a (F) - I) (t - m) .(r-m)-(t-m) r-t

LEMME 6.5 Soit G un graphe qui verifie (H), de parametres (n; r, t). Soient C et Ddeux elements de <e tels que Ic II DI = t. Alors :

(I) 3kEN, vc«o-«: 1.1(x)I=k.(2) VyEC-D, 3,.,.EN, VxeD-C, 1.1(x,Y)I=,.,..

PREUVE. C'est clair d'apres Ie lemme precedent.

LEMME 6.6. Soit Gun graphe qui oerifie (H). Si 0 est connexe alors 0 est de diametre2.

PREUVE. On suppose que les parametres de G sont (n; r, t) et on choisit G avec Ieplus petit t possible tel que 0 soit connexe et 3a E V( G), 3b E .1(a), Ft a, b) = 0 .

Comme 0 est connexe, pour tout sous-graphe complet E de G, GE est ou bien complet,ou bien est irreductible (Corollaire 6.2). Montrons que Vx E V( G), Ixl = 1. Supposonsque Ixl = m ;;.2 alors G est une m-extension d'un graphe 0(, qui verifie (H), de parametres(nlm; rim, tim) et O. est connexe (Proposition 5.22). II existe un morphisme 4>: 0-+ g.eton a 1>(a)"r:. 4>(b) car sinon on aurait b E ii, donc f'(c) = r(b) = Ft a, b) = 0 et a E R(G)ce qui n'est pas car 0 est convexe.

Nous avons 1> (b) E .1(1)(a)) et r (1> (a), 1>(b)) = 0 comme on Ie verifie imrnediatement.Comme t] m < t nous avons une contradiction avec Ie choix de G.

Nous avons .1(a, b)"r:. 0, car sinon si .1(a, b) = 0, G({a, b}) serait une clique de G :r =2, t = I, mais dans ce cas 0 n' est pas connexe.

Soit x E .1(a, b), alors Gx verifie (H), de parametres (A(x); r - I, t - 1) et Ox estirreductible. On a {a, b} c .1(x) et .1(x) II Ft a, b) = 0, done Ox n'est pas connexe. D'apresune remarque faite plus haut R( Ox)"r:. 0 contradiction, d'ou Ie resultat: Va E V( 0),3b E .1(a), Ft a, b)"r:. 0: G est de diametre 2.

PROPOSITION 6.7. (Blokhuis et autres [8]). Soil 0 un graphe qui oerifie (H). Si 0 estfortement irreductible G est regulier.

PREUVE. (On suppose que les parametres de G sont (n; r, t) . Remarquons d'abordque si a et b sont deux sommets adjacents de G, alors 1.1 (a)1 =1.1 (b )1. En effet, d'apresIe Lemme 6.6, Tt a, b)"r:. 0 et nous avons Ie resultat d'apres Ie Lemme 6.4.

Si t = 0, nous avons deja vu que 0 est connexe et que 0 est regulier. Si t;;. I, 0 estconnexe et Ie resultat est vrai: G est regulier.

PROPOSITION 6.8. (Blokhuis et autres [8]). Soit G un graphe qui oerifie (H). Si 0 estfortement irreductible 3,.,. EN tel que Vx E V( 0), Vy EJ'(x), ,.,. =1.1 (x, y)l.

PREUVE. Soient (n; r, t) les parametres de G. Comme 0 est connexe, t < r - I.Soient x E V( 0), Y E nx). Posons ,.,. = 1.1 (x, y)l . Soit a E nx). Montrons que j, =

280 F. Zara

I ~ ( a, x)l. Pour cela, distinguons plusieurs cas:(l) aE~(Y). Soient G(D) une clique de G contenant a et yet G(C) une clique de Gcontenant x et rencontrant Den t points. Nous avons x E C - D et {a, y} c D - C. D'apresle Lemme 6.4 JL = I~(a, x)l·(2) a E r(y) et ~ (a, y) n r(x) ¥ 0. Soit b E~ (a, y) n r(x). Nous avons le diagramme:

x.

donc, d'apres le (l) , I~ (x, y)1 = JL = I ~ (x, b)1 et I~ (x, b)1 = I~ (x, a)1, d'ou le resultat,(3) aEr(y) et ~(a,y)nr(x)= 0. Done, dans ce cas ~(a,y)c~(x) car xe~(a,y) .

D'apres le Lemme 5.4 ~(X,y)=UFEF(X,Y ) F. Soient F un element de F(x, y) et G(C)[resp. G(D)] la clique de G contenant F et {x} (resp. F et {y}). Nous avons C n D = F =

C n ~(y) = Dn ~(x). D'un autre cote D n ~(a) c ~(a, y) c ~(x) done D n ~(a) cD n~ (x) et, comme ces deux ensembles sont de cardinal t, nous obtenons F = D n ~ (x) = D n~(a): F c ~(a). 11 en resulte que ~(x, y) c ~(a, y) c ~(x) n ~(y) = ~(x, y) d'ou l'egalite~(x, y) = ~(a, y). Soient F I E F(x, a), G(C.) [resp. G(D.)] la clique de G contenant F]et {x} (resp. F. et {a} ).

Nous avons ~(y)nClc~(x,y)c~ (a), done ~(y)nClc~(a)nCIet ~(y)nCI=~(a)nCI=FI' 11 en resulte que ~ (x,a)c~(y). Le merne raisonnement que ci-dessusmontre alors que ~(x, y) = ~(a, x) = ~(a, y).

Comme nous n'avons que les trois possibilites (l), (2) et (3), nous avons le resultat.Soient maintenant a E V( G) et b e Fta). Comme 0 est connexe, il existe une suite a,

(0~ i ~ v) d'elements de V( G) qui verifie: ao= x, av = a et pour 0~ i ~ v - I, aj Er(ai+l)'Dans ces conditions JL = I~(x, y)1 = I~(ah x)1= 1~(a2' al)1 = .. . = I~(av-h av)1 puis,toujours de la meme maniere I~(a, b)1 = 1~(aV-h a)1= JL.

COROLLAIRE 6.9. Soit Gun graphe qui oerifie (H) etfortement irreductible. On supposequ'il existe a E V(G) tel que lal= 1. Alors G estfortement regulier.

PREUVE. Soient (n; r, t) les parametres de G. Si t =0, G est fortement regulier maisVb E V( G) Ihl = r. Nous avons done t ~ 1.

D'apres le Theoreme 5.12, Vx E V( G), Ixl = I, done, d'apres le Theoreme 6.1, VXE V( G ),OX est connexe et, d'apres la Proposition 6.7 G; est regulier.

Soint a E V(G), b E ~(a). Posons A= I~(a, b)l. Comme Ga est regulier, VeE ~(a),

1~(a)n~(b)I=I~(a)n~(c)I=A. Soient XE V(G), Y E ~ (X) . Si aE~(x), d'apres ce quiprecede I~ (a, x)1 = A= I~ (x, y)1 en faisant jouer a x le role de a. Si a EJ'(x), il existec E ~(a, x) car G est de diarnetre 2. Alors I~ (a, c)1 = A= I~(c, x)l, puis, de la meme maniereA= I~ (x, y)l. Nous avons le resultat grace aux Propositions 6.7 et 6.8.

A titre d'application de ce qui precede, nous allons caracteriser les espaces polairespar leurs parametres parmi les graphes qui satisfont a~H) et fortement irreductibles.

THEOREME 6.10. Soit Gun graphe qui oerifie (H), de parametres (n; r, r). On supposeque G est fortement irreductible et qu'il existe des en tiers a et m, a ~ 2, m ~ 3 tels que

a m - lr=-

a-I'

am-I_It= , et n~r(am+I+I).

a-IAlors:(I) Si m ~ 5, G est Ie graphe de collinearite d'un espace polaire de rang m et a est unepuissance d'un nombre premier.


(2) Si m =4, et si a est une puissance d'un nombre premier G est Ie graphe de collinearited'un espace polaire de rang 4.(3) Si m = 3 et si a est une puissance dun nombre premier impair ou si a =2, G est Iegraphe de collinearite dun espace polaire de rang 3.

PREUVE. (I) Comme G est fortement irreductible, G est regulier. Comme (r, t) = I,Vx E V( G), Ixl = 1, done G est fortement regulier, II existe ainsi un entier s ~ 2 tel quen=r{I+[(r-l)(s-I)/t]} d'ou s-I=(n-r)t/r(r-I). lei no us avons r-t=a m- I

, rI=at et (n-r)/r=(n/r)-I~am+l, done s-I~am.

D'un autre coten-r=r(r-I)(s-I)r- t t(r- t) (~)~

a-I a m - 2

est entier. Comme (a, (am -1)/(a - I)) = 1, nous obtenons:

f3 E ~*, (I)

Pour tout X dans V( G), Gx verifie (H), de parametres (k; r-I, t - I) et Gx est regulier,En particulier G; est fortement irreductible, Nous avons k = at( 1+ f3a m-2); Ies parametresde Gx sont done

( (am-I_I) _ (am-I_I) (a m-

2 _1))a (1 + f3a m 2); a , a .

a-I a-I a-I

II existe un entier a qui ' divise a = (r - I, t - I) tel que Gx soit une a-extension d'ungraphe G 1 que verifie (H), fortement irreductible, de parametres (k/ a; (r- 1)/ a,(t - 1)/ a) = (n l ; r l s t l ) ; et Vy E V( GI ) , Iyl = I, done GI est fortement regulier.

Ainsi il existe un entier Sl tel que

[-'--(r",----l-_1.:....0.)(S--=-I_--,-I)]nl = rl 1+-

t1

et

S I _ I = '=--[k_----:(_r-~I)=](_t-----'-1)(r-I)(r-I-a)

f3a m- l(a m-2- I)

am-(a+l)a+a

par un calcui facile. Comme

f3a m- l(a m - 2-1)

am-(a+I)a+a

est entier, il en est de merne de

f3a m-3(a 2-(a + I)a +£1')

a m-(a+l)a+a

ou encore, en simplifiant par a - I:

(2)

est entier. Si a = a, A =0, t = t1 et, d'apres Ia Proposition 5.22, Ie resultat est vrai.Dans toute la suite, nous supposons que a ¥- a et nous derivons une contradiction.Comme ala, posons £1'= aa 1 ; aloes (2) devient

f3am-3a';'-3a(al-l)A = ----=---:------::--'-------.:-'~-'------;;---a[a m - 2a;, -t +a m 3a';'-2+ .. . +aaf+al-I]

282 F. Zara

mais (a" a m-2a;"-1 + ... +aoi+a.-I)= I done

(3am-3(at- l )B = _~_--,-----:.--:_~c..--""':-_----".-__

a m-20;"-t +a m-30;"-2+ .. . +aoi+ol-I

est entier. Soit d = (0',0\ -I). Nous avons 0'= da c.a, -I = d02 et (0'10 02) = I; nousobtenons:

C = dm-3 m-2(d I)m-I (d 1)2at 02+ + ... + at 02+ + 02

{3dm-3a;"-3d02B = -----=--."...--~----:.-~=-----"....--

d[d m- 3a;"-2(d02+ I)m-l + ... + at(d02+ 1)2+ 02]

mais (a" d m-3a;"-2(d02+ I)m-I + . . . + al(d02+ 1)2+ 02) = I done

{3dm-302

est entier. Utilisons maintenant l'hypothese m ~ 5. Nous avons

a 2d2(do + l?d m-30 d 20I<C< t 2 2_ 2~ ~ d'" 30';" 2(d02+ I)m-\ - a;"-4(d02+ I)m-3

ou encore (da2+ 1)2~ a;"-4(d02+ I)m-3~ d 202 mais cette inegalite est impossible en

nombres entiers >0.

REMARQUE. Si m = 4, l'inegalite I ~ C devient I ~ d 202/ (d0 2+ I) qui est toujourssatisfaite si d ~ 1.

(2) Supposons maintenant que m = 4 et que 0 = pU avec p premier. Alors 0'= pV avecv < u. Nous obtenons

(3pUpV(pU-V_I) (3pU(pU-V-I)A = --7'-'-~----'----r" + p2U + pU _ pV p3U-V + p2U -V+ pU-v _ I'

lei (pU,p3u -v+ p2u-v+ pu- V_I)=I, done D={3(pU-v_I)/(p3u-v+ p2u-v+ pu-V_I) est

entier; d'ou

pU-V _Iu-v < I,p

contradiction.(3) Supposons enfin que m=3. Nous avons [A-(r-2)/(r-t)]={3. Soient XtE V(G),X2E.::l(X\), F={X"X2} et X3E.::l(F)-R(Gp). Posons F'=Fu{X3}' D'apres Ie Corollaire6.4

done a(F')~a-2 puisque c'est un entier.Soient X4E .::l(F')- R( Gp.) et F"= F'u {X4}.Toujours d'apres Ie Corollaire 6.4, a (F") ~

(0 - 3)(0 - 2)/02< I, done a(F") =0 car c'est un entier.II en resulte que Gp " est complet.Montrons que a(F') =O. Supposons Ie contraire: a(F'),c O. Alors G(.::l(F') n .::l(X4)) =

G p" est complet et Gp. n'est pas complet: d'apres la Proposition 5.9, G p. est un grapheen marguerite; d'apres la Proposition 5.11, VyE.::l(F)-R(Gp), G(.::l(F)n.::l(y)) est ungraphe en marguerite.

D'apres Ie debut, nous savons que IR( Gp)1 = a -I, done G(.::l(F) - R( Gp)) verifie (H),de parametres (a 2+ a - a + (3a 2; a2+ a - a, 0 - a) et c'est une (a - a)-extension d'ungraphe G' qui verifie (H), regulier et de parametres «02+ 0 - 0'+ (3a2)/(0 - a); (a 2+ 0-


a)/(a-a), 1). Nous obtenons (a 2+a-a)/(a-a)EN, done a2(a-a)EN. Nous avonsa = r". a = pV avec v < u et p premier, done p2U / (pU - pV) = p2U-V/ pU-v -I EN. Ceci n'estpossible que si pU-v - I = I, done pU-v = 2. Comme p est impair nous avons uneimpossibilite, Done a(F') = O. Le merne raisonnement que ci-dessus montre que GF estun graphe en marguerite, done Gx, est une (t - I) -extension. Comme t - I = a, nous avonsIe resultat.

Si a =2, a = I et {3 ~ 4, done

A= (3(a-a) {3a2+a-1 5

n'est pas entier, Ie resultat est vrai dans ce cas.

PROPOSITION 6.11. Soit G un graphe qui oerifie (H), fortement irreductible et deparametres (n; r, t), ou

am_1r=-

a-I'

am-I

t=-a-I'

n = r[1 +a m-

I {3 ],

a et m sont entiers, a ~ 2, m ~ 3 et {3 E {I, a, a2, a I/2}, (si (3=a 1/ 2, on suppose que a est uncarre], Alors G est Ie graphe de collinearite d'un espace polaire de rang m.

PREUVE. D'apres le Theoreme 6.10, dont nous gardons toutes les notations, il suffitde montrer que l'entier

(3am-3(a-a)

A= m 1+ m 2+a a .. '+a-a

est nul. Si {3 = I ou si {3 = a, A < I, done A = O. Si (3= a",

am-I(a-a)A= a-(a+I)+A',

a m- l+a m-2+ .. '+a-a

ou A' est un entier. Si 'm ~ 4,

I a(a m-2+am-3 +... +a2)+(2a + 1)a - a(a + I)A = m -I m-2 .

a +a +"'+a-a

Si m =3,

A,=(2a+1)a-a(a+l)a2+a-a .

Si a < a, no us avons 0 < A' < I, c'est impossible et III encore a = a et A = O.Enfin si a = c2 et {3 = c, nous avons

nous obtenons encore A < I done A = O.Dans tous les cas nous avons la conclusion.

COROLLAIRE 6.12. Soit G un graphe qui oerifie (H) et fortement irreductible. Si lesparametres de G sont ceux d'un espace polaire, G lui-mime est un espace polaire.

PREUVE. C'est clair d'apres ce qui precede. Le seul cas non couvert par les resultatsprecedents est Ie cas m = 3, a est un carre: a = c2 et b = c3

• Dans ce cas A =

284 F. Zara

c3(c2-a)/(c4+c2-a). lei on a c v p", p premier, a v p" avec v~2u. Done

p3U(p2U _ pV) p3U(p2U-V -1)A = -=-,--=---;:--=--'-

p4U = r" _v" p4U-V +p2u-v -1 '

done, comme (p, p4U-V +p2U-V -1) = 1,2u-v

A'= Pp4U-V +p2U-V _ 1

doit etre entier. Ceci n'est possible que si A' = 0 puisque A' < 1, done 2u = v, a = a etnous concluons comme dans les cas precedents.

7. LES GRAPHES VERIFIANT t=r-2 ET CEUX VERIFIANT r~2t-l

Dans ce paragraphe, nous classifions dans une premiere partie tous les graphes verifiant(H) et t = r - 2. Dans une deuxieme partie, nous montrons que si un graphe G verifie(H) de parametres (n; r, t) est fortement irreductible et est tel que 7~ r ~ 2t -1, alorsc'est une m-extension d'un graphe G 1 qui verifie (H), de parametres (nlm; rim, tim)avec (rlm)-2= tim et fortement irreductible,

Si t = 3, r ~ 5 et si t = 2, r ~ 3 nous retombons sur des graphes connus.Partie [A]. Dans toute cette partie, nous faisons les hypotheses:

HYPOTHESES 7.1. G est un graphe qui oerifie (H), de parametres (n; r, r-2).

PROPOSITION 7.2. On a les hypotheses 7.1. On suppose en plus que G est fortementirreductible. Alors, pour tout sous-graphe complet G(E) de G oerifiant lEI ~ t, GE estfortement irreductible.

PREUVE. Nous procedons par recurrence sur r. Pour r = 3, t = 1 et si a E V( G), Oaest connexe puisque Ga verifie (H) de parametres (A(a); 2, 0).

Supposons le resultat vrai pour les graphes G' satisfaisant al'hypothese et de parametres(IV(G')I; r-l, r-3). Soient G(E) un sous-graphe complet de G, IEI~t et aEE. .

Nous savons que, comme t ~ 1 et 0 est connexe, Ga n'est pas complet (Proposition5.9), done Ga verifie (H), de parametres (A(a); r-l, r-3). Nous savons aussi que Gaest irreductible (Theoreme 6.1). Si Ga n'est pas fortement irreductible, il existe un entierm ~ 2 tel que IR( Ga)1 = m -1, done G est une m-extension et, comme (r, r-2) = 2, si rest pair et 1 sinon, nous voyons que r est pair et que m = 2: G est une 2-extension d'ungraphe G 1 qui verifie (H) et de parametres (nI2; r12, (rI2)-1). Dans ces conditions,nous savons que 0 1 n'est pas connexe (Proposition 4.9). D'apres la Proposition 5.14, 0n'est pas connexe contrairement al'hypothese, Done Ga est fortement irreductible. Nousavons E - {a} c .1(a) et IE - {a}1 ~ t -1. Par hypothese de recurrence G(.1 (a) n.1(E - {a})) est fortement irreductible, done, comme .1(a) n .1(E - {a}) = .1(E), GE estfortement irreductible,

COROLLAIRE 7.3. On a les hypotheses 7.1. Si G est fortement regulier, pour toutsous-graphe complet G(E) de G avec lEI ~ t, GE est fortement regulier.

PREUVE. Cela resulte aussitot de ce qui precede et du Corollaire 6.9.

LEMME 7.4. On a les hypotheses 7.1 et G est fortement regulier.(1) jL[= Ina, b)1, a E V( G), b e .1(a)] est un nombre pair et on pose jL =2u.(2) Pour que G existe, ilfaut que 2+u(r-2)lu(r-1)r.


(3) Si r;;;'4, uE{I,2} et Ji.E{2,4}.(4 ) Si r=3, uE{l,2,4} et Ji.E{2,4,8}.

285

PREUVE. (l) Nous avons la formule bien connue Ji. = 1- k +A+ 1. lei, avec les notations du paragraphe 3, Ji. = (s -1)(r - t)(r- t -1)/ t =2(s -1)/ t. Soit FE f(6, et soit O( C)une clique de 0 contenant F:C=Fu{a,b}. Nous avons, si xEL1(F):L1(x)nC=Fdone x e Ft a.by; si x e Ft a.by, alors x~C et L1(x)nC=F: nous venons de montrerque L1(F)=r(a,b)u{a,b}: IL1(F)I=Ji.+2. Mais OF verifie (H), de parametres (Ji.+2; 2, 0) et, comme OF est regulier, 21Ji. +2, done 21Ji.. Nous posons Ji. = 2u.

(2) Nous avons Ji. = 2u = 2(s -I)/(r - 2) done s = I + u(r - 2). La condition d'integralite

r(r-1)s(s-l)---"----=----'--------'- E Nt[r- t +s-I]

donneici

r(r-1)[1 +u(r-2)]u---"-----'-'------'------'-.:'- E N.

2+u(r-2)

Comme 1+ u(r -2) == -I mod (2+ u(r-2» cette condition equivaut aur(r -1)

----"----=--- E N.2+u(r-2)

(3) Soient m un entier, I ~ m ~ t, FE f(6m, a, b e L1(F), b e L1(a) et O( C) une cliquede 0 contenant Fu{a,b}. Nous avons FcF'=C-{a,b} et L1(F')=r(a,b)u{a, b} c L1(F), done Ft a, b) c L1(F).

II en resulte aussitot que Ie parametre Ji. est le meme pour tous les graphes fortementreguliers OF, FE f(6m (l ~ m ~ t). Soit FE f(6'-h alors OF est un quadrangle generalise detype (3,2), (3,3) ou (3,5) et nous savons dans ce cas que r = 3, et que u E {I, 2, 4},Ji. E {2, 4, 8}. Soit FE f(6' - 2' alors r= 4 et 12u/2(u+ I) =6u/ (u+ 1) E N, done 6/(u + 1) EN,u E {I, 2, 5}.

Si r;;;'4, en comparant ces deux conditions, nous trouvons uE{I ,2} et Ji.E{2,4}.

THEOREME 7.5. On a les hypotheses 7.1 et 0 est fortement regulier. Si Ji. = 2, (; estisomorphe au graphe latticiel ~(r).

PREUVE. Les parametres du graphe fortement regulier 0 sont: r, s = r - I, t = r - 2done n=r2

, k=(r-I?, 1=2(r-1), A=(r-2?, JL=(r-1)(r-2), A=(r-2) et Ji.=2,done (; a comme ensemble de parametres (r 2

• 2(r-I), r-2, 2).D'apres un theoreme de Shrikhande [9], comme (; a Ie merne ensemble de parametres

que Lir), si r,e4, (;=Lir) qui est d'ailleurs un quadrangle generalise de type (r,2).Supposons r =4, alors n = 16, k =9, 1=6, A=4, JL =6, A= Ji. =2. Soit a E V( 0), Oa estisomorphe aun quadrangle generalise de type (3,2) , mais, pour le graphe de Shrikhaude0', O~ n'est pas de ce type, donc (; = L 2( 4) dans ce cas.

THEOREME 7.6. On a les hypotheses 7.1 et 0 est fortement regulier. Si Ji. =4, (; estisomorphe au graphe triangulaire T(2r).

PREUVE. Les parametres du graphe fortement regulier 0 sont: r, s =2r - 3, t = r - 2done n = r(2r-1), k= (r-I)(2r-3) , 1=4(r-1), A= (r-2)(2r-5), JL = (r -2)(2r-3),A= 2( r - I) et Ji. = 4 done (; a comme ensemble de parametres (r(2r - I), 4(r -1), 2( r -1) ,4).

286 F. Zara

D'apres le theoreme de Chang [2] et Hoffmann [5], comme G a meme ensemble deparametres que T(2r), si r'f:.4, G est isomorphe aT(2r).

Montrons maintenant que le resultat est encore vrai lorsque r = 4. Supposons doner = 4. Nous savons qu'il y a, apart T(8), trois autres graphes fortement reguliers qui ontles memes parametres que T(8): les trois graphes exceptionnels Ch(i) de Chang. lIs sonttous les trois dans la meme 'switching class' que T(8). Nous avons une partition deV( G): V( G) = VI U V2, G( V;) est un sous-graphe de Ch(i) et si a, E V; (i = 1,2), {at. a2}arete de T(8) implique {at. a2) arete de Ch(i) et {at. a2} arete de T(8) implique {at. a2}arete de Ch(i):

Pour ch(1), VI = {(1, 2), (3,4), (5, 6), (7, 8)};

pour ch(2), VI = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, I)};

pour ch(3), VI ={(1, 2), (2, 3), (3, I), (4, 5), (5,6), (6,7), (7, 8), (8, 4)}.

Comme nous nous interessons aux graphes Ch( i), nous avons G( V;) est un sous-graphede Ch(i), i = 1,2) et si a, E V; (i = 1,2), {at. a2} est une arete de Ch(i) si et seulement sic'est une arete de T(8).

Dans ces conditions, il n'est pas difficile de voir que nous avons les cliques:

pour ch(1):{(1, 2), (3,4), (5,6), (7, 8)} et {(1, 2), (1,3), (2, 5)};

pour ch(2): {(t, 2), (3,4), (5,6), (7, 8)} et {(1, 2), (3,4), (6, 7)};

pour ch(3):{(1, 2), (4, 5), (1,4), (2, 5)} et {(1, 2), (4, 5), (6, 7)}.

Dans les trois cas, la condition Al n'est pas verifiee. Done, dans tous les cas, G estisomorphe aT(2r).

REMARQUE 7.7. Soit G un graphe qui verifie (H), de parametres (n; r, r-2) etfortement regulier. Alors G est determine des que l'on se donne ret ji. Designons un telgraphe par G(r, ji).

Nous tracons un diagramme dans lequel nous joignons par un trait montant deuxgraphes lorsque l'un deux est un sous-graphe de l'autre. Nous obtenons:

I II Ii I

t=JG(' + 1, 4 )G(,+1,2)

G(',4)G(',2) :

I I: II G(4,4)

G(4,2)

G(3,2)

G(3,8)

Nous pouvons remarquer que Aut G(r, 2) = S, JC2, Aut G(r, 4) = S2r Aut G(3, 8) =W(E6 ) = 0_(6,2).

Les inclusions de graphes induisent des inclusions de groupes.

PROPOSITION 7.8. Soit G un graphe qui uerifie (H), de parametres (n; r, r - 2). II existedes graphes G j (O:s; i :s;v) tefs que:(1) G=G(R(G))vGovG,v ···vGv ;


(2) 0 0 est une 2-extension d'un graphe O~ de parametres (IV(O~)I; r~, r~-I).

(3) Chaque OJ est isomorphe aun graphe Gtr; iiJ. De plus la decomposition precedentede 0 est unique aI' ordre pres des facteurs.

PREUVE. D'apres la Proposition 4.7, nous avons

0= O(R(0)) v 0 1 V ••• v G;

ou chaque OJ est connexe (l ",;; i",;; u) et OJverifie (H) de parametres (\V( oJI; r; r, - 2)avec pour tout i, r,~ 2.

Supposons que rl ~ r2~ ... ~ ru~ 2. Soit v Ie plus petit entier tel que rv+1 = 2. Alorsrv ~ 3 et si i ~ v + I, r,=2. Dans ces conditions, si i ~ v + I, 0; est une 2-extension d'ungraphe discret 0;. Posons O~= 0~+1 V 0~+2 V ••• v O~; alors O~ verifie (H), de parametres(n: ::~+1 IV( OJ)l; u - v, u - v -I) et il est clair que si 0 0 = 0v+1 V0v+2V... v ou, 0 0 estune 2-extension de O~. D'apres la Remarque 7.7, si I",;; i",;; v, ii; E {2, 4, 8} tel que 0;:::,:Gir; iii) puisque chaque OJ est fortement irreductible,

Partie [B]. Dans cette derniere partie nous classifions les graphes qui verifient (H),de parametres (n; r, t), r"';; 2t -I et fortement irreductibles,

THEOREME 7.9. Soit 0 un graphe qui oerifie (H), de parametres (n; r, t) et fortementirreductible. On suppose que r"';;2t-1. Allors j[ existe un entier m~1 tel que mlr,mlt,(rlm)-2=(tlm) et 0 est une m-extension d'un graphe 0 1 qui oerifie (H), fortementirreductible et de parametres in] m; r] m; (rl m) - 2) avec r] m ~ 5.

PREUVE. Elle est divisee en plusieurs etapes.(A) Nous faisons une recurrence sur t. Si t =2, r = 3 et 0 n'est pas connexe. Si t =3,

r E {4, 5}, done, comme 0 est connexe, r = 5 et le resultat est vrai.Nous supposons Ie resultat vrai pour tous les graphes 0' verifiant (H), de parametres

(n' ;r',t') avec r'",;;2r'-I, It'l<t et fortement irreductibles, Comme 0 est fortementirreductible, d'apres le Corollaire 6.2, si O(E) est un sous-graphe complet de 0, OE estou bien complet, ou bien irreductible.

Soit x E V( 0). Si Ox est complet, nous savons (Proposition 5.9) que 0 est un grapheen marguerite. Comme R(0) =0, t =0, mais, alors r"';; -I ce qui est impossible. DoneOx n'est pas complet, Ox verifie (H), de parametres (A(x); r-I, t -I). Si R(Ox),e 0,IR( oJI = m -I ~ I, alors 0 est une m-extension d'un graphe OJ. qui verifie (H), deparametres in] m; r] m, t] m) et fortement irreductible. Nous avons r] m a (2tl m) - (II m)et, comme rim est entier r] m a (2tlm) -1. Comme Vy E V( 0,), l.vl = 1,0, est fortementregulier (Corollaire 6.9), done l'hypothese de recurrence implique que (rlm)-2= timet, comme rlm"';;(2tlm)-I, nous obtenons tlm~3, ou encore rt m e S,

(B) Dans tout ce qui suit, nous supposons que R (Ox) = 0 , et nous montrons que nousarrivons aune contradiction. Nous montrons d'abord que Ox n'est pas une m-extensionpour tout m~ 2. D'apres la Proposition 5.21 et les Remarques 5.22 nous aurions, dansle cas contraire r ~ 2t + I, ce qui n'est pas. Dans ces conditions, l'hypothese de recurrenceappliquee a Ox montre que Ox ne peut pas satisfaire a cette hypothese, done, commeOx est fortement irreductible, nous obtenons r - I ~ 2( t - I). 11 en resulte aussitot quer~2t-l, done r=2t-1 et (r-1)=2(t-I).

Le meme raisonnement applique a Ox montre que Vy E .d(x) Oxy est fortement irreductibIe. Nous allons montrer que cette situation ne peut pas se produire. Nous supposonsIe contraire et nous arrivons a une impossibilite.

288 F. Zara

(3) II existe un entier s;;;. 2 tel que n = r[1 + ( r - I) (s -1)/1] done

n = (21- I)[I + (21- I)(s - I )/ t], k = ( r - I)s = 2(1- I)s,

A= (21- 3) + (s -I)( t - I) ; (n - r)/ ( r - 1)

= 2(21 - I)(s -1)/ 1, [k - (r -1)]/ (r - 1) = 2(s - I),

[A - (r-2)]/ (r- 1) = s-l.

Nous obtenons ainsi les relations:

et

2(s - l)----'---...:...E~

1(I)

(2)r(r-I )s(s-I ) 2(t -I )(21-l)s(s-l )--'----'--'-------'- = E ~.

l[r-l +s-l] l[t-l +s -l]

Exprimons maintenant que Gx est fortement regulier, pour x E V( G) : les parametres deGx sont ( n l ; r" 11)' II existe un ent ier SI ;;;' 2 tel que n, = k = r\[l + (rl .,... 1)(S l -1)/1\] etk l=A= (r l-l) s l= (21-3 )s \ car rl=r -I= 2t- 2, tl=I-I ; done (21- 3) +(s -l)(t -I) = (21- 3)sl et s\ - I = (s -I)(t -1)/ (21- 3). Comme (1-1 ,21 - 3) = I, no us obtenons

Enfin , nous avons la condition

et cette condition s'ecrit:

s-I--E~.

21-3(3)

(4)2(21-3 )sl (s-l )----'-----'-....:....:....--'- E ~

21- 3 + s - 1

Remarquons que AI = (r\ -2) +(Sl -I)(t\-I ) = (t -2)(s\ + I).Exprimons enfin que si x E V(G ), y E .1(x), Gxy est fortement regulier, Les parametres

de o; sont (n2; r2, t2).II existe un entier S2;;;' 2 tel que n2= A = r2[1 + ( r2 -1)(S2-1 )/ t2], r2= 21- 3, 12 = t - 2,

k2=A\ = (r2-I )s2=2(1-2 )S2= (1 -2)(sl +1) done S2 =(S\ + 1)/ 2 et s\ est impair.Nous avons S2- I = (Sl - 1)/2 = (s - 1)(1- 1)/2(21- 3) E ~. Enfin la condition

donne

2(21- 3)S2(S-I ) E ~. (5)2(2 1-3) +s - I

(D) Nous avons la formule (I ) 2(s -I)/ IE~ et la formule (3) ( s - I)/(2 1 -3) E~ .

Comme ( t,2 t - 3) =( 1, 3), no us distinguons 4 cas suivant que 2 divise 1 ou non et 3divise t ou non .

Nous ne traiterons ici que le 'cas 611 qui est Ie plus complique: les autres se traitantde la meme maniere, Ie plus simple etant celui ou (6, 1)= l. Nous supposons done que1=6v. Alors 21-3=3(4v -l ) et l-I=6v -1. (I ) et (3) donnent ( S - I)/ 3V E~ et (5 1)/3(4v -I) E~, done il existe un entier a tel que 5 -I = 3v(4 v -I)a. Nous obtenons5\ - I = av (6v - I) et 52 - I = av(6v - 1)/2, donc av est un entier pair.


Remplacons t, S, SI et S2 par leur valeur dans les formules (4) et (5) pour obtenir:

2.3(4v -1)[av(6v -1) + 1]3av(4v -1)--'--------'-""---.:---'------"-~-'-----'-E ~,

3(4v -1) +3av(4v -1)

done, apres simplification et en remarquant que av == -1 [mod( av + 1)]:

12(3v -1)(4v -1)-'-----'-------'- E ~.

av + 1De meme

3(4v -1)[av(6v -1) + 1]3av(4v-1)--'------'-=----'-------'--=------'------'- E ~,

2.3(4v -1) +3av(4v-1)

d'ou, comme ci-dessus:

24(3v-l)(4v-1)-'-----'-------'-E ~.

av+2

289

(4)

(4')

(5)

(5')

(2)

Comme (av + 1, av +2) = 1, de (4') et (5') nous tirons:

24(3v-l)(4v-1)-'-----'-------'- E ~.

(av + l)(av +2)

L'application x ~ 24(3x - 1)(4x - 1)/(ax + 1)(ax + 2) est croissante pour x ~ 1 etlim x -> + 00 24(3x -1)(4x -1)/(ax +2) = 288/ a', Done 24(3v -1)(4v -1 )/(av + 1)(av +2) <288/ a 2

• Comme le membre de gauche de cette inegalite est un entier, nous obtenons1<288/a2

, done 1"';a",;16.Exprimons maintenant la condition (2):

2(6v -1 )(12v -1)[3v(4v -1)a + 1]3av(4v -1)()

E~,6v[6v-l +3av 4v-l ]

d'ou apres simplification par 6v:

(6v -1)(l2v -1)[3v(4v -1)a + l]a(4v-1)-'---------'---....:.-':.---.:----'---'-----~'----..:...E ~.

6v -1 +3av(4v-1)

Maintenant (4v-l,6v-1)=1, (3av(4v-l)+6v-l, 4v-1)=1 et 3av(4v-1)+I==-6v+2 (mod3av(4v-l)+6v-1); nous obtenons:

2(3v -1)(6v -1)(12v -1)a---'------'--'------'-------'-E ~.

6v -1 +3av(4v-1)

Comme av est pair, nous pouvons enlever le facteur 2 du numerateur, Puis 6v -1 ==- 3av(4v - 1) (mod 6v -1 + 3av(4v - 1)) et, en faisant les memes operations que ci-dessus,nous trouvons finalement

Mais

a2(3v-l)(12v-1)

-----'---'----'- E ~.

3av(4v-l)+6v-l(2')

donc

a 2(3v -1)(l2v -1)

3av(4v -1) +6v-l

a(a +3)(6v -1)3a

3av(4v -1) +6v -1'

a(a+3)(6v-l)( )

E~,3av4v-l +6v-l

290 F. Zara

et, en operant eomme ci-dessus, nous trouvons

a2(a +3) •----'----'----E I~.

3av(4v-1)+6v-l(2")

Maintenant une elimination cas par cas donne Ie resultat: (2") est impossible en nombresentiers lorsque 1",; a ",; 16 et av est pair.

COROLLAIRE 7.10. Soit 0 un graphe qui oerifie (H), de parametres (n; r, t). On supposeque r"'; 2 t - 1 et que l' une des conditions suivantes est satisfaite:(a) r- t est impair,(b) r - t est pair et (r - t) / 2 ne divise pas r ou ne divise pas t. Alors G n' est pas connexe.

PREUVE. D'apres le Theoreme 7.9 si G est eonnexe, 0 est une m-extension (m » 1)d'un graphe 0 1 que verifie (H), fortement irreductible et de parametres (n(; rh r j - 2).

Nous avons done r = mrh t = mrl - 2m. II en resulte que r - t =2m et que (r - t)/2 = mdivise r et t.

En prenant la negation de eette proposition, nous avons Ie resultat.

EXEMPLE. Soit 0 un graphe qui verifie (H), de parametres (n; r =2t -1, t) et R( 0) =0. Alors r - t = t - 1 est premier a t, done G n'est pas eonnexe. D'apres la Proposition4.7, on a 0=0,V02V' "vOu avec u"';(2t-1)/(t-1)=2+1/(t-1) done u=2, 0=0\ v O2, 0\ et O2 verifient (H), de parametres (n i ; r; t\).

On an = n l + n2,r - t = rl - tl = r2- t2= t -1, rl + t2= r2 + t\ = t. Nous obtenons r\;;:: t -1,r,> t-l d'ou rl = t, r2= t-l car r\ +r2= r=2t-l, puis t1 = 1 et t2=0. Done 0\ est unquadrangle generalise de parametres (n,; t, 1), O2 est un graphe qui verifie (H), deparametres (n2; t -1,0).

REFERENCES

I. M. Aschbacher, A homomorphism theorem for finite graphs. Proc. Amer. Math. Soc. 54 (1976), 468-470.2. Chang Li-Chien, The uniqueness and non-uniqueness of the triangular association schemes. Sci. Record

Peking Math. (New Serie) 3 (1959), 604-613.3. S. Dixmier, F. Zara, Essai d'une methode d'etude de certains graphes. CR.A.S. Paris 282 (1976), 259-262.4. P. J. Cameron and J. H. Van Lint, Graphs, Codes and Designs. London Math. Soc. Lecture Notes Series 43

Cambridge University Press, Cambridge, 1980.5. A. J. Hoffman, On the uniqueness of the triangular association scheme. Ann. Math. Statist. 31 (1960),492-497.6. A. Neumaier, Regular cliques in graphs and special I 1/2-designs. In Finite Geometries and Designs (Cameron,

Hirschfeld, Hugues, eds) London Math. Soc. Lecture Notes Series 49, Cambridge University Press, Cambridge,1981.

7. A. Neumaier, Strongly regular graphs with smallest eigenvalue-m. Archiv. Math. 33 (1979), 392-400.8. T. Kloks and A. Blokhuis, Note on Zara graphs. Eindhoven University of Technology, 1983.9. S. S. Shrikhande, The uniqueness of the Lz association scheme. Ann. Math. Statist. 30 (1959), 781-798.

Received 1 February 1983

FRAN<;:OIS ZARA

Uniuersite de Picardis, UE.R. de Mathematiques33, rue Saint Leu, 80039 Amiens Cedex, France

Documents

Graphes Lies aux Espaces Polaires