Oriented matroids and complete-graph embeddings on surfaces

Jurgen Bokowski, and Tomaz Pisanski
Journal of Combinatorial Theory, Series A
Volume 114, Issue 1 , January 2007, Pages 1-19
http://dx.doi.org/10.1016/j.jcta.2006.06.012

射影平面における擬直線アレンジメントがtriangularであるということを，(2次元) cell全体に対するproper 2-coloringで，片方のcolor classがtriangular cellのみからなるものが存在することとする．
まず，6以上の偶数nに対して，n個の擬直線から成るtriangularアレンジメントから，次のようにして種数(n-3)(n-4)/6の向き付け不可能曲面上へのn頂点完全グラフのtriangular埋め込みを得る．
まず，完全グラフの各頂点はアレンジメントの各擬直線に対応させる．
そして，埋め込みの三角形はアレンジメントのtriangular cellに対応させるのである．
しかし，種数が整数であることから，この方法だとnを6で割った余りが0か4のときのみしかうまくいかない．
また，n=12に対してはtriangular擬直線アレンジメントが存在しない．
そのため，n頂点完全グラフのtriangular埋め込みを必ず得るためには擬直線アレンジメントよりも一般的な対象を考える必要がある．
そこで，この研究はtriangular curve arrangementというものを考えて，全ての完全グラフのtriangular埋め込みがtriangular curve arrangementから生成できることを証明した．

論文中の図がきれい．