小さな有向マトロイドの実現可能性の完全な分類

スポンサーリンク

概要

• 論文の詳細を見る

• 点配置、超平面配置の組合せ構造の列挙は古くから研究されてきた組合せ幾何における重要な問題である。しかし、現在までの研究は退化のない場合、2次元の場合の研究がほとんどであった。近年、FinschiとFukudaにより、退化を含み、さらに大きなランクも含んだ有向マトロイドの列挙がなされ、それらの中のどれが実際に点配置の組合せ構造に対応するかという有向マトロイドの実現可能性問題が盛んに調べられた。しかし、それらの研究では実現可能性の完全な分類には成功していなかった。本稿では、それらの実現可能性の完全な分類を行う。具体的には要素数8・ランク4、要素数9・ランク3、要素数9・ランク6の有向マトロイドの実現可能性を完全に分類し、8点からなる3次元の点配置、9点からなる2次元の点配置、9点からなる5次元の点配置の組合せ構造を完全に決定する。また、9頂点からなる5次元多面体の組合せ構造も完全に決定する。

• 2010-04-15

著者

• 宮田 洋行

  東京大学大学院情報理工学系研究科

• 森山 園子

  東京大学ナノ量子情報エレクトロニクス研究機構

• 福田 公明

  スイス連邦工科大学チューリッヒ校

関連論文

• 小さな有向マトロイドの実現可能性の完全な分類
• BDDを用いたグラフのTutte多項式計算の再考察
• 双二次最終多項式による有向マトロイドの実現不可能性判定
• Non-LP orientations, non-line shellings, and non-representable oriented matroids
• Analyzing automorphism groups of oriented matroids by semidefinite programming (Computational Geometry and Discrete Mathematics)
• Computational Analysis of Orientations of Matroids (Computational Geometry and Discrete Mathematics)
• 最小包含球問題から得られる4-cubeグラフの向きづけ
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• 三値マトロイドの生成とWhiteの予想に関する実験
• P行列線形相補性問題の新たな部分クラスの提案
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• 4次元超立方体上のPLCP向き付けの列拳

もっと見る 閉じる

スポンサーリンク