9 4 I 9:00 9:20 9:20 9:40 :M L 0:00 :00, :0 2:0 2:0 3:40 II 3:40 4:00 4:00 4:20 4:40 5:40, 5:50 6:50 7: II 9:5 9:35 9:35 9:55 Colored hook formu

Transcription

1 :30 2: :55 9:00 9:00 9:20 9:20 9:40 poset 9:40 0: :20 :20, :30 2:30 2:30 4:30 4:30 5:30, 5:40 6:40 7:00 7:20 p q g 7:20 7:40 NTT 7:40 8:05 labeled tree chordal graph 8:05 8:25 8:25 9:50 I 9:50 20:0 Trace generating functions of plane partitions 20:0 20:30 Catalan, Motzkin, Schröder Hankel q-analogue 20:30 20:50 GAP Partition

2 9 4 I 9:00 9:20 9:20 9:40 :M L 0:00 :00, :0 2:0 2:0 3:40 II 3:40 4:00 4:00 4:20 4:40 5:40, 5:50 6:50 7: II 9:5 9:35 9:35 9:55 Colored hook formula for a generalized young diagrams 0:5 0:35 A wild configuration chase 0:35 :00 Homotopy type of the box complexes of graphs without 4-cycle :00 :20 Algebraic shifting of strongly edge decomposable spheres :20 :40 3 :40 :

3 (Asai-Yoshida[3]) A, G Hom(A, G) 0 mod gcd( A/A, G ) A A A [2] A A n C n Frobenius F (Frobenius ) G n N # {x G x n = } 0 mod gcd(n, G ) I (Iwasaki []) G H G n N # {x G x n H} 0 mod H Frobenius G n H G H n N G σ # {x HσH x n H} 0 mod H 2 [email protected]

4 2 G H n N G σ, τ # {x HσH x n HτH} 0 mod H 3 G Ω n 2 a Ω a σ a σ G G a := {g G a g = a} G a,a σ := {g G a g = a, (a σ ) g = a σ }, G a n G a n Ga σ Z G a,a σ := {x G x n G a } Iwasaki 4 ( ). Frobenius Iwasaki G H G G a H a := i 0 a i H ai H := a i Ha i C a := {haδh h H δ H a } C a a H- 4 G H G x x H- C x G H- G = C x C x2 C xr (disjoint union). ( x = G ). ( C xi ) n := {α n α C xi } # {x G x n H} = H # { i ( C xi ) n = C G } [] S.Iwasaki, A Note on the nth Roots Ratio of a Subgroup of a Finite Group,Jounal of Algebra 78 (982), [2] T.Yoshida, Hom(A, G),J.Algebla 56(993) [3] T.Yoshida and T.Asai, Hom(A, G),J.Algebra 60(993)

5 Poset Bjorner Factor-order, Subword-order Mobius Bjorner, Sagan, Vatter Rooted-forest( component tree Poset) Generalizedsubword-order Mobius Rooted-forest Conjecture P := {a, b, c a < c, b < c } P Generalizedsubword-order P Mobius µ µ(a i, c j ) = T i+j (X) X j i for 0 i j {T n (X) n N} Chebyshev Definition s ( 2), m N Tm(X) s (s = 2 Chebyshev T0 s (X) =, T s (X) = (s )X Tm(X) s + Tm+2(X) s = sx Tm+(X) s Tm(X) s P s = {a, a s, c a i < c, for i =, r} Theorem s( 2), 0 m n,{a m } {a i a im i, i m {, s}} µ({a m }, c n ) Tm+n(X) s X n m 2 Finite Graded poset ab-index Quasi-symmetric-function( Qsym ) Euler poset c = a + b, d = ab + ba cdindex Stembridge P-partition Enriched-P-partition Stembridge map cd-index Qsym Enriched-P-partition Peak-algebra Billera, Ehrenborg, Readdy ( oriented matroid) Poset ab-index Intersection lattice ab-index c-2d index

6 Hetyei Poset Chebyshev Billera, Ehrenborg, Hsiao, Readdy, Willigenburg Stembridge map, c-2d index Chebyshev open problem 2

7 (Hiroki Shimakura) (VOA) ( )., VOA., VOA,.. VOA VOA. VOA, VOA., VOA Lam.,, Lam,.. n k (binary linear code) C F 2 n F n 2 k.,,. F n 2 {e, e 2,..., e n }, F n 2 c = c i e i (c, c 2,..., c n ).,. F n 2 c (weight) 0 wt(c). (doubly even), 4, (triply even) 8. F n 2,., x, y F n 2, x, y = n i= x iy i mod 2. C, C = {x F n 2 x, y = 0 y C} (dual code). C

8 (self-orthogonal), C C, (self-dual) C = C. n C n 2 C 2 n + n 2 C C 2.,. 2, ϕ : F n 2 F 2n 2, c (c, c). n C, 2n Φ(C) F 2 ϕ(c), ( n, 0 n ).,. 2.. C., Φ(C) 2. VOA, () 6 Reed-Muller RM(, 4) 3. (2) 32 RM(, 4) RM(, 4) Φ(d + 6)., d , 48., 24 7., , , RM(, 4) RM(, 4) RM(, 4).,,.. F n +n 2 2 F n 2, Fn C 8, Φ(C) 6. 3 H 8 [8, 4, 4], RM(, 4) = Φ(H 8 )

9 Theorem F. Let p be prime and a be integer. Then a p a (mod p). Corollaly F. Let p be prime and (a, p) =. Then a p (mod p). Corollaly F2. Let p be prime and (a, p) =. Then sa p s (mod p) for s p. Definition. When sa n s (mod n), let a i = sa i mod n (i =, 2,..., n) for s n. Find the first i (i =2, 3,..., n) such that a i = s. Put the i be L. Then the sequence a (= s),a 2 (= sa),a 3 (= sa 2 ),..., a L (= s) is called an L-orbit starting s. When there exist (n ) L-orbits starting, 2,..., n, we say that n admits L-orbits. Note. Let p be prime. It is a widely known result that p admits p-orbits and that a is called a primitive root w.r.t. mod p. Especially, the least a denoted g is called a least primitive root w.r.t mod p. Example. (p, g) =(2, ), (3, 2), (5, 2), (7, 3), (, 2), (3, 2), (7, 3), (9, 2), (23, 5), (29, 2), (3, 3), (37, 2), (4, 6), (43, 3), (47, 5), (53, 2), (59, 2), (6, 2), (67, 2), (7, 7), (73, 5), (79, 3), (83, 2), (89, 3), (97, 5). (p, g) =(5, 2) p-orbit :, 2, 4, 3, (p )-cycle C =(, 2, 4, 3). (p, g) =(7, 3) p-orbit :, 3, 2, 6, 4, 5, (p )-cycle C =(, 3, 2, 6, 4, 5). Definition. Let K n denote the symmetric complete digraph of n vertices. The symmetric complete multi-digraph λk n is the symmetric complete digraph K n in which every edge is taken λ times. Let C k be the directed cycle on k vertices.the C k -t-foil is a digraph of t edge-disjoint C k s with a common vertex. When λk n is decomposed into edge-disjoint sum of C k -t-foils, we say that λk n has a C k -t-foil decomposition. Moreover, when n =(k )t + and every vertex of λk n appears in the same number of C k -t-foils, we say that λk n has a tightly balanced C k-t-foil decomposition. This decomposition is a type of resolvable C k -foil designs. Example 2. (n, g) = (3, 2) n-orbit :, 2, 4, 8, 3, 6, 2,, 9, 5, 0, 7, (n )-cycle C =(, 2, 4, 8, 3, 6, 2,, 9, 5, 0, 7). C 5-3-foil = (3,, 2, 4, 8) (3, 3, 6, 2, ) (3, 9, 5, 0, 7). C 5-3-foil = (3, 2, 4, 8, 3) (3, 6, 2,, 9) (3, 5, 0, 7, ). C 5-3-foil = (3, 4, 8, 3, 6) (3, 2,, 9, 5) (3, 0, 7,, 2). C 5-3-foil = (3, 8, 3, 6, 2) (3,, 9, 5, 0) (3, 7,, 2, 4). These C 5-3-foils comprise a tightly balanced C 5-3-foil decomposition of 5K 3. Conjecture. λk n has a tightly balanced C k-t-foil decomposition if and only if λ 0 (mod k) and n =(k )t +. Department of Informatics, Faculty of Science and Technology, Kinki University, Osaka , JAPAN. E- mail:[email protected] Tel: (ext. 5409) Fax:

10 グラフのトラックレイアウト 宮 内 美 樹 日 本 電 信 電 話 株 式 会 社 NTT コミュニケーション 科 学 基 礎 研 究 所 グラフ G=(V,E)の 頂 点 集 合 V を 2 つの 部 分 集 合 A と B に 分 けて,G の 辺 がすべて A の 頂 点 と B の 頂 点 とを 結 ぶ 辺 になっているようにできるとき G を 2 部 グラフという.この 分 割 集 合 A, B を 部 集 合 と 呼 び,A, B の 頂 点 の 個 数 がそれぞれ m, n のとき,G = G m,n で 表 す.もし G が A の 頂 点 と B の 頂 点 を 結 ぶ 辺 を 全 て 含 んでいれば G は 完 全 2 部 グラフと 呼 ばれ G=K m,n で 表 す. グラフ G の 辺 上 に 次 数 2 の 頂 点 を 幾 つか 付 け 加 えて 得 られるグラフを G の 細 分 という. 付 け 加 えられた 次 数 2 の 頂 点 を 細 分 点 と 呼 ぶ.グラフはまたそれ 自 身 の 細 分 ともみなす. 集 合 S の 全 順 序 というのは,S 上 の 全 順 序 σ のことをさす. 集 合 S はσによって 順 序 付 けられ ているというように, 全 順 序 σ のことを 簡 単 に 全 順 序 σとも 書 くことにする.グラフ G の 頂 点 順 序 というのは, 頂 点 集 合 V(G) 上 の 全 順 序 σのことである. 頂 点 集 合 V(G)の 分 割 {V i : i t}が G の 頂 点 t- 彩 色 であるとは, 任 意 の 辺 vw E(G)に 対 して, v V i かつ w V j ならば i j が 成 り 立 つときのことを 言 う. G の 頂 点 t- 彩 色 {V i : i t}の 各 部 分 集 合 V i が < i によって 順 序 づけられているとき, 順 序 集 合 (V i, < i ) をトラックと 呼 び,{(V i, < i ) : i t} を G の t-トラック 割 り 当 て と 呼 ぶ. 各 部 分 集 合 での 順 序 がわかっているときは, 単 にトラック 割 り 当 てを{ V i : i t}とも 表 記 する. トラック 割 り 当 てにおける X- 交 差 とは, 異 なる i と j で v < i x かつ y < j w となるような 2 辺 vw と xy のことを 言 う.E(G)の 分 割 {E i : i k} のことを,G の 辺 k- 彩 色 と 言 う. 辺 vw E i は 色 i に 彩 色 されていると 言 う.グラフ G の (k, t)-トラックレイアウトとは,g の t-トラッ ク 割 り 当 てと, 同 色 の X- 交 差 を 持 たない G の 辺 k 彩 色 からなるものを 言 う.(k, t)-トラックレイ アウトを 持 つグラフのことを (k, t)-トラックグラフという. グラフ G の 頂 点 の 順 序 において,L(e) と R(e) をそれぞれ,G の 辺 e E(G)の 両 端 点 で,L(e) < σ R(e)を 満 たすものとする.L(e) < σ L( f )なる, 異 なる 2 辺 e, f E(G) に 対 して,e と f がネスト しているとは, L(e) < σ L( f ) < σ R( f ) < σ R(e) を 満 たすときをいう. グラフ G のキューとは, 辺 集 合 E(G)の 部 分 集 合 E E(G) で E のどの 辺 もネストしていな い 部 分 集 合 を 言 う.グラフ G の k-キューレイアウトとは,g の 頂 点 順 序 σと 辺 集 合 E(G)の 分 割 {E s : s k} からなるセットで, 各 分 割 集 合 E s が 頂 点 順 序 σに 対 して,キューとなっているも のをいう.k-キューレイアウトを 持 つグラフを k-キューグラフと 呼 ぶ.グラフ G のキュー 数 qn(g)とは G が k-キューグラフとなるような 最 小 の k のことである. 今 回 は,グラフの 細 分 の(k,2)-トラックレイアウトについてキュー 数 と 関 連 付 けられた 結 果 を 紹 介 するとともに 最 新 の 成 果 を 発 表 する.

11 Labeled tree G 4 T G ()T G (2)T Q i Q h Q j path Q h Q j Q i Theorem. (H. Shinohara 2007 preprint) L V ( V = k) L L, L 2 L L L 2 u, v L 2 u v w w L \uv u L vw\uv L L minimal separator

12 . Ising Model Gibbs NP Chertkov and Chernyak [].2 AI LDPC, , tel , Institute of Statistical Mathematics, 4-6-7, Minami-Azabu, Minato-Ku, Tokyo, Definition ( ). V = {i,..., i N },E V V G := (V, E) (j, i) E i j V E E i.e. (j, i) E (i, j) E i.e. (i, i) / E G, (j, i) (i, j) ji(= ij) Ẽ N(i) i d i := N(i) i Definition 2 ( ). G = (V, E) χ := i V χ i G x = (x i ) i V χ i = {0, } χ G Definition 3. (G, χ) ji Ẽ ψ ji : χ j χ i R 0 G Ψ = {ψ ji } ji Ẽ (G, χ, Ψ) p(x) = Z ji Ẽ ψ ji(x j, x i ) χ p x = (x i ) i V,Z 2.2 (Belief Propagation) {p i (x i )} i V Z loopy belief propagation

13 [2] Algorithm (Belief Propagation) (j, i) E t = 0 i j m t=0 (j,i) R χj m (j,i) (x j ) = χ j x j χ j 2. t = 0,,... m t+ (j,i) (x j) = ω x i χ i ψ ji (x j, x i ) k N(i)\{j} m t (i,k) (x i) () ω x j m t+ (j,i) (x j) = {m (j,i) } (j,i) E 3. p(x) p i (x i ), p ji (x j, x i ) b i (x i ) := ω j N(i) b ji (x j, x i ) := ω ψ ji (x j, x i ) m (j,k) (x j) k N(j)\{i} m (i,j) (x i) (2) k N(i)\{j} 4. log Z log Z B = m (i,k ) (x i) (3) b ji (x j, x i ) log ψ ji (x j, x i ) ji Ẽ x jx i b ji (x j, x i ) log b ji (x j, x i ) x jx i ji Ẽ + i V (d i ) x i b i (x i ) log b i (x i ) (4) G tree( ) 2.3 Loop Loop (G, χ, ψ) {m (i,j)} {β ij } ij Ẽ, {γ i} i V x R {f n (x)} n=0 f 0(x) =, f (x) = 0, f n+ (x) = xf n (x) + f n (x) : 2.3. Loop Z = + β l + β r + β l β 67 β r γ 6 γ 7 (5) β l = β 2 β 23 β 34 β 45 β 56 β 6, β r = β 78 β 89 β 9(0) β (0)() β ()(2) β (2) Z B = 5 Z B Theorem (Loop Expansion). Z = Z B ( + C G r(c)) (6) G G 2 C = (E C, V C ) d C,i C i r(c) := 3 ij ẼC β ij i V C f dc,i (γ i ) (7) 6 Pfaffian [] M. Chertkov and V.Y. Chernyak. Loop series for discrete statistical models on graphs. Journal of Statistical Mechanics, page P06009, 2006a. [2] J. Pearl Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference Morgan Kaufman, 988. [3] M. E. Fisher, On the Dimer Solution of Planar Ising Models J. Math. Phys., 7:776-78, E G = 2 E. 6

14 Trace Generating Functions of Plane Partitions Soichi OKADA Graduate School of Mathematics, Nagoya University A plane partition is an array of non-negative integers π π 2 π 3 π = π 2 π 22 π 23.. satisfying i,j π i,j < and π i,j π i,j+, π i,j π i+,j for all i and j. A plane partition π is identified with its diagram {(i, j, k) P 3 : k π i,j }, where P is the set of positive integers, and can be visualized as a stack of unit cubes. For positive integers a, b and c, we denote by P(a, b, c) the set of all plane partitions whose diagrams are contained in the a b c box. Given a plane partition π = (π i,j ), we define the k-th trace t k (π) by putting t k (π) = π i,i+k. In this talk, we follow an idea of Okounkov and Reshetikhin to prove Gansner s formula b π P(a,b, ) k= a+ q t k(π) k = where q[i, j] = j k=i q k and its finite analogue b π P(a,b,c) k= a+ q t k(π) k a i= j=. b ( q[ i +, j ]), = ( q a a+ qa 2 a+2 q ) c s(c a )(z, z 2,, z a+b ), where s (c a ) is the Schur function corresponding to the rectangular Young diagram (c a ) and z i = q[ a +, a + i ] ( i a + b).

15 Catalan, Motzkin, Schröder Hankel q-analogue 4 0 [email protected] Mathematics Subject Classifications: Primary 05A5; Secondary 05A7, 05E05, 05E0. Keywords: Catalan numbers, Fibonacci numbers, Hankel determinants. Introduction Catalan Hankel determinants q-analogue. Catalan path Catalan Motzkin Schröder path,. Catalan c n = n+( 2n ) n (n = 0,, 2,... ) c0 =, n c n = c n c k (.) k=0 [4]. Catalan n Hankel Mn t = c t c t+... c t+n c t+ c t+2... c t+n (.2) c t+n c t+n... c t+2n 2 det M 0 n = det M n =, (.3) det M 2 n = n +, (.4) det Mn 3 = (n + )(n + 2)(2n + 3) (.5) 6 [, 3]. c t + c t+ c t+ + c t+2... c t+n + c t+n c t+ + c t+2 c t+2 + c t+3... c t+n + c t+n+ Sn t = c t+n + c t+n c t+n + c t+n+... c t+2n 2 + c t+2n (.6).

16 n Hankel det M 0 n = f 2n (.7) det M n = f 2n+ (.8) [, 2]. f n Fibonacci ( f 0 = f =, f n = f n + f n 2 ). 2 Catalan q-analogue c n (q) c 0 (q) = n c n (q) = q (k+)(n k) c n k (q)c k (q) (2.) k=0., Hankel (.2) q-analogue ( ) Mn(q) t = q (i j)(i j+)/2 c i+j+t 2 (q),. Theorem 2.. n i,j n (2.2) det M 0 n(q) = det M n(q) = (2.3) Conjecture 2.2. n. [n] q = qn q det M 2 n(q) = [n + ] q, (2.4) det M 3 n(q) = [n + ] q[n + 2] q (( + q 2 )[n + ] q + q n+ ) [3] q [2] q (2.5) q-. q-motzkin numbers m n (q) q-schröder numbers s n (q) m 0 (q) = s 0 (q) =, n 2 m n (q) = q 2n m n (q) + q 2(k+2)(n 2 k) m n 2 k (q)m k (q), (2.6) k=0 n s n (q) = q 2n s n (q) + q 2(k+2)(n k) s n k (q)s k (q) (2.7) k=0.. [] A. Benjamin, N. Cameron, J. Quinn and C. Yerger, Catalan Determinants A Combinatorial Approach, preprint. [2] A. Cvetkovié, P. Rajkovié and M. Ivkovié, Catalan numbers, the Hankel transform, and Fibonacci numbers, J. Integer Seq. 5 (2002), Article [3] M.E. Mays and J. Wojciechowski, A determinant property of Catalan numbers Discrete Math. 2 (2000), [4] R. Stanely, Enumerative Combinatorics, Volume, 2, Cambridge University Press,

17 Gap Partition Partition 2 3 {{f, m, m 2, m 4 }, {f 2 }, {f 3, f 4 }{f 5, m 3 }, {m 5 }} w, w 2 Q (Q C) C A (Partition ) A n (Q) f f 2 f 3 f 4 f 5 T2 T3 T4 T T5 w w w 2 =Q w 2 m m 2 m 3 m 4 m 5 : dim A n (Q) 2n Bell

18 B(2n) Bell n (), 2, (5), 5, (52), 203, (877), 440, (247), 5975,... Young Young λ (0) λ (0) n λ (n) Young λ (i) (inner) corner box λ (i+/2) λ (i+/2) (outer) corner box λ (i+) Young Bell B(2n) 0-th -st 2-nd rd : A n (Q) Bratteli GAP A n (Q) Bell B(2n) n A n (Q) GAP Groups Algorithms and Programming GAP GAP 2

19 NUIDA, Koji CD DVD [] ID [2] 2 Marking Assumption w m w i 0 w {0, } m u,..., u l w,..., w l j j Marking Assumption (Marking Assumption) j m w,j = w 2,j = = w l,j y y j = w,j

20 Marking Assumption y l P l (y) = {{u,..., u l } Z l u < u 2 < < u l N, y j {w,j,..., w l,j } for all j m} N [3] P l (y) 3 P l (y) x = (x i,j ) i N, j m M N,m ({0, }) m y = (y,..., y m ) {0, } m j (MA) j m y j {x i,j, x i2,j,..., x il,j} {,..., N} l {i,..., i l } Ω(N l ) N l [] JASRAC INTERNET Watch 027/special.htm [2] D. Boneh and J. Shaw, Collusion-secure fingerprinting for digital data, IEEE Trans. Inform. Theory 44 (998) pp [3] K. Nuida, M. Hagiwara, T. Kitagawa, H. Watanabe, K. Ogawa, S. Fujitsu, and H. Imai, A tracing algorithm for short 2-secure probabilistic fingerprinting codes strongly protecting innocent users, 4th Annual IEEE Consumer Communications and Networking Conference (CCNC 2007) DRM Workshop, Nevada, USA, Jan.,

21 2007/09/04 9:20-9:40 CSS CSS LDPC LDPC LDPC IEEE802.n( LAN 2.4GHz/5GHz 00Mbps IEEE802.6e MAN Mobile WiMAX 3Km 2Mbps IEEE802 IEEE802.6e Acknowledgement: This research was partially supported by Grants-in- Aid for Young Scientists (B), , 2006.

22 X-compact X-compact X-code x =(x (),x() 2,...,x() m ) x 2 =(x (2),x(2) 2,...,x(2) m ) F 2 m x x 2 superimposed sum x x 2 x x 2 =(x () x (2),x() 2 x (2) 2,...,x() m x m (2) ), x ( j) i = x (l) k = 0 x ( j) i x (l) k = 0 x x 2 = x x x 2 cover X F 2 m n e e d X superimposed sum n x e cover X (m,n,e,x) X-code X-code X- compact

23 ¹ Ù Û Ö º Û Ò º º Ô ÇÒÐ Ò Ò ÈÖÓ Ð Ñ ÓÖ Ê ÙÐ Ö ÈÓÐÝ ÓÒ À ÖÓ Ù Û Ö ÃÛ Ò Ù Ò ÍÒ Ú Ö ØÝ ½ ÁÒØÖÓ ÙØ ÓÒ ÁÒ Ø ¹ ÖÚ Ö ÔÖÓ Ð Ñ Ø ÔÐ Ý Ö Ñ Ò ÖÚ Ö Ý Ò Ò Ø Ö ÐÓ Ø ÓÒ Ó Ø Ø Ø Ð Ø ÓÒ Ó Ø Ñ ÖÚ Ø Ö ÕÙ Ø Ø Ø Ñ Ø Ô º ÁÒ Ø Ô Ô Ö Û ØÙ Ý ½¹ ÖÚ Ö ÔÖÓ Ð Ñ ÓÒ Ø ÜݹÔÐ Ò º ÇÒ Ñ Ý Ø Ò Ø Ø Ø ÔÐ Ý Ö ÓÛÒ ÓÒÐÝ ÓÒ ÖÚ Ö Ø Ö ÒÓ Ó Ò ÖÚ Ö ÐÓ Ø ÓÒ Ò Ø Ö ÓÖ Ø ÓÑÔ Ø Ø Ú Ö Ø Ó ÐÛ Ý ÓÒ º Ì Ó Ú ÓÙ ÐÝ ØÖÙ Ø ÔÐ Ý Ö ØÓ ÑÓÚ Ø ÖÚ Ö ØÓ Ø Ü Ø ÔÓ Ø ÓÒ Ó Ø Ö Õ٠غ ÀÓÛ Ú Ö Ø ÒÓÙ ØÓ ÑÓÚ Ø ÓÑ Û Ö Ò Ö Ø Ö ÕÙ Ø Ø Ò Ø ÔÐ Ý Ö Ó Ú Ó º Æ Ñ ÐÝ ÒØ ÓÒÐ Ò Ò ÔÖÓ Ð Ñ Ö ÕÙ Ø ÖØ Ò Ö ÓÒ Ù Ø Ø Ø Ö ÕÙ Ø Ò ÖÚ Ø ÖÚ Ö ÑÓÚ ÓÖ Ø Ý Ò Ø Ö ÓÒº Ì Ò Ð ÖÚ Ö Ò ÓÓ Ò Ö ØÖ ÖÝ ÔÓ ÒØ Ò Ø Ö ÓÒ Ò ÓÖ Ö ØÓ Ö Ù Ø ØÓØ Ð ØÖ Ú Ð Ø Ò º Æ ØÙÖ Ð ÔÔÐ Ø ÓÒ ÒÐÙ ÐÐÓ Ø ÓÒ Ó Ö Ð Ý ÖÓ Ø Ò Ö ØÓ ÓÐÐÓÛ ÙÔ ÓÒ ÙØ Ú Ò ÒØ Ò Ø Ø Ó Ø Ü Ò Ò ÓÐ ØÝ Û Ø Ú Ö ØÖ Æ Ö ØÖ Ø ÓÒ º Ö Ñ Ò Ò Ä Ò Ð Ö Ø ØÙ Ø ÔÖÓ Ð Ñ Ò ÔÖÓÚ Ø Ø Ø Ö Ü Ø ÓÑÔ Ø Ø Ú ÓÒÐ Ò Ð ÓÖ Ø Ñ ÓÖ Ø ÓÒÐ Ò Ò ÔÖÓ Ð Ñ ÓÖ ÒÝ ÓÒÚ Ü Ö ÓÒ ¾ º Ì Ý Ò Û Ø Ð Ò Ò Ò ÜØ Ò Ø Ò ÐÝ ØÓ Ð ÔÐ Ò Ò Ò Ö Ð ÓÒÚ Ü Ó º ÀÓÛ Ú Ö Ø Ý Û Ö ÒÓØ ÒØ Ö Ø Ò ÒÝ Ô Ô Ó Ø Ö ÓÒ ÓÖ Ô Ú ÐÙ Ó Ø ÓÑÔ Ø Ø Ú Ö Ø Óº Ì ÔÖÓ Ð Ñ ÒÓØ ÔÔ Ö Ò Ø Ð Ø Ö ØÙÖ Ò Ø Òº ÁÒ Ø ÓÒÐ Ò Ò ÔÖÓ Ð Ñ Ö ÕÙ Ø Ê Ü Ý µ Ú Ò ÓÑ Û Ö ÓÒ Ø ÜݹÔÐ Ò Ø Ø Ñ Ø Ô ½ ¾ Ѻ Ì Ò Ò ÓÒÐ Ò Ð ÓÖ Ø Ñ Ð Ø Ø ÓÐ ÖÚ Ö ÓÒ ÔÓ ÒØ Ò Ö ÓÒ Ø Ø Ó Ø Û Ø Ê º ÓÖ Ò ÒÔÙØ ÕÙ Ò Ê ½ Ê ¾ Ê Ñ µ Ø Ó Ø Ó Ð Ò Ä µ Ë ½ ÈÑ ¾ ½ Û Ö Ë Ø Ò Ø Ð ÐÓ Ø ÓÒ Ó Ø ÖÚ Ö Ò ½ ÒÓØ Ø ÙÐ Ò Ø Ò ØÛ Ò ½ Ò º ÁÒ Ø Ô Ô Ö Û Ð Ø Ö ÓÒ Ø ÙÒ ÓÒ Ó Ö ÙÐ Ö ÔÓÐÝ ÓÒ Û Ø ÒØÖÓ Ê Ò Ø ÒØ Ö ÓÖº Ì ÔÓÐÝ ÓÒ Ó ÒÓØ ÖÓØ Ø Ò Ø Ö ÓÖ Û Ò ÙÑ Û Ø ÓÙØ ÐÓ Ó Ò Ö Ð ØÝ Ø Ø Ø ÓØØÓÑ ÐÛ Ý Ô Ö ÐÐ Ð ØÓ Ø Ü¹ Ü º ÐØ ÓÙ ÓÖ ÓÒÚ Ò Ò Ó Ø Ò ÐÝ Û Ø Ø Ð Ò Ø Ó Ò Ø ÔÓÐÝ ÓÒ ÓÒ Ø Þ Ó Ø ÔÓÐÝ ÓÒ Ó ÒÓØ Ñ ØØ Ö ØÓ Ø ÓÒÐ Ò ÓÑÔ Ø Ø Ú Ò º ÓÐÐÓÛ Ò ½ Û Ý Ø Ø Ø ÓÑÔ Ø Ø Ú Ö Ø Ó Ó Ò ÓÒÐ Ò Ð ÓÖ Ø Ñ Ð Ø Ö Ü Ø ÓÒ Ø ÒØ Ù Ø Ø ÓÖ ÐÐ ÒÔÙØ ÕÙ Ò Ä µ ÇÈÌ µ Û Ö ÓÔØ Ò ÓÔØ Ñ Ð Ó Ò Ð ÓÖ Ø Ñº ¾ Ö Ý Ð ÓÖ Ø Ñ Ì Ö Ý Ð ÓÖ Ø Ñ ÓÖ Ø ÓÒÐ Ò Ò ÔÖÓ Ð Ñ Ò ÐÓÛº ÓÖ Ö ÙÐ Ö ÔÓÐÝ ÓÒ ÓÒ Ò ÐÝ Ø Ø Ø Ö Ö ØÛÓ ØÝÔ ÓÒ Ø ÖÚ Ö³ Ú ÓÖ Ì ÖÚ Ö ÖÖ Ú ÓÒ ÓÒ Ó Ø Ø Ö Ú ÖØ Ð ÑÓÚ Ñ ÒØ Ò Ø Ø Ø ÓÖ ÓÒ ÓÒ Ó Ø Ú ÖØ º Ð ÓÖ Ø Ñ Ö ÓÖ Ö ÕÙ Ø µ Ø ÖÚ Ö³ ÔÖ Ú ÓÙ ÔÓ Ø ÓÒ ½ ÒÓØ Ò Ø Ò ÑÓÚ Ø ÖÚ Ö ØÓ ¾ Ù Ø Ø Ñ Ò Ñ Þ ½ º µ ÇØ ÖÛ Ó ÒÓØ ÑÓÚ Ø ÖÚ Öº ½

24 ½ Ð Ë ÓÔØ ¾ ÙÖ ½ ÇÒÐ Ò Ò ÓÖ À Ü ÓÒº Ò ½¼ ÓÑÔ Ø Ø Ú Ö Ø Ó ¾º¼¼ ½º ½ º¾ ¾º¼¼ º ¾º ½ º º¾ Ì Ð ½ ÓÑÔ Ø Ø Ú Ö Ø Ó Ó Ö ÓÖ Ö ÙÐ Ö Ò¹ ÓÒ º Ì ÓÖ Ñ ½º ÓÖ Ø ÓÒÐ Ò Ò ÔÖÓ Ð Ñ Ø Ø Ø ÓÑÔ Ø Ø Ú Ö Ø Ó Ó Ø Ö Ý Ð ÓÖ Ø Ñ ½ Ò ¾Ò ÓÖ Ó Ò Ò ½ Ò ÓÖ Ú Ò Ò Ø Ö ÕÙ Ø Ö ÓÒ Ö ÙÐ Ö Ò¹ ÓÒ Ò µº Ò Ë Ø Ó ÔÖÓÓ º Ì ÙÔÔ Ö ÓÙÒ ÔÖÓÚ Ò Ý Ò ÑÓÖØ Þ Ò ÐÝ º ÓÖ Ú Ò ÒÔÙØ ÕÙ Ò Û ÒÚ Ø Ø ÓÛ Ö Ò Ò Ó Ò Ð ÓÖ Ø Ñ Ó ÑÓÚ Ø ÖÚ Ö ÓÖ Ö Õ٠غ Ï Ù ÔÓØ ÒØ Ð ÙÒØ ÓÒ Ó Ü Ýµ È Ò ½ ¼ Ü Ò ¾ ¾ Ý Ó Ò Ò Û Ö Ü Ýµ Ø ÔÐ Ñ ÒØ Ó ØÛÓ ÖÚ Ö Ñ Ò Ý Ö Ò Ó º Ì ÙÒØ ÓÒ Ò Ö Ö Ò ÜØ Ò ÓÒ Ó Ø Å Ò ØØ Ò Ø Ò ØÛ Ò Ø ÖÚ Ö º ÌÓ ÓÛ Ø Ø ØÒ Û Ú Ò ÒÔÙØ ÕÙ Ò ÓÒ Ø Ò Ó Ö Ô Ø Ø ÓÒ Ó ØÛÓ ÔÓÐÝ ÓÒ ÇÒ Ü Ò Ø ÓØ Ö Ð ØÐÝ Ð Ò º Ï Ð Ø ÓÔØ Ñ Ð Ó ØÓ Ó Ö ØÐÝ ØÓ Ø ÒØ Ö Ø ÓÒ Ø ÖÚ Ö Ó Ö Ó Ð ØÓ Ø Þ Þ ØÛ Ò ØÛÓ Ê Ö Ò ½ º ÓÖÓ Ò Ò Êº й Ò Úº ÇÒÐ Ò ÓÑÔÙØ Ø ÓÒ Ò ÓÑÔ Ø Ø Ú Ò ÐÝ º Ñ Ö ÍÒ ¹ Ú Ö ØÝ ÈÖ ½ º ¾ º Ö Ñ Ò Ò Æº Ä Ò Ðº ÇÒ ÓÒÚ Ü Ó Ý Ò º Ö Ø ² ÓÑÔÙØ Ø ÓÒ Ð ÓÑ ØÖÝ ¾ ß ¾½ ½ º ź ˺ Å Ò Äº º Å Ó Ò º º ËÐ ØÓÖº ÓÑÔ Ø Ø Ú Ð ÓÖ Ø Ñ ÓÖ ÖÚ Ö ÔÖÓ Ð Ñ º º Ð ÓÖ Ø Ñ ½½ ¾µ ¾¼ ß¾ ¼ ½ ¼º º ËÐ ØÓÖ Ò Êº º Ì Ö Òº ÑÓÖØ Þ Æ ÒÝ Ó Ð Ø ÙÔ Ø Ò Ô Ò ÖÙÐ º ÁÒ ÓÑÑÙ¹ Ò Ø ÓÒ Ó Ø Å ÚÓÐÙÑ ¾ Ô ¾¼¾ß¾¼ ½ º ¾

25 µ = (µ µ 2 ) l m. µ, a µ,l m/l l (i,j)=(i l+i,j) µ. i (j + µ k, j + k= i i+ µ k, j + µ k,..., j + k= k= i+l Example. µ = (2, 2, 2,,, ), a µ,3 = (, 3, 5)(2, 4, 6)(7, 8, 9)., standard tableaux, l,, a µ,l : k= µ k ) (, 3, 5)(2, 4, 6)(7, 8, 9). Young subgroup S µ = S {,...,µ } S { µ +,...,µ +µ 2 } l C l = a µ,l H µ (l) = S µ C l., Z µ (k; l) H µ (l) C ; S µ σ, C l a µ,l ζ k l ( ζ k l = exp(2πk /l)), M µ (k; l) m S m Z µ (k; l) S m H µ (l)., cycle type ρ σ S m, M µ (k; l) l k=0 ζ ik l Char(M µ (k; l))(σ)., Young diagram D µ, (marked (ρ, l)-tableux on µ) (, ). Char(M µ (k; l))(σ) (marked (ρ, l)-tableux on µ)., (ρ, l)-tableux on µ., l k=0 ζik l

26 2 NUMATA, YASUHIDE Definition 2. µ Young diagram D µ = { (i, j) N 2 j µ i } m ρ = (ρ ρ 2 ), T (ρ, l)-tableaux on µ : T D µ N., Young diagram D µ. k, T ({ k }) = ρ k., ρ k k. k, n, i, j, T ({ k }) = { (i + i, j + j ) (i, j ) D (n l ) }., k l n. j k (i, j), (i, k) D µ, T (i, j) T (i, k).,,. Example 3., ((6, 3, 3, 3), 3)-tableaux on (3, 3, 3, 2, 2, 2): 2 2 2, , , , marked (ρ, l)-tableaux on µ. Definition 4. (T, c) marked (ρ, l)-tableau on µ : T (ρ, l)-tableau on µ, c { i ρ i 0 } Z/lZ. c c : { i ρ i 0 } {,..., l },,. Theorem 5. l m µ cycle type ρ σ S m, l ζl ik Char(M µ (k; l))(σ) = { marked (ρ, l)-tableaux on µ }. k=0, µ Young subgroup,. address: [email protected]

27 COLORED HOOK FORMULA FOR A GENERALIZED YOUNG DIAGRAM KENTO NAKADA INTRODUCTION Let λ be a partition of d, and χ λ the corresponding irreducible character of the symmetric group S d. As is well-known (e.g. [8]), the degree χ λ () of χ λ is given by the hook formula: d! (0.) χ λ () =, v Y λ h v where Y λ is the Young (or Ferrers) diagram of shape λ, and h v is the hooklength at a cell v of Y λ. Since the left hand side of (0.) is equal to the number #STab(Y λ ) of standard tableaux of shape λ, the formula (0.) can be rewritten as: d! (0.2) #STab(Y λ ) =. v Y λ h v The purpose of our talk is to introduce a generalization of (0.2), the colored hook formula, for a generalized Young diagram in the sense of D. Peterson and R. A. Proctor (see [][5]). We stress that the colored hook formula is new even for a Young diagram. Let Π = {α i i I} be the set of simple roots of a Kac-Moody Lie algebra g, and Φ + the set of real positive roots. Then we have the colored hook formula [2]: (0.3) (β,,β l ) Path(λ) l 0 β β + β 2 β + + β l = β D(λ) ( + β where λ is a finite pre-dominant integral weight of g, D(λ) is the diagram of λ, and Path(λ) is a set of sequences in Φ + with certain conditions. In our talk, we shall explain the unexplained notions above and furthur details. And we shall give an example of the colored hook formula in the case of the 2 2 Young diagram. Taking the lowest degree part of (0.3), we have: (0.4) (α i,,α id ) MPath(λ) = α i α i + α i2 α i + + α id where MPath(λ) is the set of elements of maximal length in Path(λ). Taking the specialization α i (i I) of (0.4), we furthur get: #MPath(λ) d! = ht(β), equivalently, (0.5) #MPath(λ) = where ht(β) is the height of β. β D(λ) d! β D(λ) ht(β), β D(λ) ), β,

28 2 KENTO NAKADA According to [], around 989, D. Peterson proved: l(w)! (0.6) #Red(w) = β Φ(w) ht(β) for a minuscule element [] [5] w of the Weyl group of g, where Φ(w) = {β Φ + w (β) < 0} and #Red(w) is the number of reduced decompostions of w. Peterson s formula (0.6) is equivalent to our reduced formula (0.5). The colored hook formula (0.3), in the simply-laced case, was conjectured by N. Kawanaka and S. Okamura in their study [9] [] of game-theoretical aspects of Coxeter groups. We also point out that another proof of Peterson s formula (0.6) has been obtained by S. Okamura [0] using a probabilistic argument. Although Okamura s proof was an original motivation behind the colored hook formula (0.3), our proof of (0.3) is entirely algebraic. We have also succeeded in generalizing the q-hook length formula ( R. Stanley [2] ) to minuscule elements. The proof will be given in a forthcoming paper [3]. REFERENCES [] J. B. Carrell, Vector fields, flag varieties and Schubert calculus, Proc. Hyderbad Conference on Algebraic Groups (ed. S.Ramanan), Manoj Prakashan, Madras, 99. [2] R. P. Stanley, Ordered Structures and Partitions, Ph.D thesis, Harvard University, 97. [3] V. G. Kac, Infinite Dimentional Lie Algebras, Cambridge Univ. Press, Cambridge, UK, 990. [4] R. V. Moody and A. Pianzola, Lie Algebras With Triangular Decompositions, Canadian Mathematical Society Series of Monograph and Advanced Text, 995. [5] R. A. Proctor, Minuscule elements of Weyl groups, the numbers games, and d-complete posets, J.Algebra 23 (999), [6] R. A. Proctor, Dynkin diagram classification of λ-minuscule Bruhat lattices and of d-complete posets, J.Algebraic Combin. 9 (999), [7] J. R. Stembridge, Minuscule elements of Weyl groups, J.Algebra 235(200), [8] B. E. Sagan, The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, Springer, New York, 200. [9] N. Kawanaka, Coxeter groups and Nakayama algorithm, to appear. [0] S. Okamura, An algorithm which generates a random standard tableau on a generalized Young diagram( in Japanese ), master s thesis, Osaka university, [] S. Okamura, to appear. [2] K. Nakada, Colored hook formula for a generalized Young diagrams, submitted to Osaka J. Math. [3] K. Nakada, q-hook formula for a generalized Young diagrams, to appear. GRADUATE SCHOOL OF INFORMATION SCIENCE AND TECHNOLOGY, OSAKA UNIVERSITY, TOYONAKA, OSAKA , JAPAN.

29 A WILD CONFIGURATION CHASE ( ) R d d + 2 d + x x2 d = d = d = 2 d 4 [2, 5] 3 Theorem. R 3 Theorem 2 (Grace[3, 4]). 3 2 a,...,a 6 ;b,...,b 6 Schläfli double six i j a i b j 2 Grace double six Lie d =,3 d R d d + 3 d + 2 [5] [] REFERENCES [] L. Babai and P. Frankl, Linear algebra methods in combinatorics (Preliminary version 2), Department of Computer Science, The University of Chicago (992). [2] K. Bezdek, Z. Lángi, M. Naszódi, P. Papez, Ball-polyhedra, 2006, preprint. [3] J. H. Grace. Circles, spheres and linear complexes, Transactions of the Cambridge Philosophical Society, Volume XVI:53 90, 898. [4] J. H. Grace. Tetrahedra in relation to spheres and quadrics. Proceedings of the London Mathematical Society, Volume S2-7:259 27, 98. [5] H. Maehara, N. Tokushige. On a special arrangement of spheres. Ryukyu Math. J., 9:5 24, Date: August 20, 2007, 02:32pm.

30 Homotopy type of the box complexes of graphs without 4-cycles (Akira Kamibeppu) V V E G = (V, E) graph, graph G,, V (G), E(G)., graph. graph., graph box complex.,. G graph, U V (G). u U, uv E(G) v V (G) U common neighbor. U V (G) common neighbor CN G (U)., CN G (φ) = V (G). u V (G), CN G (u) G u neighbor. U U 2 = φ U, U 2 V (G), V = U U 2, E = {u u 2 u U, u 2 U 2, u u 2 E(G)} G bipartite subgraph (V, E) G[U, U 2 ]. G[U, U 2 ] complete, u U, u 2 U 2, u u 2 E(G)., G[ φ, U 2 ] G[U, φ ] complete. U, U 2 V (G), U U 2 := (U {}) (U 2 {2}) ( V (G) {, 2})., graph G, V (G) {, 2}, V (G) {, 2} B(G) = {U U 2 U, U 2 V (G), U U 2 = φ, G[U, U 2 ] : complete, CN G (U ) φ CN G (U 2 ) } G box complex., ν : V (B(G)) V (B(G)) ; u φ φ u φ u u φ, ν ν = id ( Z 2 -action ) B(G). B(G), Z 2 -action., Z 2 -action. X, Y, Z 2 -action ν X, ν Y., f ν X = ν Y f f : X Y X Y Z 2 -map. graph G χ(g). [3], J. Matoušek G. M. Ziegler,. () graph G, ind Z2 ( B(G) ) := min{ n Z 2 -map f : B(G) S n }, χ(g) 2 ( )., n S n = { x R n+ x = }, a : x x Z 2 -action. (2) graph G 4-cycle, sd B(G) sd B(G) L Z 2 -retraction. Z 2 -index, ind Z2 ( B(G) )., χ(g) 2 ind Z2 ( B(G) ),. graph box complex. graph G, G := { u φ, v φ, φ u, φ v, u v, v u uv E(G)}, B(G), B(G) Z 2 -action G Z 2 -action. X A, f t : X X Z 2 -map X A deformaton retraction {f t : X X} t [0,] X A Z 2 -deformation retraction. 3-cycle, 4-cycle graph box complex,.

31 Theorem ([], Theorem 4.3 ). G 3-cycle, 4-cycle graph., t [0, ] B B 2 B(G), f t (B B 2 ) B B 2 B(G) G Z 2 -deformation retraction {f t } t [0,]. Theorem 2 ([], Theorem 4.4 ). G graph k induced cycle. () G cycle, G k S k S. (2) G, cycle, G 2k S. graph G G uv, graph G uv, G 2 x u, x v 2 ux v, vx u graph G uv. B(G uv ) x, y B(G uv ), x = y x y t [0, ], x = ( t) u φ + t φ x v, y = ( t) x u φ + t φ v t [0, ], x = ( t) v φ + t φ x u, y = ( t) x v φ + t φ u. Proposition 3 ([2], Proposition 4.5 ). G uv G 4-cycle, B(G uv ) / B(G). Remark 4 (for Proposition 3). G uv, G 4-cycle, B(G uv ) / B(G)., G 4-cycle C 4, uv. G uv 5 path P 5. box complex, B(C 4 ) 2 3-disk, B(P 5 ) 2 2-disk.,, B(P 5 ) / B(C 4 ). C 4 P 5 u v u x v x u v B(C 4 ) B(P 5 ) φ v φ u φ x v φ v φ x u φ u u φ v φ u φ x u φ v φ x v φ Proposition 3, 4-cycle graph box complex. Theorem 5 ([2], Theorem 4.7 ). graph G 4-cycle, G B(G) Z 2 -deformation retract. J. Matoušek G. M. Ziegler (2) sd B(G) L,, L sd G., L = sd G = G. Theorem 5, graph G 4-cycle, L B(G) Z 2 -deformation retract., Theorem 5. References [] A. Kamibeppu. The box complex of graphs without 3 and 4-cycles, preprint. [2] A. Kamibeppu. Homotopy type of the box complexes of graphs without 4-cycles, preprint. [3] J. Matoušek and G. M. Ziegler. Topological lower bounds for the chromatic number: A hierarchy. Jahresbericht der Deutschen Mathematiker-Vereinigung, 06 (2004), no.2,

32 ALGEBRAIC SHIFTING OF STRONGLY EDGE DECOMPOSABLE SPHERES ( ) face vector 970 Stanley, face vector., ( ) face vector McMullen g-condition ( (A), (B) ).,. face vector. [n] = {, 2,..., n} Γ [n] (i), (ii) : (i) {i} Γ for i =, 2,..., n. (ii) F Γ G F G Γ. Γ Γ face, face facet. k, f k (Γ) Γ F F = k (, F F ). Γ dim Γ = max{k : f k (Γ) 0}. Γ (d ), f(γ) = (f 0 (Γ),..., f d (Γ)) Γ f-vector (face vector). f-vector, f-vector h-vector. Γ (d ), Γ h-vector h(γ) = (h 0 (Γ),..., h d (Γ)) : h i (Γ) = i ( ) d j ( ) i j f j (Γ) and f i (Γ) = d i j=0 i j=0 ( ) d j h j (Γ) d i f (Γ) =., f-vector h-vector. 97 McMullen d h-vector. (A) h i = h d i for i = 0,,..., d; (B) (h 0, h h 0,..., h d 2 h d 2 ) M-vector, multicomplex face vector., multicomplex Σ, F Σ G F G Σ., (A) Dehn Sommerville equation, ( ). McMullen 980 Stanley [6], Billera Lee []. Stanley, h-vector. strongly edge decomposable h-vector (A), (B). strongly edge decomposable. Γ. Γ pure Γ facet. Γ F [n] link, lk Γ (F ) = {G [n] \ F : G F Γ}. i < j n, Γ i, j contraction i j [n] \ {i} C Γ (ij) = {F Γ : i F } {(G \ {i}) {j} : i G Γ}. Γ {i, j} [n] Link condition () lk Γ (i) lk Γ (j) = lk Γ (ij). ( lk Γ (i) = lk Γ ({i}), lk Γ (ij) = lk Γ ({i, j}).) The author is supported by JSPS Research Fellowships for Young Scientists.

33 . [n] pure Γ strongly edge decomposable (i) Γ = { } Γ simplex boundary; (ii) Γ {i, j} [n] Link condition, C Γ (ij) lk Γ (ij) strongly edge decomposable., strongly edge decomposable. strongly edge decomposable. (, Nevo [5] Γ PL- {i, j} Link condition C Γ (ij) PL- ).,,. (I) strongly edge decomposable h-vector (A) (B). (II) strongly edge decomposable.,. (I)., (II) Kalai squeezed sphere [3] strongly edge decomposable (squeezed (d )-sphere, d 5, d )., strongly edge decomposable., strongly edge decomposable ([2, 7]). strongly edge decomposable, (I). ( (A), (B). (B).), (I).., strong Lefschetz, (exterior) algebraic shifting. Lefschetz (strongly edge decomposable strong Lefschetz ), algebraic shifting. algebraic shifting,, Γ shifted (Γ). ( [4]. f(γ) = f( (Γ)).) Kalai Sarkaria, Γ [n] (d ) (2) (Γ) (C(n, d)). ( C(n, d) n cyclic d-polytope. (C(n, d)).) Γ (2) h-vector (A), (B). strongly edge decomposable (2),.. (i) Γ [n] (d ) strongly edge decomposable, (Γ) pure, i = 0,,..., d h i (Γ) = h d i (Γ), (Γ) (C(n, d)). (ii), Σ pure shifted (d ) i = 0,,..., d h i (Σ) = h d i (Σ) Σ s (C(n, d)), strongly edge decomposable Γ (Γ) = Σ. strongly edge decomposable ( ) algebraic shifting., Γ, (Γ) pure h-vector (A), Kalai Sarkaria, algebraic shifting. References [] L.J. Billera and C.W. Lee, A proof of the sufficiency of McMullen s conditions for f-vectors of simplicial convex polytopes, J. Combin. Theory Ser. A 3 (98), [2] T.K. Dey, H. Edelsbrunner, S. Guha and D.V. Nekhayev, Topology preserving edge contraction, Publ. Inst. Math. (Beograd) (N.S.) 66(80) (999), [3] G. Kalai, Many triangulated spheres, Discrete Comput. Geom. 3 (988), 4. [4] G. Kalai, Algebraic shifting, in: T. Hibi (Ed.), Computational Commutative Algebra and Combinatorics, Adv. Stud. Pure Math., Vol. 33, 2002, [5] E. Nevo, Higher minors and Van Kampen s obstruction, arxive:math.co/060253, Math. Scand., to appear. [6] R.P. Stanley, The number of faces of a simplicial convex polytope, Adv. Math. 35 (980),

34 "!$#&% '"(*)$+&)$+&,.-&/0*243"5$ : ;=<?>@;BADCFEHGJILKBEHMNGOMOP=<QIR<S>TIRUWV X$Y[Z4\"Y[] ^"_`badc"ebfhg*ij )9khlnm&o.prqs.thuwvhx azyz{&`b o.p}q~sbt & yz{&` nƒ_ 4 m} ˆ Š F i* b u _. & wi*a4 $ m š œ & dx$y \&Y l. žu Ÿ. `._. & u ]4 & *y X$Y Z \"Y $ $. zª «D F ²±²Œ³ «±Žµ ib b u}¹ a o.p}q~s.t œ»º ib. ¼º ½ ¾ ah ¹ X"Y*i* b ÁÀ a ½  ¹ a4 žãåäæ»çéèn bi* b 9Ê[ k ÌË º Í& khî$ï \$Y žãñðò»çqi*a µó žãñôb»ç u Æ]ÖÕ µø 9 dù k \"Y*i.a4Ú&Û9ÜÝ.i. d µøµó žãßþà»ç ¹á Õ µø šbœh & dù k \"Y.i9a Ú&Û9ÜzÝ.i* 4 m}â  yã uzä az ¹ Ú&Û*ÜzÝ*ib u _Ì å Šæ"ç $* ^ Ê xèo p}qs.têé ]&f ƒ4`$ëzì[z$] kní `*_. "î$ï Y[ ðzñ"ò Ï9ó i* rô" ] ¹ a Ú"Û*ÜÝõÈ öõ ¹ø$l9À ø Y u[ùqúhûàü u _ý } u þìÿ `&^ ¾ a ½  a4ë 9 ø"l ^ Ê x"ø Y[ hðzñ"ò Ï&ó*¹ Ú&Û9ÜzÝ9i b u _ý m _b u a 9 ø$l ^nê x 9 ø Y[ dô$ ] ¹ a [Ê[ ] _ " u i ä 4 9 ø"l ½h ¹ * ø Y ð$ñ"ò Ï9ó Ú&Û*Ü Ý.i. u}¹ a X&Y i. À a ½h ¹ a m Ë º ø Y udûàübk Î"Ï \&Y ] Ï9ó i ä a ÿ x Ú&Û9ÜzÝ*ib b $ u i* 4 Ê ¾ _ u ƒà`*a S Ø Fµ ص ± b à ÆX YbZd\"Y "!$#&%'%)(+*,%)# i. * ur¹ aà o pwqs t œjº i ¼º ½¾ az ¹ X&Y.ib À a ½  ¹ az žãtä4»ç È [i. *Ê k n Ë º Í* kzî$ï \$Y žã ÐÒ»Ç i*a µó žã ¹ Õ µø 9 dù k \"Y*i.a -S Ø = i* 4 z»ç ¹ Õ µø 9 dx"y*ib b 4 µøµó žãßþà»ç ¹á Õ µø šbœh & dù k \"Y.i* 4 m}â  y u4m _Ì. ¹ a/. dú&û&üý 0 æ9ç ] ^"_z`*a4»ç ¹ X&Y Òobpwqès.t œ º i. b u _ 243 mhº65 `*_[ 4 87:9&]"a -S Ø = È ö Ú&Û9ÜzÝ[azi* 4 <;=S FµØ صرž¹ a ohpåq szt?>a@qã Ð-@ Ç ÐCBCBCB@Ð-@ED i&agfih/jbë à ÄLCLCL ÄM@$NPO à ÞM@QN Õ µ š.œ 9 iù[a u _ý Ê ] æ$çsr $ u î _ a T khæ&ç ib b 4 & ø$lvuåø Y[ ð ñ ò Ï"ó -S FµØ صر ^ Ê x Ú&Û&Ü Ý0b]$fbƒd`*a W œyxtu W Ë X i ¹ æ6z m?[ ƒ  \ ] ^+_ W œyx " ø"l`ú ø Y hðzñ$ò Ï$ó -S Ø a F i9 b ac œ " dfe )g hujinm lk  Î$Ï. ]m4kn ½ Âo xip ½  ¹rqtsu} wv ] Knƒ `.aëxlzy 'v {} 'v Û~.y  ƒza O 'vz ß¹Iv m Ú9Û9y i é a y 'v ¹Iv é i* 4 \ ]ƒ _ W Ë X & ø"lvuáø Y[ hð$ñ ò Ï&ó Ú"Û9ÜzÝ*i. b a œ 9 dfe )gh uji m k  Î$Ï. ]m4kn ½ Âo xip ½  ¹rqtsu} wv ] Knƒ `.aëxlzy 'v {} 'v Û~.y  ƒza O 'vz ß¹Iv m Ú9Û9y i é a y 'v ¹Iv é i* 4

35 o x p / é*¹ a/y 'v È œ uhä 7 9 k o x p i* ¾ a ) ä k Æ\ k o x p ] k í `*_ o xapàm ðzñ$ò Ï"ó œ & de ]è ô$ a i$é m î í  \ k d à t.[ æ6z [ ƒà`*_* Ë L y 'vz { 'v.u _ ¹ a ÿ  énm*º o x p}m ~  k"] l3$_ º i é o x p Î Ï ] ] k d À mt[ ƒ `*_[ u " u i ä 4 a. Ë º æz ] ¹ ahð ñ ò Ï"ó "! ]$#% º _ `*_b & '#% k _ ô ¹( o xrp ¹ i i *)bi ä bƒ À ƒ a -S Ø =,+ Ú9Û*Ü Ý u _ -# % /. R `b_ z i.a& [ 0/ i"é k _ u o x p m k _ u _Ì 32 5 i [ "# % u ƒh` ¹ -S Ø a F Ê ¾ Ú&Û&ÜÝ 54 _" i*a æ6z Ëê æ Z œ Ê ¾ 76*8 R `&_ à $ƒ À ƒa ¹ 9 ÿ æ6z i :& ¹ -+ ŒŽ i. b 4 u _ ¹ a ;*<[ "=5> urk í  W X `*_[ Ú9Û@? m _. u a ( o x p4v ] Knƒd`.a 9 ø"l U ø Y - Ø F k ðñ ò Ï"ó i9a vám ËML y 'v BA i i œ " de ] 5)*y[ 9 Æ m $ u i ä À ÿ i. 4 m o x p C À ÿ ` ½ u k u a Ê k@d ] k 4 EF _ o xip4v GA i m í ` -S Ø = ½4 ¹ Ú9Û9Ü Ý k 9 ø$l U ø Y ð$ñ ò[ œ & dfeh ] m knji[ u i ä  k9 LKÏ # % ¹ aëlpy 'v M{ i. 4 R `ba i o xip -S F ½4 ¹ Ú9Û&Ü Ý k 9 ø&l U ø Y hð$ñ ò Ï"ó œ " 6dfe ]m k n k À À*¹4Ï&À í  a unm í `9_  afý i k _. u ] O*P5Q _  R b a"s. o x p ¹ ; u é ËÉi. 4 i*at i im k n Ib u ÜzÝ9i b bƒ À ƒzaw X 4Ú"Û? m ^ u y u a ý à 7U o xipdm m4knvi4ô Ê ¾ î o pwqs t m? Ìu y[.ê ] M 2 4 º ½ ¾ at 6 é Ê ¾ " n -W[ƒYXnƒ Go x p d\ R4m$ $ u ] Ê ¾ a o x pæm m k nzi ] bk o pwq~s t [ é m"$\ $ " u i ä zi ¹ k _ ÀÌu:M* 4 o x pdm œ 9 d6e ]m4knhi  k&] *bk o pwqs t [ é \ ¾ ]*fbƒ4` ¹ a ] µø _^ W T X ] ^9_`baf & ø&l ` ðzñ"ò Ï&ó œ * 6d e ] o xip vˆm m4k n I  k"] *k obprqès.tžéba}¹ y 'v dc Ë Ãfehgjilk mwâ  y u _Ì w u [ R `9_b 9ƒ À ƒa[ ¹À*k ¾nm _ B D F Õ ib b d À ÿ Ÿ*  _@o$p u ƒ4`.a éìu i é ]$q `.a º o xip d\ R mr y 5s m q a o x p}m & ø"l -S Ø a F ½Æ ¹ Ú&Û"ÜhÝ Ák ðzñzò Ï&ó œ & de ] m knji" h] *kbo*p qès*téé "S3 m " u i äæk _ À a u _Ì Æ udmt u ƒ4` v  _z R b a: é Ë i. * o x p ]$f*ƒd` ¹ýŒ ±Žµ D +W =±-W _^D ] Êz r ƒ b zi.a m _h`5w T*i ädk _ Zx Àzy {} ~,ƒ: ˆ Š ŒŽB š œn Ÿž ŽB G j ª «l ± ³² µ ² ¹ ºl» n µ¼7² ¼ œ µ¼ º ½ ¾lÀ Á ÂBÃ Ä Ã Å Á Æ Ç ÈÊÉšË ÌÍÁ ÀhÈÏÎhÐ ÑšÑYÒÔÓ Õ Õ ˆ Öh lølù Ú ÍØ Ûµˆ Ž ÓŠ ž Ž G j µ Ü ÞÝ Ž ß à áâ µ lãä œ å æ µ¼n ± ³² µ ² å ¹» ç _ÄlÃÜèéÉÜÁÌnêšëµìjÁÀhíéîGË Æ-ÈÊï ð ÎjË̪ÈÏÁÉ Ð ñlò ÒÔÓ Õ Õ Ø Öh lóôù ó ó õ ó Ž ó Š ž Ž G j ö ø Ž ž Žúùš œ»» úûg ç ¹š ² µ n üâ µ ý µ¼ f¹ µ» ná ² à ² µ f² œ: ü üþ»á ç¼lœ ç Üÿ Ë ÌÊëµÃ ÃÜѵò YÒÔÓ Õ Õ ÕôÖh ܈çÚ Û jˆ Ùlˆ Ž Ø Šß_Ž éž Ýd œ± lã n f å üä² œ ý ² µ â f ¹µ¹± f² œ -œ àü ìjáæãêµájâ Á à YÒªÓ Õ Õ ˆçÖ ôó Û Íó Û õ Ž