ランキングパタンの数え上げ

(1)

ランキングパタンの数え上げ

徳重典英

(

^琉球大学

)

2010

^年

7

^月

31

^{日高知大学}

(2)

この発表は

竹村彰通

(

^東大

)

^紙屋英彦

(

^岡山大

)

の両氏との共同研究に基づくものです。

(3)

定義と問題

理想点

y ∈ R

^{をもつ個人が}

m

^{個の選択肢}

x ₁ , . . . , x _m ∈ R

^を

y

^{からの距離によって}

並べ替える。

x ₁ x ₂ x ₃

y

(4)

入力

: x = (x ₁ , . . . , x _m ) ∈ R ^m and y ∈ R

出力

:

^{ランキング}

f (x, y ) := (i ₁ , . . . , i _m )

は次の条件で決まる：

| y − x _i ₁ | < | y − x _i ₂ | < · · · < | y − x _i _m | .

(5)

x ₁ x ₂ x ₃ y

f (x, y ) = (2, 1, 3) = 213

x ₁ x ₂ x ₃ z

f (x, z ) = (3, 2, 1) = 321

(6)

x

^{のランキングパタン}

F (x) := { f (x, y ) : y ∈ R }

x ₁₂ x ₁₃ x ₂₃

123 213 231 321

x ₁ x ₂ x ₃

F (x) = { 123, 213, 231, 321 } .

(7)

x

^と

x ⁰

のランキングパタンが同じ

⇐⇒

中点集合

( _x

2 )

と

( _x ⁰

2 )

の並び方が同じ

x ₂₃ x ₁₄

x ₁ x ₂ x ₃ x ₄

x ₁₄ x ₂₃

x ₁ x ₂ x ₃ x ₄

(8)

F ^m

^を

m

個の選択肢から得られるランキングパタン全体とする。

F ^m = { F (x) : x = (x ₁ , . . . , x _m ) ∈ R ^m , x ₁ < x ₂ < · · · < x _m }

問題

:

ランキングパタンの総数を数えよ。

r (m) := |F ^m | .

(9)

主結果

(Kamiya-Takemura-T 2010 ⁺ )

ある正定数

c ₁ , c ₂

^{が存在して}

(c ₁ m ² ) ^m < r (m) < (c ₂ m ² ) ^m .

この問題は

( _m

2 )

個の中点

x _ij = ^x ⁱ ^+x ₂ ^j

^{たちの可能な} 並び方の総数を問うている。

= ⇒

^{中面配置の導入}

(10)

R ^m

における以下の超平面たちを考える。

{ x _i = x _j : 1 ≤ i < j ≤ m }

(m

個の選択肢は全部異なる

)

{ x _i + x _j = x _k + x _` : i, j, k, l all distinct }

(

^{中点は全部異なる}

)

中面配置

(the mid-hyperplane arrangement):

M ^m := (

^{上記の超平面全体}

)

(11)

M ^m = { x _i = x _j } ∪ { x _i + x _j = x _k + x _` } .

|M ^m | ≈ cm ⁴ .

要点

: x, x ⁰ ∈ R ^m

^に対して

x

^と

x ⁰

^が

M ^m

^{の同じ部屋}

⇐⇒

x

^と

x ⁰

のランキングパタンが同じ、即ち

(12)

復習

r (m) = # { F (x) : x ∈ R ^m , x ₁ < x ₂ < · · · < x _m } .

定理

(Kamiya-Orlik-Takemura-Terao 2005)

r(m) = ( M ^m

^{の部屋の個数}

)

m! .

r (3) = 1, r (4) = 2, r (5) = 12, r(6) = 168,

r (7) = 4680, r (8) = 229386, r (9) = 18330206.

(13)

主結果の証明

(c ₁ m ² ) ^m < r (m) < (c ₂ m ² ) ^m .

上界の証明には、

M ^m

^{の部屋数の上界}

を超平面の個数を使って評価する。

(14)

平面上に

n

^{本の直線をひく}

(

^{一般の位置}

)

^。

n

^{本目の直線は他の}

n − 1

^{本の直線と交わり、}

新しく

n

個の領域を作る。領域の個数

g (n)

^は

g (n) = g(n − 1) + n.

1 2

3

4

(15)

R ^d

^内の

n

^{枚の超平面}

:

^{部屋の個数}

g _d (n)

g _d (n) = g _d (n − 1) + g _d ₋ ₁ (n − 1)

= ( _n

0 ) + ( _n

1 ) + · · · + ( _n

d

) ≤ (en/d) ^d

R ^m

^内の

M ^m

^の場合

d = m, n = |M ^m | ≈ cm ⁴

を

KOTT

^{の定理に代入して}

g ( |M | ) (ecm ⁴ /m) ^m

(16)

下界を示すため、

r(m + 1) > cm ² × r (m),

がいえると、ここから次を得る：

r (m) > (c ₁ m ² ) ^m .

x ₁₄

x ₁ x ₂ x ₃ x ₄

(17)

x ₁₅ x ₅

x ₀₄

x ₀

(18)

x ₁ < · · · < x _m

^{を固定する。}

x _1m

^{より大きい中点} が

j

^{個あるとしよう。}

x _m+1 (> x _m )

^を

x = (x ₁ , . . . , x _m )

^に加えて

j + 1

個以上の新しいランキングパタンを得る。

x ₀ (< x ₁ )

^を

x = (x ₁ , . . . , x _m )

^に加えて

( _m

2 ) − j

個以上の新しいランキングパタンを得る。

平均すると、

x ₀

^又は

x _m+1

^{を加えて、}

1 2

( _m

2 )

個以上のランキングパタンを得る。

r (m + 1) ≥ ¹ ₂ ( _m

2 ) × r(m) ≈ c ₁ m ² × r(m).

(19)

注意

(c ₁ m ² ) ^m < r (m) < (c ₂ m ² ) ^m .

c ₁ ≈ 3/(4e ² ) = 0.1, c ₂ ≈ e ² /8 = 0.92.

問題

1.

上界、下界を改良せよ。

問題

2.

極限

lim r (m) ^1/m

m ²

^{が存在するか}

?

(20)

ランキングパタンの数え上げ