シュナイダーの定理

グラフ理論において、シュナイダーの定理は、平面グラフをその接続半集合の順序次元の観点から特徴づけるものである。この定理は、1989 年に証明を発表した Walter Schnyder にちなんで名付けられている。

頂点集合Vと辺集合Eを持つ無向グラフGの接続順序集合P ( G )は、 V ∪ E を要素として持つ高さ2の部分順序集合です。この部分順序では、 xが頂点、yが辺、x がyの 2 つの端点の 1 つである場合に、順序関係x < yが存在します。

半順序の順序次元は、与えられた半順序と交差する全順序の最小の数です。このような順序の集合は、半順序の実現子と呼ばれます。シュナイダーの定理は、グラフGが平面であるためには、 P ( G )の順序次元が最大で 3 である必要があると述べています。

この定理は、ブライトウェルとトロッター（1993、1997）によって、凸多面体、またはより一般的には埋め込み平面グラフの頂点、辺、面から同様に形成される高さ3の部分順序集合の次元の厳密な境界に一般化されました。どちらの場合も、posetの順序次元は最大で4です。ただし、面格子が無制限の順序次元を持つ 4次元多面体が存在するため、この結果は高次元の凸多面体に一般化することはできません。

さらに一般的には、抽象単体複体の場合、複体の面順序集合の順序次元は最大で1 + dであり、ここでdは複体が幾何学的に実現されるユークリッド空間の最小次元である(Ossona de Mendez 1999、2002)。

Schnyder が指摘しているように、グラフGの接続ポセットは、グラフがパスまたはパスのサブグラフである場合に限り、順序次元が 2 になります。接続ポセットの順序次元が 2 の場合、その唯一の可能な実現体は、(グラフの頂点に制限される場合) 互いに逆である 2 つの全順序で構成されます。他の 2 つの順序は、2 つの頂点間の順序関係を含む交差を持ちますが、これは接続ポセットでは許可されません。頂点上のこれらの 2 つの順序では、連続する頂点間のエッジを、2 つのエッジのエンドポイントのうち遅い方の直後に配置することで順序に含めることができますが、他のエッジを含めることはできません。

グラフを4 色で着色できる場合、その接続順序集合の順序次元は最大 4 になります (Schnyder 1989)。

n頂点の完全グラフの接続順序集合は順序次元を持つ(Spencer 1971)。 ${\displaystyle \Theta (\log \log n)}$

• ブライトウェル、G.; トロッター、WT (1993)、「凸多面体の順序次元」、SIAM Journal on Discrete Mathematics、6 (2): 230–245、doi :10.1137/0406018、MR  1215230。
• ブライトウェル、G.; トロッター、WT (1997)、「平面写像の順序次元」、SIAM Journal on Discrete Mathematics、10 (4): 515–528、CiteSeerX  10.1.1.127.1016、doi :10.1137/S0895480192238561、MR  1477654。
• Ossona de Mendez, P. (1999)、「単体複体の幾何学的実現」、Kratochvil, J. (編)、Proc. Int. Symp. Graph Drawing (GD 1999)、Lecture Notes in Computer Science、vol. 1731、Springer-Verlag、pp. 323–332、doi : 10.1007/3-540-46648-7_33、MR  1856785。
• Ossona de Mendez, P. (2002)、「ポセットの実現」(PDF)、Journal of Graph Algorithms and Applications、6 (1): 149–153、doi : 10.7155/jgaa.00048、MR  1898206。
• シュナイダー、W. (1989)、「平面グラフとポセット次元」、Order、5 (4): 323–343、doi :10.1007/BF00353652、MR  1010382、S2CID  122785359。
• Spencer, J. (1971)、「単純な順序の最小スクランブル集合」、Acta Mathematica Academiae Scientiarum Hungaricae、22 (3–4): 349–353、doi :10.1007/bf01896428、MR  0292722、S2CID  123142998。