組合せ数学セミナー
発表内容の概要
本研究では，有限体上の低次多項式を計算モデルとしたとき，
その計算能力の限界を解明することを目標とする．
具体的には，o(log n) 次の Z_q 多項式では，
剰余関数 MOD_m を計算することができないことを証明する．
この結果は，MOD_m と Z_q 多項式の相関を評価することにより
得られる．本研究では，MOD_m と Z_q 多項式の相関が指数関数的に
小さくなることを示した．
この相関を評価するために，本研究では Gowers uniformity を用いた．
Gowers uniformity とは，関数の一様性を測るための指標で，
最近数学や理論計算機科学の分野で幅広い研究が行われている．
ここでは，ある指数関数の Z_q 上の Gowers uniformity の上界を
評価することにより，MOD_m と Z_q 多項式の相関を評価することができる．
この発表では，主に相関および Gowers uniformity の評価について議論する．
この評価の中で，ある数列の興味深い性質を発見したので，それも紹介する．
Let $r$, $n$ and $n_1, \ldots, n_r$ be positive integers
with $n = n_1 + \cdots + n_r$. Let $X$ be a connected graph with
$n$ vertices. For $1 \le i \le r$, let $P_i$ be the $i$th color class
of $n_i$ distinct pebbles. A configuration of the set of pebbles
$P = P_1 \cup \cdots \cup P_r$ on $X$ is defined as a bijection from
the set of vertices of $X$ to $P$. A move of pebbles is defined as
exchanging two pebbles with mutually distinct colors on the two
endvertices of a common edge. For a pair of configurations $f$ and $g$,
we write $f \sim g$ if $f$ can be transformed into $g$ by a sequence of
finite moves. The relation $\sim$ is an equivalence relation on the set
of all the configurations of $P$ on $X$.
We study the number $c(X, n_1, \ldots, n_r)$ of the equivalence classes.
A tuple $(X, n_1, \ldots, n_r)$ is called transitive if for any
configuration $f$ and for any vertex $u$, a pebble $f(u)$ can be
moved to any other vertex by a sequence of finite moves.
We determine $c(X, n_1, \ldots, n_r)$ for an arbitrary transitive
tuple $(X, n_1, \ldots, n_r)$.
[この研究は、中上川友樹氏（湘南工科大学）および、藤田慎也氏（群馬工業
専門学校）との共同研究です。]
keywords: pebble motion, motion planning, $15$-puzzle, graph puzzle,
Klein's group
本発表は、「2009年暗号と情報セキュリティシンポジウム」（SCIS2009）における話者らの
同タイトルの発表（木村元、今福健太郎、宮寺隆之、縫田光司、今井秀樹）の紹介である。
古典および量子の物理系を包含する公理的一般化である「一般確率論」（general
probabilistic theory）は、物理学的な動機は勿論、量子暗号や長期的安全な暗号との
関連といった情報セキュリティ的な動機からも近年研究が進められている。一般確率論の
数学的定式化においては、状態空間としてユークリッド空間（無限次元の場合は、
局所凸な位相線型空間）のコンパクト凸集合が採用されることが多く、支持超平面の
存在やKrein-Milmanの定理といったコンパクト凸集合の数学的性質が物理的にも
重要な意味を帯びている。本発表では、一般確率論という枠組みの紹介から始め、
状態空間としてユークリッド空間の超立方体を採用した一般確率論の物理的な性質や
その古典物理系における実現、また超立方体の状態空間からより複雑な凸多面体の
状態空間を自然に導出する方法などについて述べる（この凸多面体が一体何なのか
まだよくわかっていないので、その点についても議論できれば幸いである）。
２つの元a,bがcという元を挟むということを
({a,b},c)と表した場合に、この3項関係を
抽象化するとどのように表せるだろうか。「挟む」の具体例として
は、木の枝と、半順序
を考える。木が与えられたときに、枝aとbを結ぶパス上に枝
cがある場合に({a,b},c)と表現すると、
この3項関係はどのように特徴づけられるだろうか。
また、半順序が与えられたときに、a>c>bとなるときに({a,b},c)
と表すとすると、この3項関係はどのように特徴づけられるだ
ろうか。
実はこれらは、凸幾何の例であり、({a,b},c)は根付きサー
キットと呼ばれるものである。
凸幾何の根付きサーキットの特徴づけはすでに知られている。
本研究では木から誘導される凸幾何と半順序から誘導される凸幾何
のクラスに対して、
それらの禁止マイナー的特徴づけを与える。
この発表は東京大学の中村政隆氏との共同研究がもとになっています。
半順序集合のイデアルの一様ランダム生成について議論する。
この問題に対する多項式時間アルゴリズムの存在性は未解決である。
前半は、マルコフ連鎖モンテカルロ（MCMC）法を用いたランダム生成法の可能性について述べる。
特に、マルコフ連鎖の混交時間（mixing time）の算定法として、カップリング法について説明する。
後半は、この問題の応用として、レベルイデアル問題、一般化メディアン安定結婚問題について
述べる。
この発表はDaniel Stefankovic (University of Rochester)氏、根本俊男（文教大学）氏との
共同研究がもとになっています。
本発表では，ネットワークフローの問題の一つである普遍的最速流問題
を扱う．この問題は通常のネットワークとは異なり，各辺が容量だけでは
なく移動時間も持つネットワーク上で定義されるものであり，問題の目的
は，ネットワーク上の点に与えられた全てのサプライを最速に流すことが
でき，かつ任意の時刻において最大のサプライを流すことのできるフロー
を求めることである．本発表では，この普遍的最速流問題に対して，通常
のネットワークにおける辞書式最大流問題との関係に注目し，Minieka に
よる存在性の証明や，我々のグループによって提案された格子状ネット
ワークに対する多項式時間アルゴリズムなどを紹介する．
トップに戻る