Earl av Hanson

Hanson-grafen Gi är en oriktad oändlig graf , den enda räknebara homogena grafen som inte innehåller klickar med i -hörn, utan innehåller alla grafer fria från K i som subgrafer . Till exempel är G 3 en triangelfri graf som innehåller alla finita triangelfria grafer.

Graferna är uppkallade efter C. Ward Hanson, som publicerade sin konstruktion 1971 (för alla ) [1] . Den första av dessa grafer G 3 kallas en homogen triangelfri graf eller en universell triangelfri graf .

Byggnad

För att konstruera dessa grafer, arrangerar Hanson hörn av Rado-grafen i en sekvens med egenskapen att för varje ändlig uppsättning S av hörn finns det oändligt många hörn som har S som uppsättningen av tidigaste grannar (existensen av en sådan sekvens unikt definierar Rado-grafen). Sedan definierar han G i som den genererade subgrafen av Rado-grafen, bildad genom att ta bort ändpunkten (i vald ordning) för valfri i -klick i Rado-grafen [1] .

Med denna konstruktion är varje graf Gi en genererad subgraf av grafen Gi + 1 , och föreningen av denna kedja av subgrafer är själva Rado-grafen. Eftersom åtminstone en vertex av i -klicken i Rado-grafen är exkluderad i någon graf G i , kan det inte finnas en i -klick i Gi .

Mångsidighet

Vilken ändlig eller räknebar i -klickfri graf H som helst kan hittas som en genererad subgraf av Gi genom att successivt addera hörn vars tidigare hörn i Gi motsvarar uppsättningen av tidigare grannar till motsvarande hörn i H . Således är Gi en universell graf för en familj av i - klickfria grafer.

Eftersom det finns i -klickfria grafer med godtyckligt stort kromatiskt tal , har Hanson-grafen oändligt kromatiskt tal. Mer strikt, om Hanson-grafen Gi är uppdelad i ett ändligt antal genererade subgrafer , så inkluderar åtminstone en av dessa grafer alla finita grafer fria från i -klickar som genererade subgrafer [1] .

Symmetri

Liksom Rado-grafen innehåller G 3 en dubbelriktad Hamilton-bana så att varje symmetri av banan är en symmetri av hela grafen. Detta är dock inte sant för G i , när i > 3 - för dessa grafer har varje grafautomorfism mer än en omloppsbana [1] .

Anteckningar

  1. ↑ 1 2 3 4 Henson, 1971 , sid. 69–83.

Litteratur