Schläfli gróf

Schläfli gróf
Csúcsok 27
borda 216
Kromatikus szám 9
Tulajdonságok Nagyon szabályos
Nincs csipesz
 Médiafájlok a Wikimedia Commons oldalon

A gráfelméletben a Schläfli-gráf egy 16 -os szabályos irányítatlan gráf , 27 csúcsgal és 216 éllel. A gróf Ludwig Schläfli nevéhez fűződik . Ez egy erősen szabályos gráf srg(27, 16, 10, 8) paraméterekkel.

Építkezés

A 27 egyenes metszéspontja egy köbfelületen a Schläfli-gráf komplementere . Így a Schläfli-gráfban két csúcs akkor és csak akkor szomszédos, ha a megfelelő vonalak ferdeek [1]

A Schläfli-gráf a nyolcdimenziós vektorok rendszeréből is előállítható

(1, 0, 0, 0, 0, 0, 1, 0), (1, 0, 0, 0, 0, 0, 0, 1) és (−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),

és e három vektor első hat koordinátájának permutálásával kapott 24 vektor. Ez a 27 vektor megfelel a Schläfli-gráf csúcsainak. Két csúcs akkor és csak akkor szomszédos, ha a megfelelő két vektor belső szorzata 1 [2] .

Részgráfok és szomszédságok

A Schläfli-gráf bármely csúcsának környezete egy 16 csúcsból álló részgráf, amelyben minden csúcsnak 10 szomszédos csúcsa van (a 16-os és 10-es számokat a Schläfli-gráf paramétereiként kapjuk meg, ha szigorúan szabályos gráfként kezeljük). Mindezek a részgráfok izomorfak a Clebsch-gráf [1] [3] komplementerével . Mivel a Clebsch-gráf nem tartalmaz háromszögeket , a Schläfli-gráf nem tartalmaz karmokat . Ez a tény fontos szerepet játszik a Maria Chudnovskaya és Paul Seymour által kidolgozott gráfok karmok nélküli szerkezeti elméletében [4] .

A 27 vonal bármelyik két metszővonala az egyetlen Schläfli dupla-hatos konfigurációhoz tartozik, amely  12 vonalból áll, amelyek metszéspontja egy koronát alkot . Ennek megfelelően a Schläfli-gráfban minden uv él az egyetlen olyan részgráfhoz tartozik, amelyet a K 6 K 2 teljes gráfok közvetlen szorzata alkot , amelyekben az u és v csúcsok a szorzat különböző K 6 részgráfjaihoz tartoznak. A Schläfli-gráf 36 ilyen részgráfot tartalmaz, amelyek közül az egyik nyolcdimenziós térben 0 és 1 koordinátájú vektorokból áll, a fent leírtak szerint [2] .

Ultrahomogenitás

Egy gráfot k -ultrahomogénnek nevezünk, ha két, legfeljebb k csúcsot tartalmazó részgráfja között bármely izomorfizmus kiterjeszthető a teljes gráf automorfizmusára . Ha egy gráf 5-ultrahomogén, akkor ultrahomogén bármely k esetén . Az egyetlen ilyen típusú összekapcsolt véges gráfok a teljes gráfok , a Turan-gráfok , a 3 × 3 -as bábugráfok és az 5 csúcsú ciklus . A végtelen Rado-gráf megszámlálhatatlanul ultrahomogén. Csak két összekapcsolt gráf van, amelyek 4-ultrahomogén, de nem 5-ultrahomogén, a Schläfli-gráf és annak komplementere. A bizonyítás az egyszerű véges csoportok osztályozásán alapul [5] [6] [7] .

Jegyzetek

  1. ↑ 1 2 D. A. Holton, J. Sheehan. A Petersen-grafikon . - Cambridge University Press , 1993. - 270-271 .
  2. ↑ 1 2 F. C. Bussemaker, A. Neumaier. Kivételes gráfok legkisebb sajátérték-2-vel és a kapcsolódó problémák  // Számítási matematika. - 1992. - T. 59 , sz. 200 . – S. 583–608 . - doi : 10.1090/S0025-5718-1992-1134718-6 .
  3. ↑ Peter Jephson Cameron, Jacobus Hendricus van Lint. Tervek, grafikonok, kódok és linkjeik. - Cambridge University Press, 1991. - V. 22 . - S. 35 . - ISBN 978-0-521-41325-1 . Meg kell jegyezni, hogy Cameron és van Lint e gráfok más definícióit használta, amelyek szerint mind a Schläfli-gráf, mind a Clebsch-gráf kiegészíti az itt definiált gráfokat.
  4. ↑ Maria Chudnovsky, Paul Seymour. Felmérések a kombinatorikában 2005. - Cambridge Univ. Nyomda, 2005. - T. 327 . – S. 153–171 . Az eredetiből archiválva : 2010. június 9.
  5. ↑ JMJ Buczak. Véges csoportelmélet. – Oxfordi Egyetem, 1980.
  6. ↑ Peter Jephson Cameron. 6-tranzitív gráfok // Journal of Combinatorial Theory, B. sorozat - 1980. - T. 28 . – S. 168–179 .
  7. ↑ Alice Devillers. Néhány homogén és ultrahomogén szerkezet osztályozása. — Université Libre de Bruxelles, 2002.

Linkek