Download Combinatorics ’84, Proceedings of the International Conference on Finite Geometries and Combinatorial Structures PDF

TitleCombinatorics ’84, Proceedings of the International Conference on Finite Geometries and Combinatorial Structures
Author
LanguageEnglish
File Size12.2 MB
Total Pages373
Document Text Contents
Page 1

NORTH-HOLLAND MATHEMATICS STUDIES 123
Annals of Discrete Mathematics (30)

General Editor: Peter L. HAMMER
Rutgers' University, New Brunswick, NJ, U. S.A.

Advisory Editors
C. BERGE, Universite de Paris, France
M.A. HARRISON, University of California, Berkeley, CA, U.S.A.
V. KLEE, University of Washington, Seattle, WA, U.S.A.
J.-H. VAN LINT California Institute of Technology, Pasadena, CA, U.S.A.
G .4 . ROTA, Massachusetts Institute of Technology, Cambridge, MA, U. S.A.

NORTH-HOLLAND -AMSTERDAM NEW YORK OXFORD .TOKYO

Page 2

COM BI NATORICS '84
Proceedings of the International Conference on
Finite Geometries and Combinatorial Structures
Barl; ItalK 24-29 September, 1984

edited by

A. BARLOlTI
Universita di Firenze, Firenze, Italy

M. BILIOITI
Universita di Lecce, Lecce, Italy

A. COSSU
Universita di Bart Bari, Italy

G. KORCHMAROS
Universita delta Basilicata, Potenza, Italy

G.TALLINI
Universita 'La Sapienza: Rome, Italy

1986

NORTH-HOLLAND -AMSTERDAM 0 NEW YOAK OXFORD .TOKYO

Page 186

Oir Permu tation Arrays 191

o f Theorem 2 . 3 ) . By Satz 11.8.5 o f Huppert L141, these subgroups cover G. Hence

t h e r e cannot be any a d d i t i o n a l l i n e through e, and i s t h e r e f o r e L-maximal.

By Lemma 3 .1 the p r o o f i s complete, s ince P r o p o s i t i o n 2.2 y i e l d s J 2 J(&). 0

A c t u a l l y , t h e a s s e r t i o n o f Propos

s t r u c t u r e F(&) o f a: L e t 3
gonal pe rmuta t i on a r r a y s w i t h F(JJ )

Sec t i on 2 shows t h a t t h e t r a n s v e r s a l

p o i n t se ts and t h e same t r a n s v e r s a l s

t i o n 3 .2 depends o n l y on t h e i n t e r s e c t i o n

B1,B2 ,..., B t , I
= F (& ) . The c o n s t r u c t i o n procedure o f

seminets ')'(a) and 7113) have t h e same
The t r a n s v e r s a l seminet 7 o f t h e p r o o f

be a s e t o f m u t u a l l y o r t h o -

o f P r o p o s i t i o n 3 . 2 con ta ins

F1s, S E S ~ , w i t h u s e s o F1s = G. The re fo re each l i n e o f con ta ins e x a c t l y
n p o i n t s , and 7 7 (A) i m p l i e s t h a t t h e same i s t r u e f o r J(&) and a l s o
f o r [email protected]). As a consequence, t h e r e i s a p o i n t x o f J(3) such t h a t t h e
number t '+ l o f l i n e s o f T(&) th rough x cannot exceed t h e number t+l o f
l i n e s o f Y th rough e ( i n f a c t , t h i s i s t r u e f o r each p o i n t x o f y(2) ) .
There fore P r o p o s i t i o n 3.2 can be improved as f o l l o w s .

n:= I S I = CG:F1l p a i r w i s e d i s j o i n t t r a n s v e r s a l s
0

3.3. PROPOSITION. Get a= {A1,A 2,...,Atl be one of the s e t s ofmutuaZZy
orthogonal permutation arrays of Exnmple 2 . 5 . Let

of mutually orthogonal permutation arrays with

3 = IB1,B2,. . . ,B t , 1 be a s e t
F ( B ) = F(&). Then t ' 5 C..

The nex t lemma g i ves an upper bound f o r t h e number o f m u t u a l l y o r thogona l p e r -

mu ta t i on a r rays depending on t h e i n t e r s e c t i o n s t r u c t u r e of t h e a r rays . The p r o o f
o f t h i s lemma i s a u n i f i e d v e r s i o n o f t h e p r o o f s o f severa l r e l a t e d r e s u l t s i n
'41 and 171.

3.4. LEMMA. Let A= IA1,A2 ,..., At ] be a s e t of mutualZy orthogonu2 v x r
pemutatioil arrays, and l e t I { l , Z ,..., v}, i o c 11,2 ,..., vl, J 5 {1 ,2 , . . . , r I ,
j o < { l , Z , . . . , r l s a t i s f g

al I f II,

bi

ai 'Ji E I : j o d F . 1 i, (A),
d l V j c J 3 i . I : j + F i i (a.

t"il,i2t I : j O c Fil12 ' (A),

0

I"he1i t ' r - ! J I - 1 .

- Proof . L e t A = ( a . . ) be a v r pe rmuta t i on a r r a y w i t h F(A) = F (& . By a )
' J

"jd the re e x i s t s an element ilk I . Def ine c := a i . From b ) one ob ta ins
f o r a l l

w i t n a i = a i j , by d ) . Thus j L j 0 and a i j z a . . = c . Hence a i o j c . There-

1" 0
i I , and c ) i m p l i e s aio,of c. F o r each j c J t h e r e e x i s t s an i c I

OJ 'JO

Page 187

192 M . Deza arid T. Iliringer

f o r e a i o j = c f o r e x a c t l y one element j o f t h e ( r - i J l - l ) - e l e m e n t s e t { 1 , 2 ,
. . . ,rl \ ( J IJ { j , } ) . I n p a r t i c u l a r , t h i s i s t r u e f o r each o f t h e permuta t ion a r rays
A, t J?- w i t h c and j rep laced by ck and j, . By o r t h o g o n a l i t y , t h e
mapping k t + j, i s i n j e c t i v e . Th is i m p l i e s t s r - IJ I - 1. 0

The f o l l o w i n g c o r o l l a r y t r a n s l a t e s Lemma 3.4 i n t o t h e language o f t ransve rsa l

seminets. No t i ce t h a t t h i s c o r o l l a r y cou ld have been used i n o r d e r t o prove t h e

P ropos i t i ons 3.2 and 3.3.

3.5. COROLLARY. L a t = (X;Lo,L1,. . . ,Lt;T1,T2,. ..,Tv) b e a transversa2
seminet, and 7.et I c {1,2,. . . , v l , io c {1,2¶, . . ,v l and x E X s a t i s f y

al I f 6,

b ) mi,, T ~ ,
el x T i .

0

Then t s r - 6 - 1, w i t h r:= ITl] and 6 : : I T i n ( u i c I Ti) I .
0

3.6. COROLLARY. Let A= {A1 ,A21 . . . ,A 1 be a s e t of rnutuaZZy orthogonal v x r
t

uerrnutation arrays, and l e t

t i r - U - 1 .
p : = max { I Fi , (A) I I i ,i '=1,2,. . . ,v, i *i ' I . Then

~ P roo f . Choose i , i o t . i l , 2 ,..., v l and j o t { 1 1 2 ] ..., r I1 w i t h I F i i o ( s Z ) I = IJ
and

s a t i s f y the assumptions of Lemma 3.4. 1-1
j o & F i i (A) . De f ine I : = t i 1 and J : = F i l o ( & ) . Then I , io, J , jo

0

3.7. COROLLARY. Let A= IAl,A2, . . . , A 1 be a s e t of mutzia1Zy orthogonal v x r
t

pervnitution a r r a y s . Let h : = min { I F . #(.+?-)I 1 i , i ' =1 ,2 , . . , , v ) , and assume X z l .
T'hen

l i
t s r - A - 2 .

Proo f . Choose io,i1,iz8 i1,2 ,..., v l , il*i2$ and joF11 ,2 ,..., r l w i t h j o '
Fili2(&), j o ~ F i l i o ( ~ ) and j o & F . '2'0 . (A). Def ine I : = {ilyi21, J : = F. '1'0 . (A)
IJ F. (f-) .Then

proof i s complete i n t h e case IJI -Xtl. Assume now IJ I = A . Then X = IF. (&)I

= IF . . (&) I , and thus IJI =
A i s s e t t l e d by C o r o l l a r y 3.6. U

I , io, J , jo s a t i s f y t h e assumptions o f Lemma 3.4. Hence t h e
12iO

1210 1 2

1 l i O
I F i i ( & ) I = IJ u tjo)l = X t l . There fore t h e case

The C o r o l l a r i e s 3.5, 3.6 and 3.7 y i e l d s l i g h t g e n e r a l i z a t i o n s for some o f t h e

r e s u l t s i n L41, 171 and r171 (which a r e fo rmula ted i n terms o f designs w i t h
m u t u a l l y o r thogona l r e s o l u t i o n s ) .

s e t o f permuta t ions opera t i ng t r a n s i t i v e l y on t h e s e t

A v x r permuta t ion a r r a y A i s c a l l e d row-transit ive i f t h e rows o f A form a

{ l Y 2 , . ..,rl.

Page 372

Participan Is

A.M. P a s t o r e

S . P e l l e g r i n i

C. P e l l e g r i n o

G. P e l l e g r i n o

C. P e r e l l i Cippo

M . P e r t i c h i n o

G. P i c a

F . P i r a s

A . I . Pornil io

L. Porcu

L . Pucc io

G . Q u a t t r o c c h i

P . Q u a t t r o c c h i

G. Raguso

L . R e l l a

T . Roman

L . A . R o s a t i

H . G . Samaga

M . S c a f a t i

R . S c a p e l l a t o

E . Schroder

R . Schu lz

D . Sena to

H . Siernon

C . S o m a

R. S p a n i c c i a t i

A.G. S p e r a

R . S tangarone
K . Strarnbach

G . T a l l i n i

P . . T e r r u s i

J . Thas

M . Ughi

V . V a c i r c a

B a r i

Bresc i a

Modena

Pe r u g i a

B r e s c i a

B a r i

Napoli

Cagl i a r i

Rorna

Milano

Mess i n a

C a t an i a

Modena

Bari

B a r i

Buc a r e s t i

F i r enze

Hamburg

Roma

Parma

Hamburg

B e r l i n

Napoli

Ludwigsburg

Roma

Rorna

P a l e rmo

B a r i

Er langen

Roma

Bari

Gent

Pe rug ia

C a t an i a.

Page 373

Participants 387

K . Vedder

A. Venezia

F . Verroca

R . V incen t i

A . Ventre

H . Wefelscheid

B. Wilson

N . Lagag l i a Salvi

H . Z e i t l e r

E . Z i z i o l i

R. Z u c c h e t t i

Gissen

Roma

B a r i

Pe rugi a

Napoli

Essen

London

M i 1 ano

Bay r e u t h

B r e s c i a

Pav ia

Similer Documents