組合せ数学セミナー
発表内容の概要

10/28(金): 河村彰星 (京都大学 大学院人間・環境学研究科)
視覚的に一様な整数行列の構成について

デジタルハーフトーン技術への応用を期待して Aronov‐浅野‐菊地‐Nandy‐
笹原‐宇野が提案した次の問題について考えます．
    $n \times n$盤面に連続する$n ^2$個の整数を書き込み，各$k \times k$
    正方形領域内の和をなるべく一定にせよ．
ただし盤面の左右の端どうし，上下の端どうしは繋がっているものとします．

11/11(金): 岡本吉央 (豊橋技術科学大学 情報工学系)
\ell_1へのグラフの近似埋め込みについて

アブストラクト：
正の辺重みを有する無向グラフの頂点集合上に，距離を「2頂点間の最短路の
重み和」と定義することで，これは距離空間になる．考えたい問題は，これを
\ell_1に埋め込む際の歪みをできる限り小さくすることである．今回はそのよ
うな結果のいくつかを紹介したい．

11/25(金): 柏原賢二 (東京大学 大学院総合文化研究科)
凸包がcrosspolytopeとなる点配置から得られるクラッターに関するpacking propertyの特徴づけ

凸包がcrosspolytopeになるような，一般の次元の点配置を考
え，その正コサーキット全体のなすのクラッターを禁止マイナー的に特
徴づけします．
点配置に対して，正コサーキットとは，凸包のあるファセット上にある
点集合の補集合といっても同じです．ユークリッド空間内の点配置の正
コサーキットのクラッターは，有向グラフの有向サイクルをなす枝の全
体のクラッターの一般化になっています．このようなクラッターの一般
の場合のpacking propertyの特徴づけは難しいですが，凸包が
crosspolytopeになる場合に限ると，禁止マイナー的に特徴づけること
ができます．具体的には，奇数点サイクルの最小頂点被覆のクラッター
をマイナーとして持たないことと，packing propertyを持つこと
が同値になります．

12/2(金): 亀井聡 (帝京科学大学 理工学部)
内部点を持つ三次元球体のconstructibilityについて

単体的複体の組合せ的性質であるconstructibilityは、shellabilityを弱めた
概念である。一般にconstructibleな擬多様体は、球体か球面に限られるが、三
次元以上においてはその逆は成り立たず、球体や球面ではあるがconstructible
ではないような例が、多数構成されている。球体や球面がconstructibleかどう
かを判定する、十分に汎用的かつ効果的なアルゴリズムは知られていないが、
内部点が二つ以下の三次元球体については、辺の性質を用いた判定条件を八森
が与えている。今回は、八森の用いた手法を拡張し、内部点の個数が一般の場
合について考察した結果を紹介する。

12/16(金): 和田崇志 (立教大学 理学研究科数学専攻)
交代群のヒルベルトイデアルのグレブナー基底

ヒルベルトイデアルとは有限群の次数が正の不変式で生成されるイデアルのことで
ある。この講演では、交代群のヒルベルトイデアルのグレブナ基底について得られ
た結果を紹介する。また、普遍グレブナ基底についても議論する。

1/13(金): 縫田光司 (東京大学 大学院数理科学研究科)
Coxeterマトロイドについて

今回は、マトロイドの一般化の一つである「Coxeterマトロイド」について紹介する。
Coxeterマトロイドは（有限）Coxeter群を用いて定義され、そのCoxeter群が
A型（対称群）の場合が通常のマトロイドに相当する。
Coxeter群は多面体や超平面配置と深く関わっているため、Coxeterマトロイドも
それらの対象と密接な関係を持つ。今回は、Coxeterマトロイドの定義や
基本的な性質の他に、そのような幾何学的な取り扱いについても触れたい。

2/3(金): 小田芳彰 (慶応義塾大学 理工学部数理科学科)
スターでない２つの木の平面への埋め込み

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が存在すると予想した。今回の講演ではこの周辺に関するいくつかの
結果を紹介する。

2/17(金): 脇隼人 (東京工業大学 情報理工学研究科)
完全グラフと完全二部グラフのCrossing Numberについて

与えられた無向グラフ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)