プログラム＋予稿集 - Hiroshima University

2016
2016
8
23
15 : 50 − 16 : 30
16 : 40 − 16 : 50
−
−
−
(1)(
−
(10
−
(10
16 : 55 − 17 : 15
17 : 25 − 17 : 40
23( )-26( )
( )
14 : 55 − 15 : 00 −
15 : 00 − 15 : 40
8
)
)−
(
−
)−
(
(
)
)
(10
POSET
− 18
)−
(2)(
(
17 : 45 − 18 : 00
)
)
SCHEMOID
)
−
2016 8 24 ( )
9 : 00 − 9 : 20
9 : 25 − 9 : 45
10 : 00 − 10 : 20
14 : 00 − 14 : 20
Ehrhart
−
(15
(
16 : 25 − 16 : 45
)
(
)
δ
−
Ehrhart
(15
)−
(
)
(
)
(
ABD
−
)
Coxeter
2
−
(
)
Some adjacency properties of graphs and tournaments
(
)
d-defective k-fold coloring
−
(15
)−
(
)
Robinson-Schensted
15 : 25 − 15 : 45
16 : 00 − 16 : 20
)−
Riemann
14 : 25 − 14 : 45
15 : 00 − 15 : 20
)
3
11 : 25 − 11 : 45
11 : 50 − 12 : 05
)
(
10 : 25 − 10 : 45
11 : 00 − 11 : 20
(NTT
(
)
Jacobi-Trudis’s fomula
−
(15
)−
(
)
(
)
Pieri rules and oscillating tableaux
−
(15
)−
17 : 00 − 18 : 00
(
(
OK)
)
SELF-REPRODUCING
(
)
K1,3 -free
−
2016
8
25
9 : 00 − 9 : 40
9 : 50 − 10 : 30
10 : 40 − 11 : 20
11 : 35 − 11 : 55
−
( )
−
−
−
−
(1)(
(10
−
)
)−
(2)(
(10
)
)−
(3)(
(15
(
)
)−
)
On certain transformations on link diagram and their algebraic structures
12 : 00 − 12 : 10
14 : 00 − 18 : 00
Minty
(
−
−
−
(
)
)−
20 : 20 − 20 : 30
20 : 35 − 22 : 00
2(
(
)
(
2016
8
26
)
( )
9 : 00 − 9 : 20
(
)
9 : 25 − 9 : 45
(
)
10 : 00 − 10 : 15
−
(15
11 : 05 − 11 : 25
11 : 30 − 11 : 50
)−
(
10 : 20 − 10 : 40
10 : 45 − 10 : 55
OK)
)
(
)
(
)
Latin Square and Entropy and Doubly Stochastic Transicions
−
(10
(
)−
)
Hom
(
)
一般講演予稿
Pieri Rules and Oscillating Tableaux
名古屋大学多元数理科学研究科
岡田 聡一 (Soichi OKADA) ∗
!
非負整数の広義単調減少列 λ = (λ1 , λ2 , · · · ) (λ1 ≥ λ2 ≥ · · · ≥ 0) で i≥1 λi < ∞ とな
!
るものを分割 (partition) という．分割 λ に対して，成分の総和 |λ| = i≥1 λi を λ を大
きさといい，0 でない成分の個数 l(λ) = #{i : λi ̸= 0} を λ の長さという．また，格子点
の集合
D(λ) = {(i, j) ∈ Z2 : 1 ≤ i ≤ l(λ), 1 ≤ j ≤ λi }
を λ の Young 図形と呼び，格子点の代わりに単位正方形をおいて図示する．分割とそ
の Young 図形を同一視することが多い．分割 λ, µ に対して，D(λ) ⊃ D(µ) となるとき
λ ⊃ µ と表す．
分割 λ の Young 図形の正方形に数字 1, 2, · · · , |λ| を 1 つずつ書き込んで，2 つの条件
(i) 各数字は 1 回ずつ現れる.
(ii) 各行，各列は単調増加である.
をみたすようにしたものを，λ を枠とする標準盤 (standard tableau) という．分割 λ
を枠とする標準盤 T は，分割の増大列 (λ(i) )ki=0 （ただし k = |λ|）で λ(i) ⊃ λ(i−1) ,
|λ(i) | = |λ(i−1) | + 1 (1 ≤ i ≤ k) をみたすものと同一視できる（T において数字 1, 2, · · · , i
が書き込まれている部分が，λ(i) の Young 図形である）．
振動盤 (oscillating tableau) とは，標準盤の一般化であり，次のように定義される．分
割 λ と非負整数 k が与えられたとき，分割の列 (λ(i) )ki=0 で，2 つの条件
(i) λ(0) = ∅, λ(k) = λ.
(ii) λ(i) ⊃ λ(i−1) , |λ(i) | = |λ(i−1) | + 1，あるいは，λ(i) ⊂ λ(i−1) , |λ(i) | = |λ(i−1) | − 1.
をみたすものを，λ を枠とする長さ k の振動盤と呼ぶ．このとき，Krattenthaler [2]，
Burrill–Courtiel–Fusy–Melczer–Mishna [1] は独立に，全単射を構成することによって，次
の定理を証明している．
定理 1. ([2, Theorem 3], [1, Theorem 1]) 非負整数 k, n, m が与えられたとき，次の 2 つ
の集合の元の個数は等しい：
(a) 1 行の Young 図形に対応する分割 (m) を枠とする長さ k の振動盤 (λ(i) )ki=0 で，
l(λ(i) ) ≤ n (0 ≤ i ≤ k) をみたすもの全体のなす集合．
(b) |λ| = k, l(λ) ≤ 2n, c(λ) = m となる分割 λ を枠とする標準盤全体のなす集合．
ここで，c(λ) は λ の Young 図形において長さが奇数である列の個数である．
この講演では，古典群の表現論を利用することによって，この定理がどのように証明で
き一般化できるかを解説する．この一般化の鍵となるのが，自然表現の対称テンソル積表
現・交代テンソル積表現と与えられた既約表現とのテンソル積の既約分解を記述する Pieri
型の公式である．
例えば，直交群の表現論を用いると，次の定理を証明することができる．
（上の定理 1 は
斜交群の表現論を用いて証明できる．
）
∗
[email protected]
定理 2. 非負整数 k, N , m が与えられたとき，次の 2 つの集合の元の個数は等しい：
(a) 1 列の Young 図形に対応する分割 (1m ) を枠とする長さ k の振動盤 (λ(i) )ki=0 で，
(λ(i) )′1 + (λ(i) )′2 ≤ N (0 ≤ i ≤ k) をみたすもの全体のなす集合．
(b) |λ| = k, l(λ) ≤ N , r(λ) = m となる分割 λ を枠とする標準盤全体のなす集合．
ここで，λ′j は λ の Young 図形の第 j 列の長さであり，r(λ) は λ の Young 図形におい
て長さが奇数である行の個数である．
参考文献
[1] S. Burrill, J. Courtiel, E. Fusy, S. Melczer, and M. Mishna, Tableau sequences, open diagrams, and Baxter families, to appear in European J. Combin,
arXiv:1506.03544.
[2] C. Krattenthaler, Bijections between oscillating tableaux and (semi)standard
tableaux via growth diagrams, to appear in J. Combin. Theory Ser. A,
arXiv:1412.5646.
[3] S. Okada, Pieri rules for classical groups and equinumeration between generalized
oscillating tableaux and semistandard tableaux, arXiv:1606.02375.
Latin Square and Entropy in Doubly Stochastic Transitions
Nozomu Ochiumi (Shonan Institute of Technology)
Email: [email protected]
Abstract
A set {Π1 , . . . , Πr } of r × r permutation matrices is called latin square if the table a1 Π1 +
· · · + ar Πr is a latin square of r different “letters” a1 , . . . , ar . We consider a Markov chain
with states 1, . . . , r and with a transition matrix represented as a convex linear combination
p1 Π1 + · · · + pr Πr on a latin square {Π1 , . . . , Πr }. We find an interesting class of latin
squares, any convex linear combination on each of which becomes a transition matrix that
ensures H(Xn |X0 = 1) = · · · = H(Xn |X0 = r) for n = 1, 2, . . . for any initial distribution.
This sameness of the individual entropies is then shown to be a sufficient condition for the
sequence H(Xn |X0 ), n = 0, 1, . . ., to be convex upward.
Let X0 , X1 , . . . be a homogeneous Markov !
chain with!state space {1, . . . , r} and with r × r
doubly stochastic transition matrix P = (pij ), j pij = i pij = 1, i, j = 1, . . . , r. Our interest
is in the behavior of the sequence of the n-step conditional entropy:
"
(n)
H (n) ≡ H(Xn |X0 ) =
P {X0 = j}Hj , n = 0, 1, . . . ,
j
where
(n)
Hj
≡ H(Xn |X0 = j), j = 1, . . . , r.
From the well-known fundamental entropy inequality H(p) ≤ H(pP ) (for any probability rvector p) as noted in §6 of Shannon [1], we readily see that the sequence H (n) is non-decreasing,
for we have
(n)
(n)
(n)
(n+1)
(n+1)
Hj = H(pj ) ≤ H(pj P ) = H(pj
) = Hj
,
(n)
where pj is the j-th row of P n (P 0 = I).
The sequence H (n) , however, does not always form a convex upward sequence, i.e., the sequence
satisfying
H (n+1) − H (n) ≤ H (n) − H (n−1) , n = 1, 2, . . . .
(1)
In this paper we are especially concerned with following symmetric sufficient condition for (1) to
hold for any distribution of X0 :
(n)
H1
= · · · = Hr(n) , n = 1, 2, . . . .
(2)
(n)
If (2) holds, we have H (n) = Hj for j = 1, . . . , r and the chain starting at any state will show
an identical entropic behavior. We can actually prove the following
Theorem 1. If (2) holds, we have the upward convexity (1) for any initial distribution.
An illustrative example for such Markov chains may be a card-shuffling process as described
in [2]. Let T be a stochastic shuffle (permutation) of a deck of N cards and X0 be an initial state
(there are r = N ! possible states) and T is applied to, but independently of, Xn−1 to produce
Xn = T Xn−1 , n = 1, 2, . . ., then we can show that the transition matrix is doubly stochastic, and
obviously (2) holds.
Now let {Π1 , . . . , Πr } be a set of r × r permutation matrices such that the elements of the
sum Π1 + · · · + Πr are all 1. We may then call such a set latin square of order r, because the
linear combination a1 Π1 + · · · + ar Πr represents a latin square of r different “letters” a1 , . . . , ar .
Moreover, if a latin square becomes a group under the matrix multiplication, we call it latin
group. Using the Cayley’s theorem we can find, for an arbitrary group G of order r, a latin group
{Π1 , . . . , Πr } isomorphic to G.
It is shown in [3] that (2) holds when P can be expressed as a convex linear combination on
a latin group {Π1 , . . . , Πr }, i.e., when P can be written in the form
P = p1 Π1 + · · · + pr Πr
for some probability vector (p1 , . . . , pr ) (reminiscent of the Birkhoff-von Neumann’s theorem on
doubly stochastic matrices).
The following theorem provides a partial solution to the problem (raised in [3]) of characterizing the class of latin squares each of which makes (2) hold for any transition matrix expressed
as a convex linear combination on that latin square.
Theorem 2. Let L0 = {Π1 , . . . , Πr } be a latin group of order r. If a permutation matrix Π0
satisfies Π0 Πj Π−1
0 ∈ L0 for j = 1, . . . , r, then (2) holds for any Markov chain with a transition
matrix represented as a convex linear combination on the latin square L1 = {Π0 Π1 , . . . , Π0 Πr }.
Note that the set {Π0 | Π0 L0 Π−1
= L0 } of all Π0 satisfying the condition stated in the
0
theorem is the normalizer of the group L0 .
Corollary 1. Let L0 = {Π1 , . . . , Πr } be a latin group of order r and Π0 be a permutation matrix.
If each matrix belonging to L1 = {Π0 Π1 , . . . , Π0 Πr } is symmetric, then (2) holds for any convex
linear combination on L1 .
References
[1] C. E. Shannon, “A mathematical theory of communication,” Bell System Tech. J., 27(1948)
379–423.
[2] T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, Inc.,
1991.
[3] Y. Horibe, “On the increase of conditional entropy in Markov chains,” Trans. of the Tenth
Prague Conference on Information Theory, Statistical Decision Functions, Random Processes,
pp.391–396, Publishing House of the Czechoslovak Academy of Sciences, 1988.
歪平面分割の積公式について
京都大学大学院情報学研究科 上岡修平 1
歪平面分割の積公式
1
r と c を非負整数とする. µ = (µ1 , . . . , µr ) ⊆ (cr ) を (整数) 分割とする. µ のヤング図形は r × c の
長方形に収まる. 非負整数の配列 π = (πi,j )(i,j)∈(cr )/µ で次の条件を満たすものを型 (shape) (cr )/µ
の歪平面分割 (skew plane partition) という: πi,j ≥ max{πi+1,j , πi,j+1 } すなわち π は各行および
各列について単調非増加である. 例えば
⎛
⎞
- - - 2 2
⎜
⎟
⎜ - - 3 1 1⎟
⎜
⎟
π=⎜
⎟
⎝ - 3 2 1 0⎠
3 2 0 0 0
(1)
は型 (5, 5, 5, 5)/(3, 2, 1, 0) の歪平面分割である.
歪平面分割について次の積型母関数が知られている.
定理 1 (Gansner [1]). r と c を非負整数とする. µ = (µ1 , . . . , µr ) ⊆ (cr ) を分割, µ′ = (µ′1 , . . . , µ′c ) ⊆
(rc ) を µ と共役な分割とする. このとき
'
r−1
(
tr (π)
yk k
π k=−c+1
(
=
(i,j)∈(cr )/µ
−1
i
(1 − [y]i−1−µ
−j+1+µ′ )
j
(2)
が成り立つ. ただし左辺の和は型 (cr )/µ の歪平面分割 π すべてにわたってとる形式和である. な
)
*n
お歪平面分割 π に対して trk (π) = j−i=k πi,j である (π の k トレース). また [y]n
m =
k=m yk で
ある.
2
離散二次元戸田分子との関係
次の差分方程式により記述される離散力学系を離散二次元戸田分子という [2]:
(s,t)
a(s,t+1)
+ b(s+1,t)
= a(s,t)
+ bn+1 ,
n
n
n
(s+1,t)
a(s,t+1)
bn+1
n
(s, t) ∈ Z2 ,
n=
(s,t) (s,t)
= an+1 bn+1 ,
(s,t)
0, 1, 2, . . . , b0
(3a)
(3b)
= 0.
(3c)
µ = (µ1 , µ2 , . . . ) を分割, µ′ = (µ′1 , µ′2 , . . . ) を µ と共役な分割とする. αi,j (i, j = 1, 2, . . . ; (i, j) ̸∈ µ)
を次により定義する:
(i,j)
αi+k,j+k = ak−1
=
1 Email:
(i,j−1)
bk
for i, j = 0, 1, 2, . . . with µ′j+1 ≤ i < µ′j and k = 1, 2, . . . ;
(4a)
for i, j = 0, 1, 2, . . . with µi+1 < j ≤ µi and k = 1, 2, . . . .
(4b)
[email protected]
ただし µ0 = µ′0 = ∞ である. さらに非負整数 n を固定し, βi,j,k (i, j = 1, 2, . . . ; (i, j) ̸∈ µ;
k = 1, 2, . . . , n) を次により定義する:
βi,j,k =
αn+i−k,n+j−k+1
.
αn+i−k,n+j−k
(5)
π を型 (cr )/µ で成分が高々n の歪平面分割とする. π の重み w(π) を次で定義する:
w(π) =
(
πi,j
(
(i−1,j)
n
(
ak−1
(
βi,j,k .
(6)
(i,j)∈(cr )/µ k=1
定理 2 (K.). r と c と n を非負整数, µ ⊆ (cr ) を分割とする. このとき
'
w(π) =
π
(7)
(i−1,j−1)
(i,j)∈(cr )/µ k=1
ak−1
が成り立つ. ただし左辺の和は型 (cr )/µ で成分が高々n の歪平面分割 π すべてにわたってとる.
離散二次元戸田分子 (3) は次の特殊解を持つ:
s+n−µ
s−µ
s+n+1
s+1
a(s,t)
= [y]s+1−µs+1
(1 − [y]−t−n+µ
′
n
t+n+1
−t+µ′t+1
b(s,t)
= [y]s+n−1−µs+n (1 − [y]
n
),
−t−1+µ′t+1
−t−n+µ′t+n+1
).
(8a)
(8b)
定理 2 をこの特殊解に適用すると, 歪平面分割についての次の積公式が得られる.
系 3 (K.). r と c と n を非負整数とする. µ = (µ1 , . . . , µr ) ⊆ (cr ) を分割, µ′ = (µ′1 , . . . , µ′c ) ⊆ (rc )
を µ と共役な分割とする. 歪平面分割 π の重み w(π) を (6) および
βi,j,k =
1 − [y]i−j−1
−n−j+k+µ′
n+j−k+1
1 − [y]i−j
−n−j+k+1+µ′
yi−j
(9)
n+j−k
により定める. このとき
'
π
w(π) =
(
(i,j)∈(cr )/µ
i
1 − [y]i−1−µ
−n−j+1+µ′
n+j
i
1 − [y]i−1−µ
−j+1+µ′
(10)
j
が成り立つ. ただし左辺の和は型 (cr )/µ で成分が高々n の歪平面分割 π すべてにわたってとる.
積公式 (10) は積型母関数 (2) の一般化 (“boxed” 版) である. 実際, 系 3 において n → ∞ の極
限をとると βi,j,k → yi−j となり, (10) の左辺と右辺はそれぞれ (2) の左辺と右辺に帰着する. また
µ = ∅ かつ yk ≡ q とすると, 通常の平面分割についての MacMahon の三重積公式 [3] が得られる.
参考文献
[1] E. R. Gansner, The Hillman-Grassl correspondence and the enumeration of reverse plane
partitions, J. Combin. Theory Ser. A 30 (1981), 71–89.
[2] R. Hirota, S. Tsujimoto, and T. Imai, Difference scheme of soliton equations, State of the
art and perspectives of studies on nonlinear integrable systems (Japanese) (Kyoto, 1992),
Sūrikaisekikenkyūsho Kôkyūroku, 822, 1993, pp. 144–152.
[3] P. A. MacMahon, Combinatory analysis, volume 2, Cambridge University Press, Cambridge,
1916.
クラスタリングを用いた野球投手の傾向分析
横浜市立大・国際総合科学部
小泉 和之1
野球というスポーツは大きく投手と打者に分かれている. ここではルールの説明は省略す
るが, 投手と打者では役割が分かれており, それぞれ良い悪いという評価の仕方は異なる.
本研究では, 最終的に投手の評価方法の提案を目的とするが, まずは打者の評価方法から述
べる. 打者は打席に立てば毎回結果を残せるということはほぼなく, 打席に立った回数 (打数)
のうち, 何回安打 (本塁打も含) を打ったかという割合, 打率で評価されることが多い. 古くは
この打率が 3 割を超えれば一流であると言われることが多かった. 野球というスポーツは得
点を競い合い, その得点の大小で勝敗が決まる. 打率とは打者の評価方法として重要ではある
が, より得点と関係の強い指標を作れればそれが直接的に勝敗に影響を与えると考えられる.
そこで注目を集めたものが出塁率である. 打率では四球, 死球, 犠飛数, 犠打数を除き打数と
しているのに対し, 出塁率では,
出塁率 =
安打数 + 四球数 + 死球数
打数 + 四球数 + 死球数 + 犠飛数
(1)
のように犠打を除く打席結果も考慮している. これにより, 打率よりも得点に関係の強い指標
として注目されている.
また, 打者にはタイプが異なる選手が多くおり, 中でも注目を集めることが多いのが本塁打
を多く打つ打者である. 野球の華と言われる本塁打はそれだけで 1 得点が入る. 他の安打は少
なくとも 2 回打たなければ得点には結び付かない. 得点に結び付きやすい順に
本塁打 ≥ 3 塁打 ≥ 2 塁打 ≥ 単打
となる. そうであれば, 本塁打を打てる打者だけを使えばそれだけ得点できるかと思いがち
だが, 本塁打はそれほど多く打てるものではないため, 他の出塁と絡めて打つ方が現実的であ
る. 打者は 1 試合におよそ 4,5 回打席が回ってくるがその中で 1 回でも本塁打を打てればかな
り本塁打を打つ選手と言える. 中村剛也 (西武ライオンズ) はおかわり君と呼ばれているがそ
れは彼が 1 試合で複数回本塁打を打つことが多かったためである. しかし, 彼はその分, 三振
も多く, 打率という観点では .250 前後であることが多い. 最近では山田哲人 (東京ヤクルト),
筒香嘉智 (横浜 DeNA) などのように本塁打も多く打つが, 打率も 3 割を超えるような選手も
いるが, それほど多くはないし, こういう選手は打率で評価が高いので, おかわり君のような
選手の評価をするために,
IsoP = (長打率) − (打率),
長打率 =
塁打数
打数
(2)
という指標が提案されている. ただし, 塁打数は安打の中でも本塁打なら 4, 3 塁打なら 3 とい
うように進んだ塁の個数を表わす. これは安打が長打になる可能性が高い打者ほど高くなる
が, 打率の高い選手, 低い選手が混在してしまうので打者の 1 つの指標というくらいに捉える
べきである.
打者の評価方法としては, 最も価値がありそうなものとして, 長打を打てようが打率が高か
ろうが, チームの勝利に貢献出来る打者であるという指標が重要となる. そこで, 1987 年の広
選手名
ランス
正田耕三
打率
本塁打数
出塁率
長打率
.218
.333
39
0
.325
.363
.536
.405
島東洋カープを例にとる ([1]). 表は両極端な 2 人の成績である. 正田耕三は長打はあまり打
てないがこの年のセ・リーグ首位打者 (シーズンで最も打率の高かった選手) を獲得し, ラン
スはこの年の本塁打王を獲得した. この 2 人はどちらの方がチームの勝利 (得点) に貢献をし
たと考えられるか. 実はこれまで説明した出塁率, 長打率 (IsoP ではなく) が得点に強い関係
性を持っていることが知られており, それらを両方考慮した指標として
OPS = 出塁率 + 長打率
(3)
が近年, 主流となっている. これは例えば走力, 守備力などを考慮していない指標であり, 不
完全ではあるが計算の簡便さなどからメジャーリーグでは重要視されている. このようにあ
る程度しっかりした理屈から評価されていることがわかる.
続いて, 投手の評価について説明する. 近年の投手は昔の投手と異なり, 1 人で 1 試合を投
げ抜くということは少なく, 最初に投げる投手 (先発投手) と後半に投げる投手 (リリーフ投
手) と役割を決めて配置し, 1 試合を複数の投手で戦うという分業制を採用しているチームが
多い. 高校野球でもこの分業制をしいているチームは多い.
投手の評価としては打者同様に古くから使われているものは防御率と呼ばれるもので, 仮
に最後 (9 回) まで 1 人で投げた場合, 理論上何点とられるかを評価した値であり, この数字が
小さいほど投手としては点を取られづらいのだから良い投手と言える. しかし, この値は一般
的にリリーフ投手の方が小さい値になりやすい傾向にあり, 先発とリリーフでは異なる評価
指標があった方がよいと考えられる.
先発では現在, QS (Quality Start) 率という指標がよく使われている. これは先発投手が 6
回以上投げて自責点 3 点以内に抑えた試合数を登板試合数で割った値である. この確率が高
いほど失点が少ないので価値があるという考え方である. 必ずしも 0 点に抑えなくとも評価
できるという利点がある.
一方で, 先発, リリーフ共によく評価に用いられるのが, 1 回投げたときに平均してどのく
らいランナーを出すかという,
WHIP =
与四球数 + 被安打数
投球回数
(4)
という指標がある. これは, 1.32 くらいが平均であり, それよりも小さいほど良いとされる指
標である. しかし, こちらも防御率同様に一般にリリーフの方が低い数値になることが多いの
で, 共通の指標で評価するのは不適切かもしれない. 本研究ではこれらに相当する指標の提案
が目標ではあるが, その前提としてそもそも先発とリリーフでは投手として特徴が異なるの
ではないかという点に注目し, ある程度の回数を投げている先発・リリーフのデータからクラ
スタリングを行い, 投手タイプの分類を行う. クラスタリング手法の詳細, 分析結果の詳細に
ついては当日報告する.
参考文献
[1] おさーる DATA BOX. http://www.geocities.jp/osahru_bbd/yeardata/80/c1987.html.
1
[email protected]
Some adjacency properties of graphs and tournaments
)∗
(
1.
. |A ∪ B| = n
A, B ⊂ V (G)
,A
,B
z∈
/ A∪B
,G
n-e.c. (n-existentially closed)
.
,
T
,
A, B ⊂ V (T ) a ∈ A, b ∈ B
(z, a), (b, z) ∈ E(T )
z∈
/ A∪B
, T n-e.c.
.
,
.
,
Sk
:
A ⊂ V (T ) (|A| = k) a ∈ A
(z, a) ∈ E(T )
z∈
/A
. Sk
. n-e.c.
Schütte
. (cf. [1])
1963 , Erdős-Rényi[7]
n
, Erdős-Rényi
(
)
n-e.c.
.
, n-e.c.
,
.
Erdős, Rényi
,
.
Paley
Paley
.
G
1 (cf. [3], [8]) Pq
n2
, Pq
2 2n−2
q
Tq
q
3
,4
.
, Tq
Paley
n-e.c.
Sk
. [2]
, Tq
Paley
. q>
.
([8]).
, Hadmard
.
, Paley
n-e.c.
,
[4]
.
2.
,
“Paley-like”
.
,
, g Fq
.
,
q ≡ 5 (mod 8)
.
n-e.c.
,
(4)
Tq
,
V (Tq(4) ) = Fq , E(Tq(4) ) = {(x, y) | x − y = g i , i ≡ 0, 1 (mod 4)}
(4)
Tq
, −1 = g 4j+2
q
.
,
.
Fq
,h
q ≡ 7 (mod 12)
.
, well-defined
(6)
,
Tq
V (Tq(6) ) = Fq , E(Tq(6) ) = {(x, y) | x − y = hi , i ≡ 0, 1, 2
(4)
Tq
q
2
, −1 = g 6j+3
(mod 6)}
, well-defined
.
.
2010 Mathematics Subject Classification: Primary 05C20 Secondary 05C80, 11T23, 11T24
∗
464-8601
e-mail: [email protected]
Sk
(6)
Tq
√
(4)
n-e.c.
.
, q > 2(k − 1)2 {(2 +
(6)
n-e.c.
.
, q > 2(k − 1)2 (22k − 1)2
2 q > n2 23n−1
(4)
, Tq
Sk
, Tq
.
3 q > n2 26n−4
Sk
.
, Tq
2)k − 1}2
,
(
)
. |A ∪ B ∪ C| = n
A, B, C ⊂ V (D)
a ∈ A, b ∈ B, c ∈ C
,
(z, a), (b, z) ∈ E(D)
(z, c), (c, z) ∈
/ E(D)
z ∈
/ A∪B∪C
,D
strongly n-e.c.
. [2] , q ≡ 5 (mod 8)
, Paley
(4)
Dq
.
, D
V (Dq(4) ) = Fq , E(Dq(4) ) = {(x, y) | x − y = g i , i ≡ 0 (mod 4)}
[2]
,
(4)
q
, Dq
.
, Dq
, n-e.c.
.
,
) n-e.c.
.
strongly n-e.c.
.
Covering array
, [6]
(
)
n-e.c. Sk
, intersecting family covering-free family
([5]).
,
.
n-e.c.
,
,
(4)
4 q > 9n2 24n−2
(
(
(
)
, Covering array
)
.
[1] N. Alon, J. H. Spencer. The Probabilistic Method. Fourth edition. Wiley-Interscience
Series in Discrete Mathematics and Optimization, John Wiley and Sons, Inc, 2016.
[2] W. Ananchuen, L. Caccetta. Cubic and quadruple Paley graphs with the n-e.c. property.
Discrete Math. 306 (2006), 2954-2961.
[3] A. Blass, G. Exoo, F. Harary. Paley graphs satisfy all first-order adjacency axioms. J.
Graph Theory. 5 (1981), 435-439.
[4] A. Bonato. The search for n-e.c. graphs. Contrib. Discrete Math. 4 (2009), 40-53.
[5] M. Borowiecki, J. Grytczuk, M. Hauszczak, Z. Tuza. Schütte’s tournament problem and
intersecting families of sets. Combin. Probab. Comput. 12 (2003), 359-364.
[6] C. J. Colbourn, G. Kri. Binary covering arrays and existentially closed graphs. In: Coding
and cryptology, Lecture Notes in Comput. Sci., 5557, 22-23, Springer, Berlin, 2009.
[7] P. Erdős, A. Rényi. Asymmetric graphs. Acta Math. Acad. Sci. Hungar. 14 (1963), 295315.
[8] R. L. Graham, J. H. Spencer. A constructive solution to a tournament problem. Canad.
Math. Bull. 14 (1971), 45-48.
[email protected]
Abstract
s-distance set
t-triangle set (t ≤ 3)
1
t-triangle set
Pusan National University
s-distance set
Rd
d
X
s-distance set
s-
X
s
A2 (X) = {d(x, y) | x, y ∈ X, x ̸= y}
|A2 (X)| = s
X
d
s-distance set
k
d(x, y)
k-
x, y
X ⊂ Rd
g2∗ (d) := max{|X| | X is a 2-distance set in Rd }
Theorem 1 (Blokhuis).
g2∗ (d) ≤
Theorem 2.
!
"
d+2
2
g2∗ (d)
d≤8
a∼ d
d
1 2 3
4
5
6
7
8
3 5a 6 10b 16c 27d 29 45
a: C5 , b:T5 = L(K5 ), c: Clebsch graph, d: Schläfli graph
g2∗ (d)
2
t-triangle set
{Y ⊂ X : |Y | = 3}/≡
Definition 3. X
3
X
t-triangle set
Remark 4.
•
•
•
a, b, c
A3 (X)
abc
n = |X|, s = |A2 (X)|, t = |A3 (X)|
Ai (X)
(|Ai (X)|)1≤i≤n
isometric sequence
|A3 (X)| = t
√
A2 (X) = {1, 3, 2}
Example 5. X √
1
α = 1, β = 3, γ = 2
s=3
A3 (X) = {ααβ, αβγ, βββ}
t = 3.
t
X
gt (d) := max{|X| | X is a t-triangle set in Rd }.
3
t-triangle set
s, t
s
≤t≤
3
Theorem 6. n ≥ 5
Remark 7.
2-distance set
t≤3
!
"
s+2
.
3
s≤t
.
n≥5
n = 4, s = 3, t = 1
Corollary 8. 1-triangle set
g1 (d)
#
4
g1 (d) =
d + 1,
Theorem 9. 2-triangle set
g2 (d)
g2 (d) =
#
5
2d
if d = 2, 3
if d ≥ 4.
if d = 2,
if d ≥ 3.
(d = 2)
Lemma 10. X ⊂ Rd (n ≥ 5)
2-triangle sets
cross polytopes (d ≥ 3)
s=t=3
|X| ≤ 2d + 2
X = Rd ∪ (−Rd )
regular simplex
Rd
Theorem 1, Theorem 6, Lemma 10
Theorem 11. 3-triangle set
g3 (d) (d ≤ 5)
g3 (2) = 6, g3 (3) = 8, g3 (4) = 10, g3 (5) = 16.
isometric sequence
Problem 12.
isometric sequence (|Ai (X)|)1≤i≤n
Rd
3
Ehrhart
∗
2
P ⊂ Rd
Zd
d
lP
|(lP ) ∩ Z |
l
|(lP ) ∩ Zd | = cd ld + cd−1 ld−1 + · · · + c0
lP = {lx | x ∈ P }
Ehrhart
P
P
l
d
1
P
d
F1 , . . . , Fn
P
Fk
1
1
P
c0 , cd−1 , cd
Fk
Fk
Vol
Vol(Fk )
Vol(P )
P
P
1.
1. c0 = 1.
2. cd−1 =
1
2
!n
k=1
Vol(Fk ).
3. cd = Vol(P ).
c0 , cd−1 , cd
P
3
Ehrhart
1
d
c1
d
P ⊂ R3
3
F1 , . . . , Fn
primitive
2. P
1≤k≤n
P
1
E = Fk1 ∩ Fk2
c1
Fk
vk ∈ Z
m(E)
P
P
3
s(E)
1. m(E) = |((Rvk1 + Rvk2 ) ∩ Z3 )/(Zvk1 + Zvk2 )|
2. (Rvk1 + Rvk2 ) ∩ Z3
e1 , e2
s(E) = s(p, q)
s(p, q) =
$$
q ## $$ ##
"
i
pi
q
i=1
3. q = m(E)
s(E)
q
p
well-defined
4. P
1
vk1 = e1 , vk2 = pe1 + qe2 (0 ≤ p < q)
s(p, q)
F
Pi , Qi , Fki
∗ [email protected]
F
,
((x)) =
%
x − [x] −
0
1
2
(x ∈
/ Z),
(x ∈ Z)
2
C(F )
P
1
Dedekind
s(p, q)
F
primitive
v ∈ Z3
1: F
Pi , Qi , Fki
1≤i≤r
εi = det(v, vki+1 , vki ),
−−−−−−→
−−−−→
⟨Pi−1 Qi−1 , vki+1 ⟩
⟨Pi Pi+1 , vki−1 ⟩
ai =
, bi =
−−−−−−→
−−−−→
εi ⟨Pi−1 Qi−1 , v⟩
εi−1 ⟨Pi Pi+1 , vki ⟩
vk0 = vkr , vkr+1 = vk1
&
& bi+1
&
&
& ε−1
& i+1
"
&
C(F ) = −
ai && 0
& .
2≤i<j≤r
& .
& .
&
& 0
0×0
5 ([2]). P ⊂ R3
ε−1
i+1
0
bi+2
ε−1
i+2
..
.
···
ε−1
i+2
..
.
..
.
···
..
.
..
.
0
..
.
bj−2
ε−1
j−2
0
ε−1
j−2
bj−1
0
1
3
E1 , . . . , Em
c1 =
&
&
&
&
&
&
&
& εi εi+1 · · · εj−1 Vol(Pj−1 Pj )
&
m(Pj−1 Pj )
&
&
&
&
&
P
F1 , . . . , F n
P
$
m #
n
"
1
1 "
s(Ej ) +
Vol(Ej ) +
C(Fk )
4
12
j=1
k=1
1
Pommersheim [1]
P
P
d
Ehrhart
P
P
Ehrhart
cd−2
3
5
[1] J. E. Pommersheim, Toric varieties, lattice points and Dedekind sums, Math. Ann. 295 (1993), 1–24.
[2] Y. Suyama, Ehrhart polynomials of 3-dimensional simple integral convex polytopes, arXiv:1605.04694.
d-defective k-fold coloring
(
[email protected]
)
kdefective
1-defective 2-fold coloring
d-defective coloring
k-fold coloring
1
i
d
(i, d)-coloring
i
d
χd (G)
2
G
(i, d)-coloring
i = χd (G)
d-defective coloring
k
j
j:k-coloring
G
j:kcoloring
k
χk
k
j = χk
k-fold coloring
d-defective k-fold coloring
3
k
d
d-defective k-fold coloring
G
χdk
1-defective 2-fold
G∗v
v∈
/ V (G)
1. G
2.
χ(G ∗ v)
V (G)
E ′ (G)
V ′ (G)
v
v
G ∗ v = (V ′ (G), E ′ (G))
v
|V (G)|
G
χ12 (G)
1-defective 2-fold
G∗v
χ12 (G) ≤ χ12 (G ∗ v) ≤ χ12 (G) + 2
1 χ12 (G ∗ v) = χ12 (G)
G
v
G
χ12 (G ∗ v)
v
χ12 (G ∗ v) = χ12 (G) + 1
u
G\u
1 χ12 (G ∗ v) = χ12 (G) ⇒ ∃u, χ12 (G \ u) < χ12 (G)
??
2 ∀u ∈ V (G), χ12 (G \ u) = χ12 (G) ⇒ χ12 (G ∗ v) = χ12 (G) + 2(v ∈
/ V (G))
[1] Sc K. Appel, W. Haken, Every planar map is four colorable. Part I: Discharging,
Illinois Journal of Mathematics Volume 21, Issue 3, p429-490, 1977.
[2] UT L. Cowen, W. Goddard, C. E. Jesurum, Defective coloring revisit, Journal of
Graph Theory vol.24 No.3, p205-219, 1997.
[3] E. R. Scheinerman, D. H. Ullman, Fractional Graph Theory, John Wiley and Sons,
1997.
有向グラフ上のパーコレーション
田中 守
(東北大学)∗
パーコレーションとは、無限グラフの”ランダムな”部分グラフの性質を調べる分野
である。特に、ボンドパーコレーションは辺の存在する割合のパラメータ 0 ≤ p ≤ 1 を
用いて、連結部分グラフの大きさの期待値を評価することや、無限連結部分グラフが
存在する p の極小値などを求めることが重要である。パーコレーションには、他にもサ
イトパーコレーション、有向パーコレーション、連続パーコレーション等々いろいろ
あるが ([1] 参照)、ここでは各頂点が周りの頂点をランダムにいくつか選んで繋がるよ
うなパーコレーションを考えたい。
自然数 d ≥ 2 を固定し、G = (V, E) を d-正則、頂点推移的な、連結無限単純有向グラ
フで (x, y) ∈ E ⇔ (y, x) ∈ E を満たすものとする。例えば、正方格子、三角格子、六
方格子に最近接頂点への有向辺を与えたもののような、いくつかの平面または双曲タ
イリングの頂点と有向辺から成る有向グラフや、有限生成無限群の有向ケーリーグラ
フなどがある。
G = (V, E) に対し、x ∈ V の周りの頂点集合を Lx := {y ∈ V | (x, y) ∈ E} =
!
{x(1), x(2), . . . , x(d)} とする。このとき、P(Lx ) を Lx の部分集合族とし、Ω := x∈V P(Lx )
とする。各元 ω ∈ Ω は Eω := {(x, y) ∈ E | x ∈ V, y ∈ ω} により、G の部分有向グラフ
Gω = (V, Eω ) と 1 : 1 に対応する。
p = (p0 , p1 , . . . , pd ) を
p0 , p1 , . . . , pd ≥ 0 かつ p0 + p1 + · · · + pd = 1
を満たすものとし、これを用いて Ω 上に確率測度を定義する：各 x ∈ V における射影
πx : Ω ∋ ω &→ ω(x) ∈ P(Lx ) に対して、F を ∪x∈V {πx−1 (S) | S ⊂ Lx } で生成される Ω 上
の σ-加法族とする。各 x ∈ V と各 {x(i1 ), . . . , x(ik )} ⊂ Lx に対して、µx を
µx (ω(x) = {x(i1 ), . . . , x(ik )}) =
pk
k!(d − k)!
=
pk
d!
d Ck
!
と定義し、(Ω, F) 上の確率測度を Pp := x∈V µx と定義する。µx (ω(x) = {x(i1 ), . . . , x(ik )})
は、Gω が「頂点 x から出ている有向辺の終点の集合が {x(i1 ), . . . , x(ik )} である」よう
な部分有向グラフである確率を表している。特に、p = (p0 , p1 , . . . , pd ) の各 pk は頂点か
ら出る有向辺の数が k 本である確率、つまり Pp (|ω(x)| = k) を表している。
Gω の辺集合 Eω に対し Eω := {(y, x) ∈ E | (x, y) ∈ Eω } とする。Gω で x, y ∈ V が
弱連結 x ! y (強連結 x ↔ y) であるとは、x = y, または z1 , . . . , zk ∈ V が存在して
(x, z1 ), (z1 , z2 ), . . . , (zk , y) ∈ Eω ∪ Eω (resp. (x, z1 ), (z1 , z2 ), . . . , (zk , y) ∈ Eω ∩ Eω ) を満
たすこととする。G の原点 o ∈ V を固定する。
（以下の議論は原点の取り方に依らない。）
頂点集合 Cω := {x ∈ V | x ! o in Gω } を弱クラスター、C̃ω := {x ∈ V | x ↔ o in Gω }
を強クラスターという。
2010 Mathematics Subject Classification: 82B43, 05C20
キーワード：パーコレーション, 有向グラフ
∗
〒 980-8577 宮城県仙台市青葉区片平 2-1-1 東北大学原子分子材料科学高等研究機構（AIMR）
e-mail: [email protected]
web: http://www.wpi-aimr.tohoku.ac.jp/mathematics_unit/mamoru_tanaka/
ここでは、「p = (p0 , p1 , . . . , pd ) がどのような条件を満たせば、弱 ( 強 ) クラスター
が無限集合になる確率が 0 または正になるか？」という問題を考えたい。ここで、p =
(p0 , p1 , . . . , pd ), p′ = (p′0 , p′1 , . . . , p′d ) に対して、pi + · · · + pd ≤ p′i + · · · p′d (0 ≤ i ≤ d) の
とき、Pp (|Cω | = ∞) ≤ Pp′ (|Cω | = ∞), Pp (|C̃ω | = ∞) ≤ Pp′ (|C̃ω | = ∞) であることは
容易に分かる。特に、G が d-正則有向木の場合には、マルチタイプ分岐過程を用いれ
ば以下が分かる。
命題 1 ([2]). G を d-正則有向木 (d ≥ 3) とする。pc,2 (Td ) :=
に対して、
(1) p0 + p1 ≥ 1 − pc,2 (Td ) ならば、Pp (|Cω | = ∞) = 0
(2) p2 + · · · + pd > pc,2 (Td ) ならば、Pp (|Cω | = ∞) > 0
1
2d2
(d2 −d−1)+
√
1
(d2 −d−1)2 −(d−1)2
≈
命題 2 ([2]). G を d-正則有向木 (d ≥ 3) とする。k(k − 1) ≤ d < (k + 1)k のとき、
(1) p0 + · · · + pk = 1 ならば、Pp (|C̃ω | = ∞) = 0
(2) pk+1 + · · · + pd = 1 ならば、Pp (|C̃ω | = ∞) > 0
より一般に、最初に与えた有向グラフ G = (V, E) に対して次が成り立つ:
定理 1 ([2]).
(1) p0 + p1 が十分 1 に近いならば Pp (|Cω | = ∞) = 0
(2) k(k −1) < d である k に対し、p0 +· · ·+pk が十分 1 に近いならば Pp (|C̃ω | = ∞) = 0
G が平面グラフであるとは、G が端点と逆辺以外で各辺が交叉しないように平面 R2
に埋め込め、さらに埋め込んだ各辺は線分であり、その長さは一定の値以上かつ一定
の値以下であるようにできることである。このとき、この埋め込みを用いて G の双対
グラフ G∗ = (V ∗ , E ∗ ) が定義できる。G∗ の原点 o∗ ∈ V ∗ を固定する。σG∗ (n) を G∗ 中の
1
o∗ から出発する長さ n の self-avoiding path の本数とし、λ(G∗ ) := limn→∞ σG∗ (n) n と
する。d∗ を G∗ の各頂点から出る辺の本数の最大値とすると、1 ≤ λ(G∗ ) ≤ d∗ − 1 で
ある。
定理 2 ([2]). G を最初に与えた無限有向グラフで、平面グラフとする。このとき
" d #2
(1) k = d または λ(G∗ ) < d−k
を満たす k に対して、pk + · · · + pd が十分 1 に近い
ならば Pp (|Cω | = ∞) > 0.
d
(2) k = d または λ(G∗ ) < d−k
を満たす k に対して、pk + · · · + pd が十分 1 に近いなら
ば Pp (|C̃ω | = ∞) > 0.
これを用いると、正方格子 (d = 4), 三角格子 (d = 6), 六角格子 (d = 3) に対して、
p2 + · · · + pd が十分 1 に近いならば Pp (|Cω | = ∞) > 0 であり、p3 + · · · + pd が十分
1 に近いならば Pp (|C̃ω | = ∞) > 0 であることが分かる。特に、d = 6, k = 3 のとき
d = k(k − 1) であるが、p3 = 1 とすると、三角格子 (d = 6) は Pp (|C̃ω | = ∞) > 0 を
満たす。よって、d-正則有向木のように d = k(k − 1) だからと言って、pk = 1 のとき
Pp (|C̃ω | = ∞) = 0 であるとは限らない。
参考文献
[1] G. Grimmett, Percolation, Springer-Verlag, Berlin, 1999.
[2] M. Tanaka, A percolation on directed graphs, arXiv:1604.00371.
(
, [email protected])
1
2
R. Woo, A. Neumaier [2]
−2
(
)
−2
R. Woo
A. Neumaier [2]
−2
2.1.
(i) (ii)
µ : V → {f, s}
H = (V, E)
:
(i)
f
s
(ii)
H = (H, µ)
;
f
s
slim
f
V s (H)
H
fat
f
V (H)
H
fat
fat-
H
[2]:
2.2. A
:
H
A=
As
slim
B(H) = As − CC
C
T
H
!
As
C
CT
O
slim
"
fat
slim
Γn
2.3 (Hoffman [1]). H
f
fat
f
K(f )
slim n-clique K(f )
H
:
λmin (Γn ) ≥ λmin (H)
(1)
lim λmin (Γn ) = λmin (H)
(2)
n→∞
Γn
ϵ>0
slim
∆
λmin (∆) ≤ λmin (H) + ϵ.
n
2.3
Woo
Neumaier
[2]
3
fat
Γ
fat
fat
fat
H
slim
4
normalized cut
[1] A. J. Hoffman, On graphs whose least eigenvalue exceeds −1 −
√
2, Linear Algebra Appl. 16
(1977), 153–165.
[2] R. Woo and A. Neumaier, On graphs whose smallest eigenvalue is at least −1 −
Algebra Appl. 226-228 (1995), 577–591.
√
2, Linear
平坦 δ 列とその Ehrhart 多項式
土谷 昭善
(大阪大学大学院 情報科学研究科)∗
本講演は大阪大学の日比孝之氏との共同研究に基づく。([1])
1. 準備
P ⊂ RN を d 次元整凸多面体とし, ∂P をその境界とする。任意の正整数 n につい
て i(P, n) と i∗ (P, n) を
i(P, n) = |nP ∩ ZN |, i∗ (P, n) = |n(P \ ∂P) ∩ ZN |
で定義する。この時，次のようなことが知られている。
• i(P, n) は，n に関する d 次多項式であり，定数項は常に 1 である。
• （Ehrhart 相互法則）i∗ (P, n) = (−1)d i(P, −n) が成立する。
この多項式 i(P, n) を P の Ehrhart 多項式と呼ぶ。
整数列 δ0 , δ1 , δ2 , . . . を次の公式で定義する。
(1 − λ)
d+1
∞
!
n
i(P, n)λ =
n=0
∞
!
δi λi .
i=0
i(P, n) が n に関する d 次多項式であることなどから，任意の i > d について δi = 0
であることがわかる。この整数列
δ(P) = (δ0 , δ1 , . . . , δd )
を P の δ 列と呼ぶ。
δ 列について，次のようなことが知られている。
• δ0 = 1, δ1 = i(P, 1) − (d + 1), δd = i∗ (P, 1) である。
• δi は非負である ([3])。
• s = max{i | δi ̸= 0} とすると，t = 1, . . . , d − s に対し，i∗ (P, t) = 0 であり，
i∗ (P, d − s + 1) = δs である。
δ 列の分類について，次元に注目すると，d = 2 の時には [2] により完全分類され
ているが，d ≥ 3 の場合ではほとんど未解決である。本講演では δ 列の形に注目
してこの問題を考える。
∗
e-mail: [email protected]
2. 平坦 δ 列の特徴付けとその Ehrhart 多項式
P ⊂ RN を d 次元整凸多面体とし, δ(P) をその δ 列とする。P の δ 列が平坦であ
るとは，ある正整数 a に対して δ(P) が (1, 0, . . . , 0, a, . . . , a, 0, . . . , 0) のような形
をする時に言う。
本講演の主結果は平坦 δ 列の完全な特徴づけである。
定理 1 正整数 a に対し有限非負整数列
(δ0 , . . . , δd ) = (1, 0, . . . , 0, a, . . . , a, 0, . . . , 0)
" #$ %
" #$ %
k
ℓ
が或る d 次元整凸多面体の δ 列となる必要十分条件は，k ≤ ℓ を満たすことである。
次に平坦 δ 列の Ehrhart 多項式について議論する。k と ℓ を正整数とし，P と Q
を次を満たす d 次元整凸多面体とする:
• t = 1, . . . , k に対し i(P, t) = i(Q, t) である。
• t = 1, . . . , ℓ に対し i∗ (P, t) = i∗ (Q, t) である。
Ehrhart 相互法則などにより，k + ℓ ≥ d であれば，このとき P と Q の Ehrhart 多
項式は一致する。しかし，k + ℓ ≤ d − 1 であれば，このとき必ずしも P と Q の
Ehrhart 多項式が一致するとは限らない。
定理 1 により次の定理が得られる。
定理 2 任意の非負整数 k, ℓ に対して，k + ℓ ≤ d − 1 であれば，d 次元整凸多面体
P, Q で次を満たすものが存在する。
• t = 1, . . . , k に対し i(P, t) = i(Q, t) である。
• t = 1, . . . , ℓ に対し i∗ (P, t) = i∗ (Q, t) である。
• i(P, k + 1) ̸= i(Q, k + 1)，i∗ (P, ℓ + 1) = i∗ (Q, ℓ + 1) である。
参考文献
[1] T. Hibi and A. Tsuchiya, Flat δ-vectors and their Ehrhart polynomials,
arXiv:1604.02505.
[2] P. R. Scott, On convex lattice polygons, Bull. Austral. Math. Soc. 15 (1976),
395–399.
[3] R. P. Stanley, Decompositions of rational convex polytopes, Annals of Discrete
Math. 6 (1980), 333–342.
(
[email protected]
g
)
Stanley
.
.
g
.
1 Stanley
i
g
P
P
fi (P)
f
f (P) = (f−1 (P), f0 (P), · · · , fd−1 (P))
Stanley
P
f
.
h(P) = (h0 (P), h1 (P), · · · , hd (P))
h
.
P
. d
[1]
h
.
1 (g−
h = (h0 , h1 , · · · , hd ) ∈ Zd+1
[1],[2])
f
3
h
P
d
.
(1) hj = hd−j (0 ! j ! d)
(2) 1 = h0 ! h1 ! · · · ! h⌊d/2⌋
(3) hi+1 − hi ! (hi − hi−1 )<i> (1 ! i ! ⌊d/2 − 1⌋)
P
3
(1)
Poincare
(2)
Hard Lefschetz
(3)
Macaulay
XP
.
2
g
J. Huh
Scheme
M. Haiman
.
C2
n
Hilbert
2 (Read’s Conjecture [3])
χG (q) = an q n − an−1 q n−1 + · · · + (−1)n a0
G
a0 , a 1 , · · · , a n
log-concave
.
0<i<n
ai−1 ai+1 ! ai 2
3 (Macdonald Positivity Conjecture [4])
Macdonald
Pµ (x; q, t) ∈ Q(q, t)[x]
)Kλµ (q, t) ∈ Q(q, t)
Shur
(Kostka-Macdonald
.
Kλµ (q, t) ∈ N[q, t]
[1] R. P. Stanley. The number of faces of a simplicial convex polytope. Adv. in Math., 35(3):236-238,
1980.
[2] L. J. Billera. and C. W. Lee. A proof of sufficiency of McMullen’s conditions for f-vectors of simplicial
convex polytopes, J. Comb. Th., Ser.A 31(1981), 237-255.
[3] J. Huh. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, J.
Amer. Math. Soc.25 (2012), no. 3, 907-927.
[4] M. Haiman. Hilbert schemes, polygraphs and the Macdonald positivity conjecture, J. Amer. Math.
Soc. 14 (2001), no. 4, 941-1006.
ABD
Coxeter
2
)∗
(
1.
R
A
B
S = R[x1 , . . . , xℓ ]
D
Coxeter
R
ℓ
Aℓ−1 = {Hij = {xi − xj = 0} | 1 ≤ i < j ≤ ℓ} ,
!
"
Bℓ = {Hi = {xi = 0} | i = 1, . . . , ℓ} ∪ Hij±1 = {xi ± xj = 0} | 1 ≤ i < j ≤ ℓ ,
!
"
Dℓ = Hij±1 = {xi ± xj = 0} | 1 ≤ i < j ≤ ℓ .
A
V =R
ℓ
Aℓ−1
1
Bℓ
Dℓ
H
H∈A
#
A
H = ker(pH )
pH ∈ V ∗
Q(A ) = H∈A pH
#
A
Q(Aℓ−1 ) = 1≤i<j≤ℓ (xi − xj ) ℓ
#
#
2
Q(Bℓ−1 ) = x1 · · · xℓ 1≤i<j≤ℓ (xi − x2j ) Q(Dℓ−1 ) = 1≤i<j≤ℓ (x2i − x2j )
N = {0, 1, 2, . . . }
multi-index
α = (α1 , . . . , αℓ ) ∈
αℓ
α1
ℓ
α
N
|α| = α1 + · · · + αℓ ∂ = ∂1 · · · ∂ℓ
α! = α1 ! · · · αℓ !
$
%
(m)
m
D (S) = |α|=m S∂ α
θ = |α|=m fα ∂ α ∈
D(m) (S) 0
multi-index α
fα 0 i
θ i
deg(θ) = i
SD(m) (A )
D(m) (A ) = {θ ∈ D(m) (S) | θ(Q(A )S) ⊆ Q(A )S}
m
D
(m)
(A )
AD(m) (A )
S-
D(m) (A )
{θ1 , . . . , θsm }
S-
exp D(m) (A ) = {deg(θ1 ), . . . , deg(θsm )} .
m=1
D(1) (A )
D(1) (A )
A[5]
D
D(S/Q(A )S)
(m)
(A )
Hölm [2]
D(S/Q(A )S) ≃
$
S-
D(m) (A )
.
Q(A )D(S)
m≥0
m D(m) (A ) SD(S/Q(A )S)
[5] Theorem 6.60
m≥2
D(m) (A )
D(S/Q(A )S)
D(1) (A )
[3]
D(2) (A )
2010 Mathematics Subject Classification: 32S22, 15A15
∗
270-1382
2-1200
e-mail: [email protected]
2.
A = Aℓ−1
A
D
B D
[4]
m
{λ = (λ1 , . . . , λm ) ∈ Z | ℓ − m ≥ λ1 ≥ λ2 ≥ · · · ≥ λm ≥ 0}
B
Λ =
λ∈Λ
λ +m−j
sA
λ
sA
λ
α ∈ Nn
αi
λ∈Λ
det(ti j
)1≤i,j≤m
=
∈ S[t1 , . . . , tm ]
m−j
det(ti )1≤i,j≤m
t1 , . . . , tm
deg sA
λ = |λ|
xα = (x1 , . . . , x1 , x2 , . . . , x2 , . . . , xℓ , . . . , xℓ )
θλA =
&
sA
λ (xα )
|α|=m
1 α
∂
α!
(2.1)
xi
(2.2)
deg θλA = |λ|
k = 1, . . . , ℓ
hA
k = (xk −x1 ) · · · (xk −xk−1 )(xk −
A
A 1 m
A
(m)
xk+1 ) · · · (xk − xℓ )
ηk = hk m! ∂k
θλ , hA
(A )
[4]
k ∈ D
Cauchy-Sylvester’s theorem on compound determinants Saito-Holm
([1])
1 ([4]).
D(2) (Aℓ−1 )
λ ∈ Λ}
WA
S-
ℓ
!
" !
"
CA = ηiA | i = 1, . . . ℓ ∪ θλA | λ ∈ Λ
exp D(2) (Aℓ−1 ) = {ℓ − 1, . . . , ℓ − 1} ∪ {|λ| |
{ℓ − 1, . . . , ℓ − 1} ℓ − 1 ℓ
!
A
D(m) (Aℓ−1 ) W A
θ ∈ D(m) (Aℓ−1 )
D(1) (Aℓ−1 )
W A-
2.
A
W 3. W A -
θλA
V
W A-
WA
D(m) (S)
w∈W
w·θ = θ
m=1
Sm=2
Coxeter
W A-
!
"
!
S-
!
ηkA | k = 1, . . . ℓ
D(2) (Aℓ−1 )
[1] P. Hölm, Differential Operators on Arrangements of Hyperplanes. PhD. Thesis, Stockholm University, (2002).
[2] P. Hölm, Differential Operators on Hyperplane Arrangements. Comm. Algebra 32 (2004),
no.6, 2177-2201.
[3] T. Józefiak and B. E. Sagan, Basic derivations for subarrangements of Coxeter arrangements. J. Algebraic Combin. 2 (1993), no.3, 291-320.
[4] N. Nakashima, Modules of differential operators of order 2 on Coxeter arrangements.
Algebr. Represent. Theory, 17 (2014), no.4, pp. 1163-1180.
[5] P. Orlik and H. Terao, Arrangements of Hyperplanes. Grundlehren dermatematischen
Wissenschaften 300, Springer-Verlag, 1992.
[email protected]
K, H
n
,
Da f : K → H, Da f (x) := f (ax)f (x)−1
f :K→H
f :K→H
a ∈ K \ {e}
planar
.
, D := {(x, f (x)) ∈ K × H | x ∈ K}
planar
.
P := K × H, L := {Hx | x ∈ K} ∪ {Dy | y ∈ K × H}
.
.
, Dembowski
,K ×H
([1]).
n
translation plane,
translation plane
([2]). André, Dembowski
Result. ([1],[2]) Π
.
(1) Π
translation plane
(2) Π
type(b) plane
n2
dual
type(b) plane
dual
Piper
G
dual
3
.
n
,G
.
,
.
.
planar
.
K ×H
(P, L, ∈)
.
n2
Piper
. André
K, H
type(b) plane
, planar
translation
([3]).
dual
.
Question.
K, H
f :K→H
,
planar
K, H
planar
.
.
, [4]
.
Conjecture. f : K → H
planar
K, H
.
.
[1] P. Dembowski and F.C. Piper : Quasiregular collinearion groups of finite projective planes. Math. Z.
99(1967), 53-75.
[2] J. André : Ünber nicht-Desarguessche Ebenen mit transitiver Translationsgruppe. Math. Z. 62(1954),
156-186.
[3] R.S. Coulter and R.W. Matthews : Planar functions and planes of Lenz-Barlotti class II, Des. Codes
Cryptogr. 10(1997), 167-184.
[4] G.L. Mullen and D. Panario : Handbook of finite fields. CRC Press (2013).
POSET からの SCHEMOID の構成について
沼田泰英 (信州大学)
大雑把にいうと, small category C は, (多重辺やセルフループを許
す) 有向グラフに辺の合成 ◦ という演算が定義されているものである.
慣習に倣い, 頂点の集合を Obj(C), 辺の集合を Mor(C) と書くことに
する. f ∈ Mor(C) に対し, f の始点を s(f ), f の終点を t(f ) と書く.
また s(f ) = x, t(f ) = y であるときには, f : x → y と書くこともあ
る. s(g) = t(f ) を満たす f, g ∈ Mor(C) に対し, 合成 g ◦ f は定義され,
s(g ◦f ) = s(f ) と t(g ◦f ) = g となる. s(g) ̸= t(f ) のとき, 合成 g ◦f は定
義されない. 合成には結合則が要請され, path を辺に書き換える操作だ
と合成のことを思うこともできる. また, 各頂点 x に対し, idx ∈ Mor(C)
が存在し, t(idx ) = s(idx ) = x, idx ◦g = g (∀g : z → x), f ◦ idx = f
(∀f : x → y) という 3 条件を満たしている. ここでは Mor(C) が有限で
あるものだけ考える.
Small category C と体 K が与えられたとき, Mor(C) を基底とする K
ベクトル空間 KC を考える. f, g ∈ Mor(C) に対し
g·f =
⎧
⎪
⎨g ◦ f
⎪
⎩0
(s(g) = t(f ))
(s(g) ̸= t(f ))
と定義することで, KC に積を定めることができる. Mor(C) が有限であ
%
るので, x∈Obj(C) idx ∈ KC を単位元とする K 代数になる.
Small category C と写像 l : Mor(C) → Λ の組 (C, l) について考える.
%
σ ∈ Λ に対し, σ̄ = f : l(f )=σ f ∈ KC とおき, { σ̄ σ ∈ Λ } を基底と
する K ベクトル空間を K(C, l) とする. K(C, l) が KC の部分 K 代数と
なっているとき, (C, l) は (unital) schemoid と呼ばれる. Schemoid は,
association scheme の圏論的一般化として, Kuribayashi–Matsuo [1] に
よって導入された. 本講演の目標は, schemoid の例の構成である.
∆ を simplicial complex とする. つまり, ∆ ⊂ 2{ 1,...,n } であり, X ∈ ∆
かつ Y ⊂ X ならば Y ∈ ∆ となるとする. Obj(C) = ∆ とし, Mor(C) =
{ νX,Y : X → Y X ⊂ Y ∈ ∆ } とおく. νY,Z ◦νX,Y = νX,Z と合成を定義
すると, C は small category となる. このように構成した C は ∆ の face
poset と思うこともできる. このとき, Λ = ∆ とし, l : Mor(C) → Λ を
l(νX,Y ) = Y \ X で定義すると, (C, l) は schemoid となる. また K(C, l)
は次で定義される可換環と同型である: 不定元 x1 , . . . , xn に関する多
項式環 S = K[x1 , . . . , xn ] について考える. G0 = { x2i i = 1, . . . , n },
G1 = { xv1 · · · xvl { v1 , . . . , vl } ̸∈ ∆ } とする. I を G1 で生成されるイ
デアルとすると, S/I は G0 ∪ G1 で生成されるイデアルを I とおくと,
Stanley–Reisner 環と呼ばれるものであり, I˜ を G0 と G1 で生成される
イデアルとすると, K(C, l) は S/I˜ と同型である.
Boolean lattice 2[n] が ‘良い性質’ を持っているため, simplicial complex ∆ に対しこの様な Schemoid の構成が可能であると考えることがで
きる. l(νX,Y ) = Y \ X と定義されており, 集合差 \ という操作があるこ
とが l の定義に大きく関わっている. この視点から simplicial complex
での構成を一般化し, [2] では, 集合差の様な操作を持つ Poset につい
て同様な schemoid の構成が可能であることを示した. また集合差では
なく disjoint union ⨿ を使うことで, l の定義は次の様に, 書き換える
こともできる: l(νX,X⨿D ) = D. この視点からも一般化をし, [2] では,
disjoint union の様な操作を持つ Poset について同様な schemoid の構成
が可能であることを示した.
References
[1] K. Kuribayashi and K. Matsuo. Association schemoids and their categories.
Appl. Categ. Structures 23 (2015), no. 2, 107―136
[2] Y. Numata, Construction of schemoids from posets, preprint. arXiv:1603.
00601
)∗
(
F2
2
Sg
Nk
(
)
G
G
F (G)
G
G
F2
)
G
G
F2
F
2
G
F2
(
F
F2
G
2
3
G
4
F2
G
φ1
φ1
φ2
Lawrencenko et al. [4]
S20
[7, 8, 9]
φ2
G
K19
Korzhik and Voss
Korzhik [5, 6]
n
Kn
Korzhik and Voss [9]
K8s+5
n = 8s + 5
G
Lawrencenko and Negami [2, 3]
Nakamoto et al. [10]
11-
G
1
F2
Suzuki [11, 13]
G
F2
1
Suzuki [12]
11. (Suzuki [12])
11
Sg
g≥1
1Nk
S1
Nk
2. (Ishiguro et al. [1], Suzuki [12]) 1 ≤ k ≤ 4
1-
3. (Nagasawa, N. and Suzuki, submitted)
Nk
1∗
e-mail: [email protected]
k≥1
1:
1-
[1] K. Ishiguro, S. Negami, Y. Suzuki, K. Yamamoto, No optimal 1-planar graph triangulates the non-orientable closed surface of genus 4, Congr. numer. 202 (2010), 25–31.
[2] S. Lawrencenko, S. Negami, Constructing the graphs that triangulate both the torus
and the Klein bottle, J. Combin. Theory Ser. B 77 (1999), 211–218.
[3] S. Lawrencenko, S. Negami, Irreducible triangulations of the Klein bottle, J. Combin.
Theory Ser. B 70 (1997), 265–291.
[4] S. Lawrencenko, S. Negami, A.T. White, Three nonisomorphic triangulations of an
orientable surface with the same complete graph, Discrete Math. 135 (1994), 367–369.
[5] V.P. Korzhik, Exponentially many nonisomorphic orientable triangular embeddings of
K12s , Discrete Math. 308 (2008), 1046–1071.
[6] V.P. Korzhik, Exponentially many nonisomorphic orientable triangular embeddings of
K12s+3 , Discrete Math. 309 (2009), 852–866.
[7] V.P. Korzhik, H.-J. Voss, Exponential families of nonisomorphic nonorientable genus
embeddings of complete graphs, J. Combin. Theory Ser. B 91 (2004), 253–287.
[8] V.P. Korzhik, H.-J. Voss, Exponential families of nonisomorphic nontriangular orientable
genus embeddings of complete graphs, J. Combin. Theory Ser. B 86 (2002), 186–211.
[9] V.P. Korzhik, H.-J. Voss, On the number of nonisomorphic orientable regular embeddings of complete graphs, J. Combin. Theory Ser. B 81 (2001), 58–76.
[10] A. Nakamoto, S. Negami, K. Ota, J. Širáň, Planar triangulations which quadrangulate
other surfaces, European J. Combin. 25 (2004), 817–833.
[11] Y. Suzuki, Graphs that triangulate a given surface and quadrangulate another surface,
J. Combin. Theory, Ser. B. 97 (2007), 237–244.
[12] Y. Suzuki, Optimal 1-planar graphs which triangulate other surfaces, Discrete Math.
310 (2010), 6–11.
[13] Y. Suzuki, Triangulations on closed surfaces which quadrangulate other surfaces. II,
Discrete Math. 303 (2005), 234–242.
On certain transformations on link diagram
and their algebraic structures
橋爪 惠 ∗
奈良女子大学大学院人間文化研究科博士後期課程 3 年，2016 年 8 月
1
Transformations on link diagram
ひもが結ばれてできる図形である結び目は，数学的には三次元球面内のひとつの 1 次元球面が作る図形と
して定式化される．また互いに交わらない有限個の結び目の作る図形を絡み目と言う．二つの結び目や絡み
目が，自分自身とぶつかること無く，連続的に移りあうとき同じものと考える．
今回紹介する話題は，平面上に描き表された結び目や絡み目に関するものである．正確にいうと，まず結
び目・絡み目を 2 次元球面上に射影したもの（ただしこの射影は
一般の位置にあるとする）の２重点でのひもの上下がわかる
ように 2 次元球面上に描いたものをリンクダイアグラムと言う．
そしてリンクダイアグラムで２重点に対応するところを交差という．
領域
交差
また 2 次元球面からもとの結び目・絡み目の射影を除いたものの
一つずつの成分を領域という．
清水理佳氏（群馬高専）らによって region crossing change と呼ばれるリンクダイアグラムの局所的な変形
が新しく定義された．さらに最近，この region crossing change の変種として region freeze crossing change
というリンクダイアグラムの局所変形が井上歩氏と清水遼氏（愛知教育大）によって提案された．今回の講
演はこの二つの変形の関係に関するものである．
定義 1.1. D をリンクダイアグラムとし，R を D の一つの領域とする．R の境界に含まれる全ての交差で交
差交換を行って得られるリンクダイアグラムを Drcc (R) とかくことにする．D から Drcc (R) を与える操作
を R での region crossing change とよぶ．一般に領域の集合 H に対して，H の各成分での region crossing
change の合成を H での region crossing change と呼ぶ．
清水理佳氏 [Shimizu] はこの region crossing change に関して次の定理を示した．
定理 1.2. 任意の結び目のダイアグラム D に対して次が成り立つ．
D の交差の集合 J に対して，ある領域の集合 H で，H での region crossing change で交差交換される交
差の集合は J に一致するようなものが存在する．
井上ー清水 [Inoue-Shimizu] は region crossing change の変種として次の概念を導入した．
定義 1.3. D をリンクダイアグラムとし，R を D の一つの領域とする．R の境界に含まれない全ての交差
で交差交換を行って得られるダイアグラムを Drf cc (R) とかくことにする．D から Drf cc (R) を与える操作を
R での region freeze crossing change とよぶ．一般に領域の集合 H に対して，H の各成分での region freeze
crossing change の合成を H での region freeze crossing change と呼ぶ．
本稿では領域の集合 H が与えられたとき H に属する領域には色を付けることによって，H を幾何的に表
すことにする．また，その色付けを coloring と呼ぶ．
∗ mam
[email protected]
←
r.f.c.c.
→
r.c.c.
定理 1.2 から結び目のリンクダイアグラムであれば好きな交差を region crossing change で交差交換でき
ることが分かる．一方，井上歩ー清水遼 [Inoue-Shimizu] は region freeze crossing change に関して，交差
交換できない交差が存在すること，さらに与えられたリンクダイアグラムの与えられた交差が region freeze
crossing change で交差交換できるための必要十分条件を示した．
定理 1.4. D をリンクダイアグラム，c を D の交差とする．region freeze crossing change で c のみを交差交
換する領域の集合が存在しない必要十分条件は次の通り．B(W resp.) を D の checkerboard coloring で塗ら
れている領域の集合（塗られていない領域の集合 resp.）とする．J を region crossing change で c のみを交
差交換する領域の集合とする．B, W の各々の元の数がいずれも偶数かつ，J の元の数が奇数．
2
Algebraic structures
この節では，C をリンクダイアグラム D の交差すべてからなる集合，R をリンクダイアグラム D の領
域すべてからなる集合とする．一般に集合 X に対して、そのべき集合を 2X と書くことにする．今、2C ,
2R に対称差によって和を導入する．つまり，A, B ∈ 2R (resp. 2C ) に対して、A + B を次で定義する；
A + B = (A \ B) ∪ (B \ A)．さらに、2C , 2R にスカラー Z2 倍を次で定義する；A ∈ 2R or 2C に対して、
0 · A = ∅ , 1 · A = A．以上により 2R と 2C がそれぞれ Z2 線形空間であることが容易にわかる．次に，この
線型空間 2R から 2C への写像 ϕ, ψ を次で定義する
H(∈ 2R ), ϕ(H) = {c ∈ C|c は H での region crossing change で交差交換される }
H(∈ 2R ), ψ(H) = {c ∈ C|c は H での region freeze crossing change で交差交換される }
これが Z2 線型写像なっていることも容易にわかる．
[Inoue-Shimizu] で，region freeze crossing change と region crossing change の関係として，次が示されて
いる．
命題 2.1. D をリンクダイアグラム，H を領域の集合，C を D の交差すべてからなる集合とする．H の元
の数が偶数のとき Imψ(H) = Imϕ(H). H の元の数が偶数のとき Imψ(H) = Imϕ(H) + C.
今回の講演ではこの二つの写像を用いて結び目のリンクダイアグラムに対する定理 1.4 の絡み目のリンク
ダイアグラムへの拡張について紹介する．
参考文献
[Inoue-Shimizu] Ayumu Inoue, Ryo Shimizu, A subspecies of region crossing change, region freeze crossing
change preprint (arXiv:1606.06809)
[Shimizu] Ayaka Shimizu, Region crossing change is an unknotting operation, Journal of the Mathematical
Society of Japan, 66 (2014), 693–708.
木ではないメディアングラフが導く距離空間につ
いて
早水 桃子
(総合研究大学院大学統計科学専攻 D3)∗
概
要
重みつき木 T は頂点集合 V (T ) と最短経路距離 dT によって距離空間 (V (T ), dT )
を導く．このように何らかの重みつき木で実現される距離空間を MST-like
と呼ぶことにする．なぜなら，距離空間 (X, !d) を実現する重みつき木
T が存
"
X
在するならば，T は重みつき完全グラフ (X, 2 ; d) における（唯一の）最小
全域木と同型だからである．本講演では MST-like な距離空間の特徴づけを
得るために，敢えて木では実現され得ない距離空間について考察してみたい．
1. Preliminaries
Definition 1.1. 有限集合 X 上の距離空間 (X, d) が MST-like である とは，X = V (T )
かつ d(x, x′ ) = dT (x, x′ ) (∀x, x′ ∈ X) を満たす木 T が存在することをいう．
! "
Remark 1.2. 木 T は重みつき完全グラフ (X, X2 ; d) における最小全域木と同型であり，
同型を除き (X, d) に対してユニークに定まる．
Definition 1.3. 有限集合 X 上の距離 d が tree metric である とは，X ⊆ V (T ) かつ
d(x, x′ ) = dT (x, x′ ) (∀x, x′ ∈ X) を満たす木 T が存在することをいう．
Remark 1.4. Tree metric という用語は誤解を招きやすく，系統樹 (phylogenetic tree) で
実現可能な距離と呼ぶほうが正確である．実際，T は X 上の系統樹と呼ばれている．
Theorem 1.5 (Buneman [1]). 有限集合 X 上の距離 d が tree metric であるための必
要十分条件は四点条件を満たすことである．即ち，任意の（相異なるとは限らない）
p, q, r, s ∈ X に対して d(p, q) + d(r, s) ≤ max{d(p, r) + d(q, s), d(p, s) + d(q, r)} が成立
することである．
Definition 1.6. 有限集合上の距離空間 (X, d) が 四点目条件を満たす とは，任意の（相
異なるとは限らない）3 点 x, y, z ∈ X に対して
1
dM (x, p∗ ) + dM (y, p∗ ) + dM (z, p∗ ) = {dM (x, y) + dM (y, z) + dM (z, x)}
2
2010 Mathematics Subject Classification: 05C12 (Distance in graphs)
キーワード：minimum spanning tree, tree metric, median graph
∗
〒 190-8562 東京都立川市緑町 10-3 統計数理研究所 福水健次研究室
e-mail: [email protected]
web: http://hayamizu.tumblr.com/
となる 4 番目の点 p∗ ∈ X が存在することをいう．
Theorem 1.7 ([2]). 有限集合上の距離空間 (X, d) が MST-like であるための必要十分
条件は，四点条件と四点目条件がともに満たされることである．
Remark 1.8. グラフ G が導く距離空間 (V (G), dG ) が四点目条件を満たすとき，G は
メディアングラフ と呼ばれる．Theorem 1.7 より，木はメディアングラフの例である．
Theorem 1.9 ([3]). 有限集合上の距離空間 (X, d) において，d の値がペアごとに全て
異なると仮定する．このとき，(X, d) が四点目条件を満たすことは (X, d) が MST-like
であるための必要十分条件となる．
2. Results
Theorem 2.1. メディアングラフが導く距離空間（四点目条件を満たす距離空間）が
MST-like である（四点条件を満たす）ための必要十分条件は，部分距離行列が次の形
になるような相異なる 4 点を含むことである:
⎛
⎞
0 a b c
⎜ a 0 c b ⎟
a+b+c
⎜
⎟
.
⎜
⎟ with max{a, b, c} =
2
⎝ b c 0 a ⎠
c b a 0
参考文献
[1] P. Buneman, A note on the metric properties of trees, J. Combinatorial Theory Ser. B
17 (1974), 48–50.
[2] M. Hayamizu, H. Endo and K. Fukumizu, A characterization of minimum spanning treelike metric spaces, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), doi:10.1109/TCBB.2016.2550431, in press.
[3] M. Hayamizu and K. Fukumizu, On the minimum spanning tree-like metric spaces,
arXiv:1505.06145 [math.CO] (2015), submitted.
対称差で閉じた集合族について
東谷 章弘（京都産業大学・理学部）
Email: [email protected]
本講演では、対称差で閉じた集合族の分類について議論する。動機はプレプリント [1] に由来する
が、本講演では集合族のみについて議論する。
• 正の整数 n に対し、[n] = {1, 2, . . . , n} とする。
• 集合 A, B に対し、A と B の対称差 A △ B とは、
A △ B = (A ∪ B) \ (A ∩ B)
を表す。
• ある集合族 A が対称差で閉じているとは、任意の A, B ∈ A に対して A △ B ∈ A となるとき
に言う。（特に、∅ ∈ A となる。）
• ある集合族が [n] の部分集合族になっているとき、[n] を台集合という。
• 台集合 [n] の部分集合族 A と B が同型であるとは、ある置換 σ : [n] −→ [n] が存在して B = σ(A)
となるときにいう。
対称差で閉じた集合族について、次の命題が成り立つ。
命題 1 正の整数 M, k は M > 2k を満たすとする。A を台集合 [M ] の集合族で対称差で閉じたもの
!
とし、max{|A| : A ∈ A} ≤ 2k を満たすとし、さらに、 A∈A A = [M ] を満たすとする。
このとき、
M ≤ 3k +
が成り立つ。
正の整数 k に対し、f (k) = 3k +
$
∞ #
"
k
ℓ=1
2ℓ
$
∞ #
"
k
ℓ=1
2ℓ
(1)
とおく。
例 2 A = {1, 2, 3, 4}, B = {1, 2, 5, 6}, C = {1, 3, 5, 7} とおき、台集合 [7] の集合族 A を A, B, C で生
成された集合族とする。つまり、
A = {∅, A, B, C, A △ B, A △ C, B △ C, A △ B △ C}
とおく。このとき、任意の X ∈ A に対し、|X| ≤ 4 となる。
一方で、f (2) = 7 となる。つまり、この例の A は命題１の (1) の等式を実現する例である。
本講演の主結果は次の定理である。
定理 3 非負整数 r に対し k = 2r とおき、M = f (k) とおく。A を台集合 [M ] の集合族で対称差で
!
閉じたものとし、max{|A| : A ∈ A} ≤ 2k を満たすとし、さらに、 A∈A A = [M ] を満たすとする。
このとき、A は次の集合で生成される集合族である：
A1 = {1, . . . , 2k},
A2 = {1, . . . , k} ∪ {2k + 1, . . . , 3k},
A3 = {1, . . . , k/2} ∪ {k + 1, . . . , 3k/2} ∪ {2k + 1, . . . , 5k/2} ∪ {3k + 1, . . . , 7k/2},
···
Ar+2 = {1, 3, 5, . . . , 4k − 1}
k が 2 ベキでない場合の定理 3 の類似として、k = 3 の場合を議論する。次の例は、東大の柏原賢
二氏との共同研究に基づく。
例 4 (k = 3 の場合) M = 10(= f (3)) とおき、A を台集合 [M ] の集合族で対称差で閉じたものとし、
!
max{|A| : A ∈ A} ≤ 6 を満たすとし、さらに、 A∈A A = [M ] を満たすとする。このとき A は
• ３つの集合で生成されたもの１つ
• ４つの集合で生成されたもの２つ
• ５つの集合で生成されたもの１つ
のいずれかと同型になる。
参考文献
[1] A. Higashitani, Lattice
arXiv:1605.00273v1.
simplices
of
maximal
dimension
with
a
given
degree,
Hom
)∗
(
G
n-
x, y ∈ V (G)
G
G
V (G)
n
c(v) ̸= c(w)
G
Lovász [2]
N (G)
n
G
G
v ∈ V (G)
A ⊂ V (G)
A
N (v)
A ⊂ N (v)
V (G)
N (G)
n-
χ(G)
N (G)
G
Lovász
c
(chromatic number)
N (G)
N (G)
{1, · · · , n}
n-
G
v
v ∈ V (G)
n+2
Kneser
Hom
[1]
T
G
Hom(T, G)
T = K2
Hom
Hom(K2 , G)
G
Hom(T, G)
G
T
G
χ(G) ≥ conn(Hom(T, G)) + χ(T ) + 1
conn(X)
X
n-
n
Kn (n ≥ 2)
Hom
[3]
Cn (n ≥ 3)
[4]
[3]
[4]
Hom(T, G) "→ Hom(T, H)
χ(G) ≥ 3
n
n
G⊂H
Hom(T, H)
Hom(T, G)
Hom(T, H)
[1] E. Babson, D. N. Kozlov, Complexes of graph homomorphisms, Israel J. Math. 152
285-316 (2006).
[2] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Ser. A 25
(3) 319-324 (1978).
[3] T. Matsushita, Box complexes and Kronecker double coverings of graphs,
arXiv:1404.1549
[4] T. Matsushita, Homotopy types of Hom complexes of graphs, arXiv:1509.03855
(
,
∗
:28-6304)
,
606-8224
e-mail: [email protected]
, Hom
(
)
E-mail:[email protected]
V
(C
R : V ⊗V → V ⊗V
)
(R ⊗ 1V )(1V ⊗ R)(R ⊗ 1V ) = (1V ⊗ R)(R ⊗ 1V )(1V ⊗ R)
(
)
X
Drinfel’d 1990 [1]
σ :X ×X →X ×X
X
(σ × 1X )(1X × σ)(σ × 1X ) = (1X × σ)(σ × 1X )(1X × σ)
(
)
[2, 4, 5]
X
σ :X ×X →X ×X
!
"
σ(a, b) = max(a, b), min(a, b)
[4]
(L, ∨, ∧)
σ :L×L→L×L
σ(a, b) = (a ∨ b, a ∧ b)
[3]
[1] Drinfel’d, V. G., On some unsolved problems in quantum group
theory, Quantum groups (Leningrad, 1990), 1–8, Lecture Notes in
Math., 1510, Springer, Berlin, 1992.
[2] Gateva-Ivanova, T., A combinatorial approach to the set-theoretic
solutions of the Yang-Baxter equation, J. Math. Phys. 45 (2004)
3828-3858.
[3] Matsumoto, D. K.: Distributive lattice and idempotent Yang-Baxter
map. preprint.
[4] Nagai, A., Takahashi, D. and Tokihiro, T.: Soliton cellular automaton, Toda molecule equation and sorting algorithm. Phys. Lett. A
255 (1999). 265-271.
[5]
., Ralph Willox., Jonathan J.C. Nimmo.: Yang-Baxter maps
from the discrete KP hierarchy.
1650
(2009). 162-172.
グラフのトラックレイアウト
宮内
日本電信電話株式会社
NTT
美樹
コミュニケーション科学基礎研究所
〒 243-0198 神 奈 川 県 厚 木 市 森 の 里 3-1
E-mail: [email protected]
グ ラ フ 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 の頂点を細分点と呼ぶ．グラフはまたそれ自身の細分
ともみなす．
頂 点 集 合 V(G)の 分 割 {V i : 1≤ i≤ t}が G の 頂 点 t-彩 色 で あ る と は ，任 意 の 辺 vw ∈ E(G)
に 対 し て ， v ∈ V i か つ w ∈ V j な ら ば i≠ j が 成 り 立 つ と き の こ と を 言 う ． G の 頂
点 t-彩 色 {V i : 1≤ i≤ t}の 各 部 分 集 合 V i が < i に よ っ て 順 序 づ け ら れ て い る と き ， 順
序 集 合 (V i , < i ) を ト ラ ッ ク と 呼 び ， {(V i , < i ) : 1 ≤ i ≤ t} を G の t-ト ラ ッ ク 割 り
当 て と 呼 ぶ ．各 部 分 集 合 で の 順 序 が わ か っ て い る と き は ，単 に ト ラ ッ ク 割 り 当 て を
{V i : 1 ≤ i ≤ t}と も 表 記 す る ．
ト ラ ッ ク 割 り 当 て に お け る X-交 差 と は ，異 な る i と j で v < i x か つ y < j w と な
る よ う な 2 辺 vw と xy の こ と を 言 う ． E(G)の 分 割 {E i : 1 ≤ i ≤ k} の こ と を ， G
の 辺 k-彩 色 と 言 う ．辺 vw ∈ E i は 色 i に 彩 色 さ れ て い る と 言 う ．グ ラ フ G の (k, t)ト ラ ッ ク レ イ ア ウ ト と は ， G の t-ト ラ ッ ク 割 り 当 て と ， 同 色 の X-交 差 を 持 た な い G
の 辺 k 彩 色 か ら な る も の を 言 う ．(k, t)-ト ラ ッ ク レ イ ア ウ ト を 持 つ グ ラ フ の こ と を (k,
t)-ト ラ ッ ク グ ラ フ と い う ．
G が (k, t)-ト ラ ッ ク レ イ ア ウ ト を 持 つ と き ， そ の 最 小 の tを tn k (G)と 書 く ． 特 に グ ラ フ
の 辺 が た だ 一 色 か ら な る (1, t)-ト ラ ッ ク レ イ ア ウ ト を 単 に t-ト ラ ッ ク レ イ ア ウ ト ， tト ラ ッ ク レ イ ア ウ ト を 持 つ グ ラ フ を t-ト ラ ッ ク グ ラ フ と い う ． ま た ， tn １ (G)を tn(G)
と書き，トラックナンバーと呼ぶ．さまざまなグラフファミリーに対するトラックナ
ン バ ー が 研 究 さ れ て い る ． [1,2]参 照 ．
本 論 文 で は ，グ ラ フ の 細 分 の (d+2)-ト ラ ッ ク レ イ ア ウ ト に つ い て 検 討 す る ．Dujmovic
と Wood は ， 任 意 の グ ラ フ G に 対 し 次 の 定 理 を 示 し た ．
定 理 １ ．[Dujmovic & Wood [1]] 任 意 の 整 数 d>0 と 任 意 の グ ラ フ G に 対 し て ，G の
細 分 の (d+2)-ト ラ ッ ク レ イ ア ウ ト で 各 辺 が 8 log d qn(G) +1 個 の 細 分 点 を 持 つ よ う
なレイアウトが存在する．
キ ュ ー 数 の 定 義 は 以 下 の と お り で あ る ．グ ラ フ 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)
を満たすときをいう．このとき， f は e の内部でネストしているという．
グ ラ フ G の キ ュ ー と は ， 辺 集 合 E(G)の 部 分 集 合 E’ ⊆ E(G) で E’ の ど の 辺 も ネ ス
ト し て い な い 部 分 集 合 を 言 う ． グ ラ フ G の k-キ ュ ー レ イ ア ウ ト と は ， G の 頂 点 順 序
σ と 辺 集 合 E(G)の 分 割 {E s : 1 ≤ s ≤ k} か ら な る セ ッ ト で ，各 分 割 集 合 E s が 頂 点 順 序
σ に 対 し て ， キ ュ ー と な っ て い る も の を い う ． G が k-キ ュ ー レ イ ア ウ ト を 持 つ と き ，
そ の 最 小 の k を G の キ ュ ー 数 と い い ， qn(G)と 書 く ．
定 理 １ に 関 し て ， Dujmovic と Wood[1]は ， ト ラ ッ ク レ イ ア ウ ト の 細 分 数 の オ ー ダ
ーが最適であることも示した．よって，細分数の最高次数の係数を減らすことが面
白い問題となる．
2 部 グ ラ フ G の キ ュ ー 数 に 関 し て は Heath と Rosenberg[3]に よ っ て 次 の 定 理 が 示 さ
れた．
定 理 ２ ． [Heath & Rosenberg[3]]
qn(K m, n )=min{ m/2 , n/2 }
定理１に定理２を代入すると以下の系が得られる．
系 ３ ． 任 意 の 整 数 d>0 と 任 意 の ２ 部 グ ラ フ G m, n に 対 し て ， G m, n の 細 分 の (d+2)-ト ラ
ッ ク レ イ ア ウ ト で 各 辺 が 8 log d n - log d 2 +1 個 の 細 分 点 を 持 つ よ う な レ イ ア ウ ト が
存 在 す る ．但 し ，m, n は そ れ ぞ れ V(G m, n )の ２ つ の 部 集 合 の 頂 点 数 で m ≥ n と す る ．
本論文では 2 部グラフに対してさらに細分点の個数を減らすことを検討し次の定理
を示す．
定 理 ４ ． 任 意 の ２ 部 グ ラ フ G m, n に 対 し て G m, n の 細 分 の (d+2)-ト ラ ッ ク レ イ ア ウ ト
個 の 細 分 点 を 持 つ よ う な レ イ ア ウ ト が 存 在 す る ． 但 し ， m, n は
で 各 辺 が 4 log d n
そ れ ぞ れ V(G m, n )の ２ つ の 部 集 合 の 頂 点 数 で m ≥ n と す る ．
文
献
[1] Vida Dujmovic' and David R. Wood. "Stacks, queues and tracks: Layouts of graph
subdivisions," Discrete Mathematics and Theoretical Computer Science, 7:155-202,
2005.
[2] Vida Dujmovic', Attila Pór and David R. Wood. “Track layouts of graphs,” Discrete
Mathematics & Theoretical Computer Science, 6(2):497-522, 2004
[3] L. S. Heath and A. L. Rosenberg, “ Laying out graphs using queues.” SIAM J.
Comput., 21(5):927–958, 1992.
Isabella Novik
.
normal
pseudomanifold
,
.
.
∆
: (i) F
∆
F
, F ∩ G ̸= ∅
F ∩G F
G
.
.
∆
∆
,∆
∆
.
(a), (b), (c)
(d − 1)
normal pseudomanifold
:
, (ii) F, G
,
∆
(a) ∆
(b) ∆
(c) ∆
∆
∆
pure (
,∆
(d − 2)
(d − 2)
),
d
F
,
,
link
lk∆ (F ) = {G ∈ ∆ : conv(F ∪ G) ∈ ∆, F ∩ G = ∅}
.
Normal pseudomanifold
(
[Ha]
, β1 (∆)
,
). fi (∆)
∆
i
∆
.
.
(Novik–Swartz [NS], M [Mu]). ∆
. d≥4
,
.
(d − 1)
normal pseudomanifold
"
$
d+1 #
f1 (∆) ≥ df0 (∆) +
β1 (∆) − 1 .
2
,
!
[Ba, Ka, Fo, Ta]
Kalai
,
.
,
∆
π1 (∆)
.
∆
, m(∆)
Gil Kalai
.
π(∆)
,
.
565-0871
1-5
.
(Kalai). ∆
,
Hurewicz
(d − 1)
. d≥4
.
(d − 1)
∆
"
$
d+1 #
f1 (∆) ≥ df0 (∆) +
m(∆) − 1 .
2
.
!
m(∆) ≥ β1 (∆)
,
,
,
,
[Mu, MN1]
,
.
d≥4
(d − 1)
(M–Novik [MN2]). ∆
,
.
normal pseudomanifold
.
!
"
$
d+1 #
f1 (∆) ≥ df0 (∆) +
m(∆) − 1 .
2
, pseudomanifold
.
,
(M–Novik [MN2]). ∆ pure
∆
v
lk∆ (v)
(d − 1)
! "
$
d #
f1 (∆) ≥ (d − 1)f0 (∆) +
m(∆) − 1 .
2
.
. d≥3
References
[Ba] D.W. Barnette, A proof of the lower bound conjecture for convex polytopes, Pacific J. Math.
46 (1973), 349–354.
[Fo] A. Fogelsanger, The generic rigidity of minimal cycles, Ph.D. Thesis, Cornell University, 1988.
[Ha] M. Hachimori,
,
http://infoshako.sk.tsukuba.ac.jp/∼hachi/math/csc2/index.html
[Ka] G. Kalai, Rigidity and the lower bound theorem. I, Invent. Math. 88 (1987), 125–151.
[Mu] S. Murai, Tight combinatorial manifolds and graded Betti numbers, Collect. Math. 66 (2015),
367–386.
[MN1] S. Murai and I. Novik, Face numbers of manifolds with boundary, Int. Math. Res. Not., to
appear.
[MN2] S. Murai and I. Novik, Face numbers and fundamental group, arXiv:1606.02550.
[NS] I. Novik and E. Swartz, Socles of Buchsbaum modules, complexes and posets, Adv. Math.
222 (2009), 2059–2084.
[Ta] T.-S. Tay, Lower-bound theorems for pseudomanifolds, Discrete Comput. Geom. 13 (1995),
203–216.
Riemann
[email protected]
“
”
1
1(
•
•
•
•
cf. [1])
P
Area(P ) P
I (P ) P
B (P ) P
1
Area(P ) = I (P ) + B (P ) − 1.
2
“
”
2
2(
) g
P
1
Area(P ) = I (P ) + B (P ) − 1 + g.
2
3(
) n
kP
EP (k)
P
P
k
k
n
1 Z2
P
{±ei | 1 ≤ i ≤ 2}
EP (k) = 2k 2 + 2k + 1
Zn
4 Zn
P
{±ei | 1 ≤ i ≤ n}
EP (k) =
#
n " #"
!
n k−i+n
i=0
EP (k)
1 EP (k)
i
n
.
−1/2
:
5
EP (k) = EP (1 − k).
2 EP (k)
1
⇔
EP (k) = EP (1 − k)
1
[1]
[2] R Bacher P De La Harpe and B Venkov Seriesde Croissance et
Polynomes D’Ehrhart Associes aux Reseaux de Racines Ann Inst
Fourier Grenoble49 3(1999)
Robinson-Schensted 対応と
ヴィエノーの幾何学的方法
青山学院大学院 M1 西山研究室
山本義也
1
アブストラクト
自然数の有限列のことを語（word）という．また w = i1 , i2 , . . . , il とし
i1 , i2 , . . . , il が 1 ∼ n の順列のとき、w を置換語という．word を ∅ に対応さ
せることを ∅ ← w と書き、∅ ← w = Pw で表す．この ← の操作は Bumping
algorithm と呼ばれる．w ↔ w(1), w(2), . . . , w(n) = i1 , i2 , . . . , in を words と
し、対称群
W =
!
1
2
3
...
n
i1
i2
i3
...
in
"
を考える．Pw は Bumping によってヤング図形となる．ここでヤング図形の
成長過程を考え、新たについたボックスに番号をつけたものを Qw とする．
Pw と Qw は同じ形のヤング図形である．このように同じ形のヤング図形に対
する標準盤のペアと対称群の元を対応させる方法として Robinson-Schensted
対応（RS 対応）がよく知られている．具体的な例を考えると以下のように
なる．
W =
Pw = 1
3
5
2
6
4
!
1 2
3 4
5
6
5 3
1 2
6
4
Qw = 1
2
4
"
5
6
3
一方、ヴィエノーの幾何学的方法を用いることで、同じような対応を導くこ
とができる．この方法ではまず、対称群の元を縦に見ることで、座標平面に
点を打つ．この点からいくつかうまく点を取り、X、Y 軸から光を当てた影
を考える．この影を線で結んでいくと残った点はその影の内部にすっぽり入
る．これをどんどん繰り返していく．こうすることで影の行き先を縦と横に
ついて考えると数字の並びを確認できる．ここで横方向に見たものが Qw の
一行目、縦軸方向に見たものが Pw の一行目と成っていることがわかる．続
けて次は影と影の交点を新たな点として考え、同じことを繰り返す．これに
よって Pw 、Qw を得ることができる．これがヴィエノーの幾何学的方法であ
る．以下はこの方法で先ほどの W を考えたものである．今回は上記の２つ
の方法を具体的な W で具体化したいと考えている．
図 1: ヴィエノーの幾何学的方法
2
参考文献
1. 大賀雅美 編集、数学セミナー、日本評論社、2016 年 3 月号．
2. B.E.Sagan, The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Secondedition. Graduate Texts
in Mathematics 203, Springer-Verlag, 2001.
Jacobi-Trudi’s fomula
Email: [email protected]
n
Pn
SST ab
(m)
(λ)
!
ek (x) =
Schur
1 (Schur
λ ∈ Pn
n
(m)
dλ
= ♯SST ab
1≤i1 <i2 <...<ik ≤n
(m)
(λ)
xi1 xi2 ...xik
1
hk (x) =
). µ = (µ1 , µ2 , ..., µn ) ∈ Zn
aµ (x) =
λ ∈ Pn ρ = (n − 1, n − 2, ..., 1, 0) ∈ Zn
Sλ =
!
m
!
1≤i1 ≤i2 ≤...ik ≤n
xi1 xi2 ...xik
µ
σ∈Sn
sgn(σ)xσ(µ) = det(xi j )1≤i,j≤n
aλ+ρ (x)
aρ (x)
Schur
Schur
1(
). Λn
xi (i = 1...n)
Λn
ei (i = 1...n)
Λn = C[e1 , e2 , ..., ek ]
hk
{eµ }µ∈Zn≥0
Λn = C[h1 , h2 , ..., hk ]
e1 ...en
{hµ }µ∈Zn≥0
Λn
Pieri rule
2. µ = (µ1 , µ2 , ..., µn ) ∈ Pn
hµ =
"
e µ hµ
{Sλ }λ∈Pn
Kλµ Sλ
|λ|=|µ|
eµ =
"
Kλµ Stλ
|λ|=|µ|
Kλµ = {T ∈ SST ab(n) (λ)|xT = xµ }
(2)
{Sλ }λ∈Pn
Λn
e µ hµ
3 (Jacobi-Trudi’s formula). λ = (λ1 , λ2 , ..., λn )
Sλ = det(hλi −i+j )1≤i,j≤n
(1)
Stλ = det(eλi −i+j )1≤i,j≤n
Sλ
(n)
dλ = det
##
Jacobi-Trudi’s formula
[1]
(n)
x1 = x2 = ... = xn = 1
1.
(2)
Sλ(1) = dλ
n + λi − i + j − 1
λi − i + j
Wely
$$
1≤i,j≤n
RSK
2002
[2] W.Fulton Young tableaux LMSST35 Cambridge 1997
(1)
(
∗
)
,
.
,
.
P
,P
.
,
, Delsarte [1, 2], Terwilliger [3]
,
“
Pi ⊆ P
i
,
.
”
,(
)
, Grassmann
.
,
, Grassmann
.
V = CP
P
.
,
i
. V
, Pi
3
V
.
,
Ei∗ (y) =
!
y
0
if dim y = i,
if dim y ̸= i
,
(y ∈ P ).
(“lowering” operator ),
(“rais-
ing” operator )
L(y) =
"
z
y covers z
(y ∈ P ),
R(y) =
z covers y
C
3
Grassmann
"
z
(y ∈ P ).
P
.
Bose–Mesner
,
. Terwilliger [4]
,
.
Theorem 1 (Terwilliger [4]).
.
Uq1/2 (sl2 )
,q
.
,
“
”
Grassmann
.
,
Terwilliger
.
.
∗
Email: [email protected]
# 2)
Uq (sl
,
[1] P. Delsarte. An algebraic approach to the association schemes of coding theory. PhD thesis, Universite Catholique de Louvain, (1973).
[2] P. Delsarte. Association schemes and t-designs in regular semilattices. J.
Combinatorial Theory Ser. A, 20 (1976) 230–243.
[3] P. Terwilliger. The incidence algebra of a uniform poset. Coding theory and
design theory, Part I, 193–212, Springer, New York, (1990).
[4] P. Terwilliger. Introduction to Leonard pairs. J. Comput. Appl. Math 153
(2003) 463–475.
未解決問題予稿
アフィン超平面配置の境界複体について
岡 亮太
(福岡教育大学教育学部)∗
[n] := {1, 2, . . . , n} とおく．H := {H1 , . . . , Hn , Hg } を次の条件（本仮定は説明をス
ムーズに行う為のものであり，本質的なものではない）を満たす Rd+1 上の線形超平面
配置（従って，各 Hi は原点を含む）とする．(1) H1 , . . . , Hn , Hg は互いに異なる．(2)
!
Hg は xd+1 = 0 で定まる超平面である．(3) Hi = {0}．
H + を xd+1 = 1 で定まるアフィン超平面とし，Hi+ := Hi ∩ Hg+ (i ∈ [n])，A :=
" +g
#
Hi | i ∈ [n] とおくと A は Hg+ ∼
= Rd 上のアフィン超平面配置を与える 1 ．特に，A
は Rd の分割を与える．この分割の内，有界なものを集めて出来る複体（正則な CW
複体となる）を，組 M := (H, g)，或いは，A の境界複体と呼ぶ．図 1 の様に，各 Hi
を一般の位置にとれば，M の境界複体 XM は閉球と同相になっていることが期待さ
れる．実際に，1975 年に T. Zaslavsky 氏によりこの主張が予想として提示され（[4]）
，
2008 年に X. Dong 氏によりアフィン有向マトロイドの理論を用いて 2 この予想が正し
いことが示された（[2]）．
定理 1 (X. Dong [2]). M が uniform，即ち，互いに異なる任意の i1 , . . . , ik ∈ [n] ∪ {g}
に対し，
k
k+1
k
$
$
$
dim
Hij ̸= 0 =⇒ dim
Hij = dim
Hi j − 1
j=1
j=1
j=1
が成立するならば，XM は閉球と同相である．
しかしながら，M が uniform であるという条件は XM が閉球である条件としては，
あまりにも強い条件である．例えば，図 2 や図 3 を与える M は uniform ではない
が 3 ，境界複体は閉球と同相である（この様な例は量産できることが直ぐに分かるであ
ろう）．勿論，閉球とはならない例もある．例えば，図 4 がそうである．
現在，講演者は関西大学の柳川浩二氏とのアフィン有向マトロイドを利用した共同
研究 ([3]) から，下記の様に予想している．
予想 1. 次の条件は同値である．
(1) X := XM は閉球である．
(2) X は Z 上 Cohen–Macaulay である．即ち，任意の x ∈ X と i < dim X に対し，
% i (X; Z) = Hi (X, X \ {x} ; Z) = 0．但し，H
% は被約ホモロジー，dim X は X
H
の CW 複体としての次元を表す．
予想 1 が正しければ，例えば，Z 上のホモロジー多様体でトップ以外の次元のホモ
ロジーが消えているような境界複体は閉球と同相ということになる．また，[3] により，
本研究は JSPS 科研費 15K17514 の助成を受けたものです．
∗
〒 811-4148 福岡県宗像市赤間文教町 1 番 1 号
e-mail:
1
逆に，任意の Rd 上のアフィン超平面配置は，必要ならば境界複体を変えない節減を行うことで，こ
の様な操作により得られるアフィン超平面配置にできる．
2
M からアフィン有向マトロイドが構成でき，境界複体の概念はアフィン有向マトロイドのそれに一
般化できる．詳細は，[1] 参照．
3
図 2 の例では H1 ∩ H2 ⊆ H3 が，図 3 の例では，H1 ∩ H2 ⊆ Hg が成立している．
Hg が一般の位置にあるとき，即ち，互いに異なる任意の i1 , . . . , ik ∈ [n] に対し，
'
& k
k
k
$
$
$
Hi j − 1
dim
Hij ̸= 0 =⇒ dim
Hij ∩ Hg = dim
j=1
j=1
j=1
が成立するとき，予想 1 の条件 (2) が満たされることが分かるので（従って，uniform
な M も予想 1 の条件 (2) を満たす）
，上述の予想 1 が正しければ，系として次の主張
を導く．
予想 2. Hg が一般の位置にあれば，XM は閉球と同相である．
，図 1，2 で
下記の図の場合（全て Hg+ による切断面を表していることに注意せよ）
4
は Hg は一般の位置にあるが，残りの図では Hg は一般の位置ではない ．特に，図 3
から予想 2 の逆は成立しないことが分かる．
未解決問題セッションでは，上述の 2 予想を大きな問題として提起したい．
H3+
H4+
H4+
H1+
H2+
H1+
H3+
図 1: uniform の例
H2+
H4+
H3+
図 2: uniform ではない例
H3+
H1+
H2+
H1+
H2+
図 3: Hg が一般の位置で
はない例
H4+
図 4: 閉球ではない例
参考文献
[1] A. Björner, et al., Oriented matroids, 2nd ed., Cambridge Univ. Press, 2000.
[2] X. Dong, The bounded complex of a uniform affine oriented matroid is a ball, J. Combin.
Theory, Ser. A 115 (2008), 651–661.
[3] R. Okazaki and K. Yanagawa, The Cohen–Macaulayness of the bounded complex of an
affine oriented matroid, preprint, 2015 (arXiv: 1512.0604).
[4] T. Zaslavsky, Facing up to arrangements: face-count formulas for partitioins of space by
hyperplanes, Memoirs of Amer. Math. Soc. 154, Amer. Math. Soc., 1975.
4
H1 ∩ H2 ⊆ Hg が成立している．
SELF-REPRODUCING な多面体
近藤 剛史 (鹿児島大学理学部数理情報科学科)
Licata と Powers は [3] において, 3 次元の 5 つの正多面体 (Platonic Solid) は, 1skeleton から多面体の形が完全に決定できることを示した. つまり, 隣接行列の第二固
有値は重複度が 3 であり, 対応する 3 つの固有ベクトルを正規直交化して 1-skeleton の
ユークリッド空間への埋め込みを考える (これを eigenpolytope という) と, 元の正多
面体と相似になるということである. これは多面体の 1-skeleton の組合せ構造から元
の幾何学的構造を回復できることを意味しており, [3] ではこの性質を self-reproducing
と呼んでいる. 論文 [3] では他にも一般次元での simplex, cross-polytope, cube や 2 次
元の正多角形が self-reproducing であることが示されている.
一方, Godsil は [1] において有限グラフからスタートして, その eigenpolytope の
1-skeleton が自分自身であるようなグラフはどのようなものがあるのかという問いを
立て, 距離正則グラフのクラスの中で完全に決定している.
距離正則グラフはかなり広いクラスにも見えるが, 4 次元の正多面体である 24-cell,
120-cell, 600-cell の 1-skeleton を含まないという意味で不自然な条件とも思える. これ
らの 4 次元の正多面体は [4] によるスペクトルの計算を見るとやはり self-reproducing
であることが分かるし, 3 次元の Archimedean solid の中にも self-reproducing だが
1-skeleton は距離正則グラフでないものが見つかる. したがって, 次の問題は Licata,
Powers も意識していたと思われるが依然として重要であると考えている.
問題 1 (多面体の組合せ構造と幾何). self-reproducing な多面体を全て求めよ.
また, 多面体の辺の上に重みを乗せたものを考え, 1-skeleton を重み付きグラフと捉
えることで, 自然に重み付きの self-reproducing というクラスを定義することができる.
[2] によると Archimedean solid の幾つかは一様な重みでは self-reproducing ではない
が, 重みを適切に選ぶと重み付きの意味では self-reproducing になる. これらは全てあ
る有限 Coxeter 群の軌道の凸包 (orbit polytope) になっており, 自然に次の問題が考え
られる.
問題 2 (Coxeter 群の軌道の組合せ構造と幾何). 有限 Coxeter 群の自然な作用に関す
る orbit polytope は適切な重みによって self-reproducing にできるか?
References
[1] C. D. Godsil, Eigenpolytopes of distance regular graphs. Can. J. Math. Vol. 50 (4), (1998),
739–755.
[2] Ivrissimtzis, Ioannis; Peyerimhoff, Norbert Spectral representations of vertex transitive graphs,
Archimedean solids and finite Coxeter groups. Groups Geom. Dyn. 7 (2013), no. 3, 591–615.
[3] C. Licata and D. L. Powers, A surprising property of some regular polytopes. Scientia 1(1988),
73–80.
[4] Nicolau C. Saldanha, Carlos Tomei, Spectra of Regular Polytopes. Discrete Comput. Geom. 7
(1992), 403–414.
E-mail address: [email protected]
重みなしブロックグラフが導く距離行列の余因子と行列式
早水 桃子
(総合研究大学院大学統計科学専攻 D3)∗
概
要
重みなしブロックグラフ G が導く距離行列 DG が与えられている．これは
tree metric なので DG を実現する木 T はユニークに定まるが，G から T を作
るために必要な頂点数 |V (T )| − |V (G)| は DG に関するどのような量を計算
すれば分かるか？例えば DG の余因子や行列式を計算することは有用か？
連結グラフ G が導く距離行列を DG と書く．Graham と Pollack [1] は n 個の頂点を
持つ任意の木 T に対して detDT = (−1)n−1 (n−1)2n−2 を示した．一般に，k 個のブロック
!
"
G1 , · · · , Gk を持つ頂点数 n の連結グラフ G に対しては detDG = ki=1 detDGi j̸=i cofDGj
"k
および cofDG = i=1 cofDGi である [2]．ここで，cofDG は DG の余因子行列の全成分
の和という意味である．
任意のブロック (biconnected component) が complete である連結グラフをブロック
グラフという．以後，G は頂点数 N のブロックグラフで，ai−1 個の Ki（i = 2, · · · , N ）
を持つとする．また，異なる n 個の頂点からなる V (G) の部分集合をラベル集合と呼
び，ラベル集合の置換が定める距離行列 DG の部分行列を D と書く．二つの部分行列
D と D′ がラベル集合の置換だけで移り合うことを D ∼ D′ と書く．
図 1: ブロックグラフ G の例（[3] より引用）
Problem 1 (H). ブロックグラフ G の（K2 を除く）ブロックの個数 a2 + · · · + an−1 を
含意する，距離行列 D の（同値関係 ∼ に関する）不変量を挙げよ．
Problem 2 (H). 距離行列 D から各ブロックの個数 a1 , · · · , an−1 を求めたい．例えば
cofD と detD を計算することで，解の候補はどれほど絞られるだろうか？
Notes. Problem 1 と少し似た趣きの（しかしもっと一般的な設定の）問題として，文献 [4] の
2.7 How large graph? (J. Matoušek; probably folklore) を挙げておく．
参考文献
[1] R. L. Graham, H. O. Pollak, On the addressing problem for loop switching, Bell System
Technical Journal 50 (1971): 2495-2519.
[2] R. B. Bapat, Graphs and matrices, Chapter 8. New York (NY): Springer, 2010.
[3] Wikipedia: Block graph. https://en.wikipedia.org/wiki/Block_graph
[4] J. Matoušek, Open problems on embeddings of finite metric space, http://kam.mff.
cuni.cz/~matousek/metrop.ps
2010 Mathematics Subject Classification: 05C50 (Graphs and linear algebra), 05C12
キーワード：tree metric, block graph
∗
〒 190-8562 東京都立川市緑町 10-3 統計数理研究所 福水健次研究室
e-mail: [email protected]
web: http://hayamizu.tumblr.com/
𝑲𝟏,𝟑 -free グラフの最大重み安定集合の Minty のアルゴリズム
筑波大学大学院システム情報工学研究科
社会工学専攻 M１ 王 雨生
一つの単純グラフの中の独立集合または安定集合は、グラフ内で互いに隣接していない
頂点の集合である。最大独立集合というのは、グラフの中の最も大きな独立集合である。
重みつきグラフの場合、頂点の重さの和が最も大きい独立集合を最大重み独立集合という。
最大独立集合は、各頂点の重みを１としたときの最大重み独立集合である。
与えられたグラフに対して、最大独立集合を求める問題、および、最大重み独立集合を
求める問題は NP 困難な問題としてよく知られており、一般には効率的に解くアルゴリズ
ムはないと考えられている。一方、グラフのクラスを限定して、そのクラスのグラフにつ
いては効率的に解くことができる、という形の結果は種々議論されている。
完全二部グラフ𝐾1,3 は Claw と呼ぶ。グラフは𝐾1,3 及び𝐾1,3に同形な誘導部分グラフが含
まないなら、Claw-free グラフと呼ぶ。Minty [1] は、Claw-free グラフに対して、最大
独立集合、および、最大重み独立集合を多項式時間アルゴリズムによって求めることがで
きることを示した。
（[1]には誤りが含まれていたが、Nakamura-Tamura [2] によって修
正されている。
）本発表では、このアルゴリズムについて紹介する。
Minty のアルゴリズムでは、Claw-free グラフ G の独立集合 S を逐次的に改善するこ
とで最適な独立集合を見つける。現在持っている独立集合 S に対して、S 中の各頂点を黒
点、他の頂点を白点と呼ぶ。Claw-free であることにより、一つの白点は最大二つの黒点
に隣接する。白点は、二つの黒点に隣接するとき bounded、1 つの黒点に隣接するとき
free、どの黒点にも隣接していないときは super free という。
Alternating path は、白点と黒点が交互に並び、しかも、任意の二つの白点は互いに隣
接していないパスである。
White(Black) alternating path というのは、両端点が白(黒)点の alternating path であ
る。パス P の重さδ(P)はパス上の全ての白点の重さの和引く黒点の重さの和である。
Augmenting path はδ(P)＞0、しかも両端点は bounded ではない(free、super free、
または黒点)もののことである。White augmenting path は両端点が白点の augmenting
path である。
対称差をΔで表すと、SΔP は安定集合であり、しかも w(SΔP)=w(S)+δ(P)である。
Minty のアルゴリズム
1．S←φ;
2．If S には、white augmenting path が存在しない then output S; stop
Else 重み最大な white augmenting path 𝑃∗を探す。
3．S←SΔ𝑃∗; go to 2
参考文献
[1] G. J. Minty: On maximal independent sets of vertices in claw-free graphs, Journal
of Combinatorial Theory, Series B, 28 (1980), 284-304.
[2] D. Nakamura, A. Tamura: A revision of Minty's algorithm for finding a maximum
weight stable set of a claw-free graph, Journal of the Operations Research 44 (2001),
194-204.
筑波大学大学院システム情報工学研究科
社会工学専攻 M１ 王 雨生
メール:[email protected]