Wykres Brouwera-Haemersa

Wykres Brouwera-Haemersa
Wierzchołki	81
Krawędzie	810
Promień	2
Średnica	2
Obwód	3
Automorfizmy	233280
Liczba chromatyczna	7
Nieruchomości	mocno regularny przechodnie na odległość Ramanujana lokalnie liniowy
Tabela wykresów i parametrów

W matematycznej dziedzinie teorii grafów graf Brouwera -Haemersa jest 20- regularnym grafem nieskierowanym z 81 wierzchołkami i 810 krawędziami. Jest to graf silnie regularny , graf przechodni na odległość i graf Ramanujana . Chociaż jego konstrukcja jest folklorystyczna, został nazwany na cześć Andriesa Brouwera i Willema H. ​​Haemersa, którzy udowodnili jego wyjątkowość jako silnie regularny graf.

Budowa

Wykres Brouwera – Haemersa ma kilka powiązanych konstrukcji algebraicznych. Jednym z najprostszych jest uogólniony wykres Paleya stopnia 4 $:$ go zdefiniować, tworząc wierzchołek dla każdego elementu w skończonym które różnią się o czwartą potęgę .

Nieruchomości

Wykres Brouwera-Haemersa to unikalny, silnie regularny wykres z parametrami (81, 20, 1, 6). Oznacza to, że ma 81 wierzchołków, 20 krawędzi na wierzchołek, 1 trójkąt na krawędź i 6 długości dwóch ścieżek łączących każdą niesąsiadującą parę odrębnych wierzchołków. Jako silnie regularny wykres z trzecim parametrem równym 1, wykres Brouwera-Haemersa ma tę właściwość, że każda krawędź należy do unikalnego trójkąta; to znaczy jest lokalnie liniowy . Znalezienie dużych gęstych grafów o tej właściwości jest jednym ze sformułowań problemu Ruzsy – Szemerédiego .

Oprócz tego, że jest silnie regularny, jest to graf przechodni na odległość .

Historia

Chociaż Brouwer pisze, że „konstrukcja tego wykresu jest folklorem” i cytuje jako wczesne odniesienie artykuł Dale'a M. Mesnera na temat kwadratów łacińskich z 1964 roku , nosi on imię Andriesa Brouwera i Willema H. ​​Haemersa, którzy w 1992 roku opublikowali dowód na to jest jedynym silnie regularnym grafem o tych samych parametrach.

Powiązane wykresy

Wykres Brouwera-Haemersa jest pierwszym z nieskończonej rodziny grafów Ramanujana zdefiniowanych jako uogólnione wykresy Paleya na polach charakterystycznych trzech. Z $wykresem$ i gier jest to jeden z zaledwie trzech możliwych ${\ Displaystyle {\ bigl (} (n ^ {2} + 3n-1) ^ {2}, n ^ {2} (n + 3),$ , których parametry mają postać 2 .

Należy go odróżnić od wykresu Sudoku , innego grafu z 20 regularnymi 81 wierzchołkami. Wykres Sudoku wywodzi się z Sudoku , tworząc wierzchołek dla każdego kwadratu układanki i łącząc dwa kwadraty krawędzią, gdy należą do tego samego rzędu, kolumny lub bloku ${\ Displaystyle 3 \ razy 3}$ puzzle. Ma wiele 9-wierzchołkowych klik i wymaga 9 kolorów w dowolnym kolorze grafu ; 9-kolorowanie tego wykresu opisuje rozwiązaną łamigłówkę Sudoku. Natomiast w przypadku wykresu Brouwera-Haemersa największymi klikami są trójkąty, a liczba potrzebnych kolorów to 7.