D:\User\sbornik_38_pdf\38.DVI


Mathematical Problems of Computer Science 38, 89{90, 2012.

On H yper gr aph Degr ee Sequence Char acter isation

H . S a h a kya n , L . A s la n ya n

Institute for Informatics and Automation Problems
of the National Academy of Sciences

hasmik@ipia.sci.am

Th e qu e s t io n o f n e c e s s a r y a n d s u ± c ie n t c o n d it io n s fo r t h e e xis t e n c e o f a s im p le h yp e r -
g r a p h wit h a g ive n d e g r e e s e qu e n c e is a lo n g -s t a n d in g o p e n p r o b le m . W e in ve s t ig a t e Ãm, t h e
s e t o f a ll d e g r e e s e qu e n c e s o f s im p le h yp e r g r a p h s o n [n] = f1 ; 2 ; ¢ ¢ ¢ ; ng h a vin g m e d g e s . In
p a r t ic u la r , we s h o w t h a t Ãm c a n b e d e ¯ n e d b y it s s p e c ia l p a r t , c o n s is t in g o f s o c a lle d u p p e r
d e g r e e s e qu e n c e s . Fu r t h e r , t h e s e t o f u p p e r d e g r e e s e qu e n c e s c o m p o s e s a n id e a l in a r a n ke d
p o s e t . A n a lo g o u s r e s u lt s a r e fo u n d fo r t h e c o m p le m e n t o f Ãm, in t e g e r n -t u p le s , wh ic h d o n o t
c o r r e s p o n d t o a n y d e g r e e s e qu e n c e o f s im p le h yp e r g r a p h s .

H yp e r g r a p h H is a p a ir ( [n]; E ) , wh e r e [n] = f1 ; 2 ; ¢ ¢ ¢ ; ng is it s ve r t e x s e t a n d E, t h e s e t o f
e d g e s , is a c o lle c t io n o f s u b s e t s o f [n]. H yp e r g r a p h is s im p le if it h a s n o m u lt ie d g e s . Th e d e -
g r e e di o f a ve r t e x i o f H is t h e n u m b e r o f e d g e s in E c o n t a in in g i, a n d d( H) = ( d1; ¢ ¢ ¢ ; dn ) is
t h e d e g r e e s e qu e n c e o f h yp e r g r a p h H. Th e h yp e r g r a p h d e g r e e s e qu e n c e p r o b le m - e xis t e n c e
o f a s im p le h yp e r g r a p h wit h t h e g ive n d e g r e e s e qu e n c e - is a lo n g -s t a n d in g o p e n p r o b le m , ¯ r s t
s t a t e d in [2 ]. W e b r in g s o m e c o m b in a t o r ia l c o u n t e r p a r t s o f t h e p r o b le m . In t e r m s o f ( 0 ,1 ) -
m a t r ic e s : t h e in c id e n c e m a t r ix o f H is a ( 0 ; 1 ) -m a t r ix, wit h c o lu m n s r e p r e s e n t in g t h e ve r t ic e s
a n d r o ws r e p r e s e n t in g t h e e d g e s . S u b s e t s o f [n] a r e id e n t i¯ e d wit h ( 0 ; 1 ) -s e qu e n c e s o f le n g t h
n s u c h t h a t t h e i-t h c o m p o n e n t e qu a ls '1 ', if a n d o n ly if t h e i-t h e le m e n t o f [n] is in c lu d e d in
t h e s u b s e t . Th u s t h e d e g r e e s e qu e n c e p r o b le m is r e d u c e d t o t h e e xis t e n c e o f ( 0 ; 1 ) -m a t r ic e s
wit h g ive n n u m b e r o f 1 s in it s c o lu m n s ( c o lu m n s u m s ) a n d wit h n o r e p e a t e d r o ws . Th e c la s s
o f ( 0 ; 1 ) -m a t r ic e s u n d e r s im ila r c o n d it io n s ( g ive n c o lu m n a n d r o w s u m s ) h a s b e e n s t u d ie d b y
R ys e r , wh o o b t a in e d n e c e s s a r y a n d s u ± c ie n t c o n d it io n s fo r t h e e xis t e n c e o f s u c h m a t r ic e s ,
s e e [7 ]. In t e r m s o f t h e n -d im e n s io n a l u n it c u b e : c o n s id e r t h e p o we r s e t o f [n] a n d it s p a r t ia l
o r d e r b y in c lu s io n . Th e ( 0 ; 1 ) -c o d in g o f s u b s e t s m a p s t h e p o we r s e t in t o En, t h e s e t o f ve r -
t ic e s o f t h e n-d im e n s io n a l u n it c u b e : En = f( x1; ¢ ¢ ¢ ; xn ) =xi 2 f0 ; 1 g; i = 1 ; ¢ ¢ ¢ ; ng. In t h is
wa y, t h e h yp e r g r a p h d e g r e e s e qu e n c e p r o b le m is e qu iva le n t t o t h e e xis t e n c e o f ve r t e x s e t s
in En wit h g ive n s iz e s o f t h e ir p a r t it io n s a c c o r d in g t o va r ia b le s xi. In t h is fo r m u la t io n , t h e
qu e s t io n a r is e s o u t o f t h e d is c r e t e is o p e r im e t r ic p r o b le m fo r En [1 ], wh e r e s o m e e s t im a t io n s
h a ve b e e n p r o ve n a n d u s e d fo r qu a n t it a t ive c h a r a c t e r is t ic s o f p a r t it io n s o f a r b it r a r y n-c u b e
s u b s e t s .
Th e h yp e r g r a p h d e g r e e s e qu e n c e p r o b le m is in ve s t ig a t e d b y s e ve r a l a u t h o r s a n d s o m e c o m -
p le m e n t a r y r e s u lt s h a ve b e e n o b t a in e d b u t t h e m a in p r o b le m is s t ill o p e n . In p a r t ic u -
la r , t h e p o lyt o p e o f d e g r e e s e qu e n c e s o f s im p le u n ifo r m h yp e r g r a p h s o n t h e ve r t e x s e t
[n] = f1 ; 2 ; ¢ ¢ ¢ ; ng is in ve s t ig a t e d in [3 ] a n d o b t a in e d s o m e p a r t ia l in fo r m a t io n . S e ve r a l
n e c e s s a r y a n d o n e s u ± c ie n t c o n d it io n s a r e o b t a in e d in [4 ] fo r e xis t e n c e o f a s im p le 3 -u n ifo r m
h yp e r g r a p h wit h t h e g ive n d e g r e e s e qu e n c e . It is s h o wn in [6 ] t h a t a n y t wo 3 -u n ifo r m h yp e r -

8 9



9 0 On Hypergraph Degree Sequence Characterisation

g r a p h s wit h t h e s a m e d e g r e e s e qu e n c e c a n b e t r a n s fo r m e d in t o e a c h o t h e r u s in g a s e qu e n c e
o f t r a d e s . W e in t e n d t o g ive c h a r a c t e r is a t io n o f Ãm - t h e s e t o f a ll d e g r e e s e qu e n c e s o f s im p le
h yp e r g r a p h s o n [n] h a vin g m e d g e s . Co n s id e r Ãm a s a s u b s e t o f a r a n ke d p o s e t ¥

n
m+1:

¥nm+1 = f( a1; ¢ ¢ ¢ ; an ) : 0 · ai · m fo r a ll i g, wh e r e a c o m p o n e n t -wis e p a r t ia l o r d e r is p la c e d
o n ¥nm+1 : ( a1; ¢ ¢ ¢ ; an ) · ( b1; ¢ ¢ ¢ ; bn ) if a n d o n ly if ai · bi fo r a ll i a n d t h e r a n k o f a n e le m e n t
( a1; ¢ ¢ ¢ ; an ) is g ive n b y a1 + ¢ ¢ ¢ + an. Fir s t we s h o w t h a t t h e a r e a o f c h a r a c t e r is a t io n c a n
b e n a r r o we d : Ãm c a n b e d e ¯ n e d b y it s s p e c ia l p a r t . D e ¯ n e Ĥ, a s p e c ia l s u b p o s e t o f ¥

n
m+1:

Ĥ = f( a1; ¢ ¢ ¢ ; an ) 2 ¥nm+1 : ai ¸ mmid fo r a ll i g, wh e r e a mmid = ( m + 1 ) = 2 fo r o d d m a n d
mmid = m= 2 fo r e ve n m.

T heor em 1 Ãm can be given by Ãm \ Ĥ, its part in Ĥ.
E le m e n t s o f Ãm \ Ĥ we will c a ll u p p e r d e g r e e s e qu e n c e s . Fu r t h e r , we g ive t h e s t r u c t u r e o f
t h e s e t o f a ll u p p e r d e g r e e s e qu e n c e s :

T heor em 2 Ãm \ Ĥ is an ideal in Ĥ.
A n a lo g o u s r e s u lt s a r e t r u e fo r t h e c o m p le m e n t o f Ãm, in t e g e r n -t u p le s , wh ic h d o n o t

c o r r e s p o n d t o a n y d e g r e e s e qu e n c e o f s im p le h yp e r g r a p h s .
Th u s , fo r d e ¯ n in g Ãm \ Ĥ, a n d h e n c e wh o le s e t Ãm, it is s u ± c ie n t t o ¯ n d m a xim a l

e le m e n t s o f t h e id e a l Ãm \ Ĥ. S im ila r ly, fo r d e ¯ n in g t h e c o m p le m e n t o f Ãm, in t e g e r n -t u p le s ,
wh ic h d o n o t c o r r e s p o n d t o a n y d e g r e e s e qu e n c e o f s im p le h yp e r g r a p h s , it is s u ± c ie n t t o
¯ n d m in im a l e le m e n t s o f t h e ¯ lt e r Ĥ n Ãm. Fu r t h e r in ve s t ig a t io n s a r e in p r o c e s s r e la t e d t o
¯ n d in g c la s s e s o f m a xim a l e le m e n t s o f t h e id e a l Ãm \ Ĥ a n d m in im a l e le m e n t s o f t h e ¯ lt e r
Ĥ n Ãm.

R e fe r e n c e s

[1 ] A s la n ya n L . A ., Is o p e r im e t r y p r o b le m a n d r e la t e d e xt r e m a l p r o b le m s o f d is c r e t e s p a c e s ,
P r o b le m y K ib e r n e t iki, 3 6 , p p . 8 5 -1 2 6 ( 1 9 7 9 ) .

[2 ] B e r g e C., H yp e r g r a p h s . N o r t h H o lla n d , A m s t e r d a m , 1 9 8 9 .

[3 ] B h a n u Mu r t h y N .L . A n d Mu r a li K . S r in iva s a n , Th e p o lyt o p e o f d e g r e e s e qu e n c e s o f
h yp e r g r a p h s . L in e a r a lg e b r a a n d it s a p p lic a t io n s , 3 5 0 ( 2 0 0 2 ) , 1 4 7 -1 7 0 .

[4 ] B illin g t o n D ., Co n d it io n s fo r d e g r e e s e qu e n c e s t o b e r e a liz a b le b y 3 -u n ifo r m h yp e r -
g r a p h s " . Th e Jo u r n a l o f Co m b in a t o r ia l Ma t h e m a t ic s a n d Co m b in a t o r ia l Co m p u t in g " .
3 , 1 9 8 8 , 7 1 -9 1 .

[5 ] Co lb o u r n Ch a r le s J., K o c a y W .L . a n d S t in s o n D .R ., S o m e N P -c o m p le t e p r o b le m s fo r
h yp e r g r a p h d e g r e e s e qu e n c e s . D is c r e t e A p p lie d Ma t h e m a t ic s 1 4 , p . 2 3 9 -2 5 4 ( 1 9 8 6 ) .

[6 ] K o c a y, W ., L i, P . C., On d e g r e e s e qu e n c e s o f h yp e r g r a p h s , A r s Co m b in . 8 2 ( 2 0 0 7 ) ,
1 4 5 -1 5 7 .

[7 ] R ys e r G. J., Co m b in a t o r ia l Ma t h e m a t ic s , 1 9 6 6 .

[8 ] S a h a kya n H ., N u m e r ic a l c h a r a c t e r iz a t io n o f n -c u b e s u b s e t p a r t it io n in g , D is c r e t e A p p lie d
Ma t h e m a t ic s 1 5 7 ( 2 0 0 9 ) 2 1 9 1 -2 1 9 7 .