@techreport{oai:ipsj.ixsq.nii.ac.jp:00031809,
 author = {中山, 裕貴 and 森山, 園子 and 福田, 公明 and 岡本, 吉央 and Hiroki, Nakayama and Sonoko, Moriyama and Komei, Fukuda and Yoshio, Okamoto},
 issue = {5(2004-AL-099)},
 month = {Jan},
 note = {有向マトロイドとは，実ベクトル空間Rnのベクトル配置を抽象化した組合せモデルである．有向マトロイドはRnのベクトル配置から得られるとき実現可能であるというが，この判定問題はNP困難であることが知られている．実現不可能な有向マトロイドを判定する手段としては，Holt-Klee条件を基にしたnon-HK*性や，双二次最終多項式を用いた手法が提案されている． 我々は台集合の要素数が8 ランクが4の有向マトロイドに着目する．このような有向マトロイドで一様なものは同型を除いて2628個あり，うち24個が実現不可能であることが知られているが，その証明は双二次最終多項式により，浮動小数点演算を用いて行われていた．本研究では，同手法を有理数演算を用いて適用し，実現不可能な24個の有向マトロイド全てを列挙した．さらに，非一様な有向マトロイドで，双二次最終多項式では発見できない実現不可能な有向マトロイドが存在することも示した．, An oriented matroid is a combinatorial model obtained as an abstraction of a vector configuration in a real vector space R^n. An oriented matroid is defined realizable if it is obtained from a vector configuration in R^n, but deciding realizability of an oriented matroid is known to be NP-hard. Hence the methods using non-HK*, which are based on Holt-Klee condition, and using biquadratic final polynomial, are proposed. Now we focus on rank-4 oriented matroids on a 8-element ground set. It is known that there exist 2628 such uniform oriented matroids, and 24 of them are non-realizable. Their specific form were obtained by biquadratic final polynomials with floating-point arithmetic. In our study, we find all such 24 matroids by a same method with exact rational arithmetic. Furthermore, we show there exist non-realizable non-uniform oriented matroids which have no biquadratic final polynomial.},
 title = {双二次最終多項式による有向マトロイドの実現不可能性判定},
 year = {2005}
}