デジタルハーフトーン技術への応用を期待して Aronov‐浅野‐菊地‐Nandy‐ 笹原‐宇野が提案した次の問題について考えます. $n \times n$盤面に連続する$n ^2$個の整数を書き込み,各$k \times k$ 正方形領域内の和をなるべく一定にせよ. ただし盤面の左右の端どうし,上下の端どうしは繋がっているものとします.
アブストラクト: 正の辺重みを有する無向グラフの頂点集合上に,距離を「2頂点間の最短路の 重み和」と定義することで,これは距離空間になる.考えたい問題は,これを \ell_1に埋め込む際の歪みをできる限り小さくすることである.今回はそのよ うな結果のいくつかを紹介したい.
凸包がcrosspolytopeになるような,一般の次元の点配置を考 え,その正コサーキット全体のなすのクラッターを禁止マイナー的に特 徴づけします. 点配置に対して,正コサーキットとは,凸包のあるファセット上にある 点集合の補集合といっても同じです.ユークリッド空間内の点配置の正 コサーキットのクラッターは,有向グラフの有向サイクルをなす枝の全 体のクラッターの一般化になっています.このようなクラッターの一般 の場合のpacking propertyの特徴づけは難しいですが,凸包が crosspolytopeになる場合に限ると,禁止マイナー的に特徴づけること ができます.具体的には,奇数点サイクルの最小頂点被覆のクラッター をマイナーとして持たないことと,packing propertyを持つこと が同値になります.
単体的複体の組合せ的性質であるconstructibilityは、shellabilityを弱めた 概念である。一般にconstructibleな擬多様体は、球体か球面に限られるが、三 次元以上においてはその逆は成り立たず、球体や球面ではあるがconstructible ではないような例が、多数構成されている。球体や球面がconstructibleかどう かを判定する、十分に汎用的かつ効果的なアルゴリズムは知られていないが、 内部点が二つ以下の三次元球体については、辺の性質を用いた判定条件を八森 が与えている。今回は、八森の用いた手法を拡張し、内部点の個数が一般の場 合について考察した結果を紹介する。
ヒルベルトイデアルとは有限群の次数が正の不変式で生成されるイデアルのことで ある。この講演では、交代群のヒルベルトイデアルのグレブナ基底について得られ た結果を紹介する。また、普遍グレブナ基底についても議論する。
今回は、マトロイドの一般化の一つである「Coxeterマトロイド」について紹介する。 Coxeterマトロイドは(有限)Coxeter群を用いて定義され、そのCoxeter群が A型(対称群)の場合が通常のマトロイドに相当する。 Coxeter群は多面体や超平面配置と深く関わっているため、Coxeterマトロイドも それらの対象と密接な関係を持つ。今回は、Coxeterマトロイドの定義や 基本的な性質の他に、そのような幾何学的な取り扱いについても触れたい。
n頂点のグラフG, H_1, H_2に対し、GがH_1, H_2を辺素に含む(辺を共有することなく部分グラフと して含む)ことができるとき、H_1, H_2に対するGへのtight packingが存在するという。 Garciaら(2002)は、H_1, H_2がいずれもスターでないn頂点の木のとき、H_1, H_2に対するある単純 平面グラフGへのtight packingが存在すると予想した。今回の講演ではこの周辺に関するいくつかの 結果を紹介する。
与えられた無向グラフGを平面に記述する際, 書き方によって, 辺の交わりの数が変化する. この交わり数の最小値をグラフGのCrossing Numberと呼ぶ. 与えられたグラフに対して, このCrossing Numberを求めるのは難しく, NP-困難であることが知られている. また, 完全グラフや完全二部グラフのように特殊な構造を持っているグラフに対しては, 1954年にZarankiewiczの予想以外は, なにもわかっていない. 2005年にDe Klerkらによって, 完全グラフや完全二部グラフのCrossing Numberと Zarankiewiczの予想との関係を連続最適化の技術や群論を利用して考察している. 本発表では, この結果について述べたいと思う. また, 時間があれば, Schrijverらによって さらに深く考察された結果について述べたいと思っている. [Keyword] Crossing Numbers, semidefinite programming, copositive cone, invariants and centralizer rings of permutation groups [論文] E. de Klerk, J.Maharry, D.V.Pasechnik, R.B.Richter and G.Salazar, Improved bounds for the corssing numbers of K_{m,n} and K_n, preprint(2005) E. de Klerk, D.V.Pasechnik and A.Schrijver, Reduction of symmetric semidefinite programs using the regular *-representation, preprint(2005)