Schneiders sætning

Schneiders sætning er en beskrivelse af plane grafer i form af ordensdimensionen dens delvist ordnede toppunktsincidenssæt . Sætningen er opkaldt efter Walter Schneider, som offentliggjorde sit bevis i 1989.

Poset af indfaldende hjørner af en urettet graf G med toppunktssæt V og kantsæt E er en poset med højde 2, der har som elementer. Denne sætning har ordensrelationer, hvis x er et toppunkt, y er en kant, og x er en af ​​enderne af y .

Ordinaldimensionen af ​​et delvist ordnet sæt er det mindste antal komplette ordrer, hvis skæringspunkt giver et givet delvist ordnet sæt. Et sådant sæt af ordrer kaldes en delvist bestilt sæt implementer. Schneiders sætning siger, at en graf G er plan, hvis og kun hvis ordinaldimensionen ikke overstiger tre.

Udvidelser

Sætningen blev generaliseret af Brightwell og Trotter [1] [2] for at opnå et skarpt estimat for dimensionen af ​​posetter i højden tre, dannet på lignende måde ud fra hjørnerne af kanter og flader af et konveks polyeder , eller mere generelt, en indlejret plan graf. I begge tilfælde overstiger den ordinære dimension af et delvist bestilt sæt ikke fire. Resultatet kan dog ikke generaliseres til flerdimensionelle konvekse polyedre , da der er firedimensionelle polyedre, hvis ansigtsgitter har en ubegrænset ordinal dimension.

For abstrakte simple komplekser , overstiger den ordinære dimension af det delvist ordnede sæt af flader af komplekset ikke 1 + d , hvor d er minimumsdimensionen af ​​det euklidiske rum , hvor komplekset har en geometrisk realisering [3] [ 4] .

Andre grafer

Som Schneider bemærkede, har POI'et for en graf G ordensdimension to, hvis og kun hvis grafen er en sti eller en undergraf til en sti. For at et delvist ordnet toppunktsincidenssæt skal have ordensdimension to, er det nødvendigt, at implementeren består af to komplette ordrer, der (begrænset til grafens hjørner) er omvendt til hinanden. Enhver anden to rækkefølger ville give et skæringspunkt, der inkluderer en ordensrelation mellem to toppunkter, hvilket ikke er tilladt for et delvist ordnet toppunktsincidenssæt. For disse to toppunkter kan en kant mellem to tilstødende toppunkter inkluderes i rækkefølgen ved at placere den direkte bag den sidste af buens to endespidser, men ingen andre kanter kan inkluderes.

Hvis en graf kan farvelægges med fire farver, så har dens poset af toppunktsincidens ordinær dimension højst fire ( Schnyder 1989 ).

Det delvist ordnede indfaldssæt af hjørner af en komplet graf med n hjørner har ordinal dimension [5] .

Noter

  1. ↑ Brightwell, Trotter, 1993 .
  2. ↑ Brightwell, Trotter, 1997 .
  3. ↑ Ossona de Mendez, 1999 .
  4. ↑ Ossona de Mendez, 2002 .
  5. ↑ Spencer, 1971 .

Litteratur