Contele Schläfli

contele Schläfli
Vârfurile 27
coaste 216
Număr cromatic 9
Proprietăți Foarte obișnuit
Fără clește
 Fișiere media la Wikimedia Commons

În teoria grafurilor, un graf Schläfli este un graf nedirecționat obișnuit cu 16 - cu 27 de vârfuri și 216 muchii. Contele este numit după Ludwig Schläfli . Acesta este un grafic puternic regulat cu parametrii srg(27, 16, 10, 8).

Constructii

Graficul de intersecție a 27 de linii pe o suprafață cubică este complementul graficului Schläfli. Astfel, două vârfuri sunt adiacente într-un grafic Schläfli dacă și numai dacă liniile corespunzătoare sunt oblice [1]

Graficul Schläfli poate fi obținut și din sistemul de vectori opt-dimensionali

(1, 0, 0, 0, 0, 0, 1, 0), (1, 0, 0, 0, 0, 0, 0, 1) și (−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),

și 24 de vectori obținuți prin permutarea primelor șase coordonate ale acestor trei vectori. Acești 27 de vectori corespund vârfurilor grafului Schläfli. Două vârfuri sunt adiacente dacă și numai dacă produsul interior al celor doi vectori corespunzători este 1 [2] .

Subgrafe și cartiere

Vecinătatea oricărui vârf al unui graf Schläfli este un subgraf cu 16 vârfuri în care fiecare vârf are 10 vârfuri învecinate (numerele 16 și 10 sunt obținute ca parametri ai grafului Schläfli atunci când este tratat ca un graf strict regulat). Toate aceste subgrafe sunt izomorfe la complementul grafului Clebsch [1] [3] . Deoarece graficul Clebsch nu conține triunghiuri , graficul Schläfli nu conține gheare . Acest fapt joacă un rol important în teoria structurală fără gheare a graficelor dezvoltată de Maria Chudnovskaya și Paul Seymour [4] .

Orice două linii care se intersectează din aceste 27 de linii aparțin singurei configurații Schläfli dublu-șase , un  set de 12 linii a căror intersecție formează o coroană . În consecință, în graficul Schläfli, fiecare muchie uv aparține singurului subgraf format din produsul direct al graficelor complete K 6 K 2 în care vârfurile u și v aparțin diferitelor K 6 subgrafe ale produsului. Graficul Schläfli conține 36 de subgrafe de acest fel, dintre care unul este format din vectori cu coordonatele 0 și 1 în spațiu cu opt dimensiuni, așa cum este descris mai sus [2] .

Ultraomogenitate

Un graf se numește k -ultraomogen dacă orice izomorfism între două dintre subgrafele sale generate care conțin cel mult k vârfuri poate fi extins la un automorfism al întregului graf. Dacă un grafic este 5-ultraomogen, atunci este ultraomogen pentru orice k . Singurele grafuri finite conectate de acest tip sunt grafurile complete , grafurile Turan, grafurile 3×3 rook și un ciclu cu 5 vârfuri . Graficul Rado infinit este numărabil ultraomogen. Există doar două grafuri conectate care sunt 4-ultraomogene, dar nu 5-ultraomogene, graful Schläfli și complementul său. Dovada se bazează pe clasificarea grupurilor finite simple [5] [6] [7] .

Note

  1. ↑ 1 2 D. A. Holton, J. Sheehan. Graficul Petersen . - Cambridge University Press , 1993. - pp . 270-271 .
  2. ↑ 1 2 F. C. Bussemaker, A. Neumaier. Grafice excepționale cu cea mai mică valoare proprie-2 și probleme conexe  // Matematica calculului. - 1992. - T. 59 , nr. 200 . — S. 583–608 . - doi : 10.1090/S0025-5718-1992-1134718-6 .
  3. ↑ Peter Jephson Cameron, Jacobus Hendricus van Lint. Modele, grafice, coduri și legăturile acestora. - Cambridge University Press, 1991. - V. 22 . - S. 35 . - ISBN 978-0-521-41325-1 . Trebuie remarcat faptul că Cameron și van Lint au folosit alte definiții ale acestor grafice, conform cărora atât graficul Schläfli, cât și cel Clebsch sunt completări ale graficelor definite aici.
  4. ↑ Maria Chudnovsky, Paul Seymour. Sondaje în combinatorică 2005. - Cambridge Univ. Press, 2005. - T. 327 . — S. 153–171 . Arhivat din original pe 9 iunie 2010.
  5. ↑ JMJ Buczak. Teoria grupurilor finite. - Universitatea Oxford, 1980.
  6. ↑ Peter Jephson Cameron. 6-grafuri tranzitive // ​​Journal of Combinatorial Theory, Seria B. - 1980. - T. 28 . — S. 168–179 .
  7. ↑ Alice Devillers. Clasificarea unor structuri omogene şi ultraomogene. — Université Libre de Bruxelles, 2002.

Link -uri