Hoffmann-Singleton-tétel

1. Sablon:Humatek

Hoffman–Singleton-tétel

A **Hoffman–Singleton-tétel** a gráfelmélet egyik híres eredménye, amely a Moore-gráfok szerkezetét és lehetséges méreteit írja le. A tétel megadja az összes lehetséges véges, szabályos gráf paramétereit, amelyek maximális csúcsfok mellett nem tartalmaznak három vagy annál rövidebb köröket.

A tétel megfogalmazása

Legyen $G$ egy $d$-reguláris, hurokmentes gráf, amelyben a gráf átmérője $2$. Ha $G$ maximális számú csúcsot tartalmaz az adott paraméterek mellett, akkor $G$-t **Moore-gráfnak** nevezzük, és a csúcsok száma:

$n=1+d+d(d-1).$

A Hoffman–Singleton-tétel kimondja, hogy $d$ értékei korlátozottak: $d=1,2,3,7\text{ vagy }57.$

Magyarázat

A Moore-gráfok azok a véges, maximális szabályos gráfok, amelyek adott átmérő mellett a lehető legtöbb csúcsot tartalmazzák. A Hoffman–Singleton-tétel megmutatja, hogy az ilyen gráfok létezése csak néhány csúcsfok-értékre lehetséges.

1. **$d=1$:** Egy élből álló gráf (két csúccsal). 2. **$d=2$:** Egy körgráf ($C_n$) átmérővel 2. 3. **$d=3$:** A Petersen-gráf az egyetlen ilyen típusú Moore-gráf. 4. **$d=7$:** Egy létező Moore-gráf 50 csúccsal, amelyet a Hoffman–Singleton-tétel alapján konstruáltak. 5. **$d=57$:** A létezés kérdése nyitott, de eddig nem találtak ilyen gráfot.

Példa

• • Petersen-gráf:**

A Petersen-gráf egy $3$-reguláris, 10 csúcsú és 15 élű gráf, amely megfelel a $d=3$, $n=1+3+3(3-1)=10$ feltételeknek. Ez az egyetlen Moore-gráf $d=3$ esetén.

Következmények

A Hoffman–Singleton-tételnek jelentős szerepe van a gráfelméletben:

• **Extremális gráfelmélet:** Maximális gráfok tulajdonságainak vizsgálata.
• **Kombinatorikus tervezés:** A Moore-gráfok struktúrája szorosan kapcsolódik a blokktervekhez és más kombinatorikai problémákhoz.
• **Cayley-gráfok:** A Moore-gráfok konstrukciója gyakran kapcsolódik véges csoportok és azok Cayley-gráfjainak vizsgálatához.

Megjegyzések

• A Hoffman–Singleton-tétel az algebrai gráfelmélet egyik fontos eredménye, amely a spektrális gráfelmélet eszközeivel bizonyítható.
• A $d=57$ eset létezésének kérdése nyitott, és az ilyen gráf konstrukciójának megtalálása vagy létezésének cáfolata az egyik nyitott probléma a gráfelméletben.
• A Moore-gráfok maximális struktúrájuk miatt különösen érdekesek hálózatok optimalizálása és szimmetria-alapú problémák szempontjából.

• Sablon:En: Sablon:T