Graf Brouwer – Haemers - Brouwer–Haemers graph - Wikipedia

Graf Brouwer – Haemers
Vrcholy	81
Hrany	810
Poloměr	2
Průměr	2
Obvod	3
Automorfismy	233,280
Chromatické číslo	7
Vlastnosti	velmi pravidelné; vzdálenost-tranzitivní; Ramanujan; lokálně lineární;
	Tabulka grafů a parametrů

V matematický pole teorie grafů, Graf Brouwer – Haemers je 20pravidelný neorientovaný graf s 81 vrcholy a 810 hranami silně pravidelný graf, a vzdálenost-tranzitivní graf a Ramanujan graf. Ačkoli jeho konstrukce je folklór, to bylo jmenováno po Andries Brouwer a Willem H. Haemers, který dokázal svou jedinečnost jako silně pravidelný graf.

Konstrukce

Graf Brouwer – Haemers má několik souvisejících algebraických konstrukcí. Jedním z nejjednodušších je zobecnění stupně 4 Paleyův graf: lze jej definovat vytvořením vrcholu pro každý prvek v souboru konečné pole ${ displaystyle GF (81)}$ a výhodu pro každé dva prvky, které se liší o čtvrtá síla.^[1]^[2]

Vlastnosti

Graf Brouwer – Haemers je jedinečný silně pravidelný graf s parametry (81, 20, 1, 6). To znamená, že má 81 vrcholů, 20 okrajů na vrchol, 1 trojúhelník na okraj a 6 délek - dvě cesty spojující každou nesousedící dvojici vrcholů.^[3] Jako silně pravidelný graf s třetím parametrem rovným 1 má graf Brouwer – Haemers vlastnost, že každá hrana patří do jedinečného trojúhelníku; to znamená, že je lokálně lineární. Hledání velkých hustých grafů s touto vlastností je jednou z formulací Problém Ruzsa – Szemerédi.^[4]

Kromě toho, že je velmi pravidelný, je to vzdálenost-tranzitivní graf.^[5]

Dějiny

Ačkoli Brouwer píše, že tento graf je „konstrukcí folklóru“, uvádí jako ranou referenci dokument z roku 1964 Latinské čtverce autor: Dale M. Mesner,^[1] je pojmenován po Andries Brouwer a Willem H. Haemers, kteří v roce 1992 publikovali důkaz, že se jedná o jediný silně pravidelný graf se stejnými parametry.^[3]

Související grafy

Graf Brouwer – Haemers je první v nekonečné rodině Ramanujan grafy definované jako zobecněné Paleyovy grafy přes pole charakteristické tři.^[2] S ${ displaystyle 3 krát 3}$ Rookův graf a Graf her, je to jeden z pouhých tří možných silně pravidelných grafů, jejichž parametry mají podobu ${ displaystyle { bigl (} (n ^ {2} + 3n-1) ^ {2}, n ^ {2} (n + 3), 1, n (n + 1) { bigr)}}$ .^[6]

Je třeba jej odlišit od Sudoku graf, jiný 20 pravidelný 81-vrcholový graf. Sudoku graf je odvozen od Sudoku skládanky vytvořením vrcholu pro každý čtverec skládačky a spojením dvou čtverců hranou, pokud patří ke stejnému řádku, sloupci nebo ${ displaystyle 3 krát 3}$ blok skládačky. Má mnoho 9 vrcholů kliky a vyžaduje 9 barev v jakékoli zbarvení grafu; 9barevnost tohoto grafu popisuje vyřešenou hádanku Sudoku.^[7]^[8] Naproti tomu u grafu Brouwer – Haemers jsou největšími klikami trojúhelníky a počet potřebných barev je 7.^[5]

Reference

^ ^A ^b Brouwer, Andries, „Graf Brouwer – Haemers“, Popisy různých grafů, vyvoláno 2019-02-11
^ ^A ^b Podestá, Ricardo A .; Videla, Denis E. (2018), Spektra zobecněných Paleyových grafů a aplikací, arXiv:1812.03332
^ ^A ^b Brouwer, A. E.; Haemers, W. H. (1992), „Struktura a jedinečnost (81,20,1,6) silně pravidelného grafu“, Sbírka příspěvků na počest Jacka van Linta, Diskrétní matematika, 106/107: 77–82, doi:10.1016 / 0012-365X (92) 90532-K, PAN 1181899
^ Clark, L. H .; Entringer, R. C .; McCanna, J. E .; Székely, L. A. (1991), "Extrémní problémy pro místní vlastnosti grafů" (PDF), Australasian Journal of Combinatorics, 4: 25–31, PAN 1129266
^ ^A ^b Weisstein, Eric W. „Graf Brouwer – Haemers“. MathWorld.
^ Bondarenko, Andriy V .; Radchenko, Danylo V. (2013), „Na rodinu velmi pravidelných grafů s ${ displaystyle lambda = 1}$ ", Journal of Combinatorial Theory, Řada B, 103 (4): 521–531, arXiv:1201.0383, doi:10.1016 / j.jctb.2013.05.005, PAN 3071380
^ Gago-Vargas, Jesús; Hartillo-Hermoso, Maria Isabel; Martín-Morales, Jorge; Ucha-Enríquez, Jose Maria (2006), „Sudokus and Gröbner bases: Not only a divertimento", Ganzha, Victor G .; Mayr, Ernst W .; Vorozhtsov, Evgenii V. (eds.), Počítačová algebra ve vědeckých výpočtech, 9. mezinárodní seminář, CASC 2006, Kišiněv, Moldavsko, 11. – 15. Září 2006, sborník, Přednášky v informatice, 4194, Springer, str. 155–165, doi:10.1007/11870814_13
^ Herzberg, Agnes M.; Murty, M. Ram (2007), "Čtverce sudoku a chromatické polynomy" (PDF), Oznámení Americké matematické společnosti, 54 (6): 708–717, PAN 2327972

[b-1] A ^b Brouwer, Andries, „Graf Brouwer – Haemers“, Popisy různých grafů, vyvoláno 2019-02-11

[pv-2] A ^b Podestá, Ricardo A .; Videla, Denis E. (2018), Spektra zobecněných Paleyových grafů a aplikací, arXiv:1812.03332

[bh-3] A ^b Brouwer, A. E.; Haemers, W. H. (1992), „Struktura a jedinečnost (81,20,1,6) silně pravidelného grafu“, Sbírka příspěvků na počest Jacka van Linta, Diskrétní matematika, 106/107: 77–82, doi:10.1016 / 0012-365X (92) 90532-K, PAN 1181899

[cems-4] Clark, L. H .; Entringer, R. C .; McCanna, J. E .; Székely, L. A. (1991), "Extrémní problémy pro místní vlastnosti grafů" (PDF), Australasian Journal of Combinatorics, 4: 25–31, PAN 1129266

[mw-5] A ^b Weisstein, Eric W. „Graf Brouwer – Haemers“. MathWorld.

[br-6] Bondarenko, Andriy V .; Radchenko, Danylo V. (2013), „Na rodinu velmi pravidelných grafů s ${ displaystyle lambda = 1}$ ", Journal of Combinatorial Theory, Řada B, 103 (4): 521–531, arXiv:1201.0383, doi:10.1016 / j.jctb.2013.05.005, PAN 3071380

[ghmu-7] Gago-Vargas, Jesús; Hartillo-Hermoso, Maria Isabel; Martín-Morales, Jorge; Ucha-Enríquez, Jose Maria (2006), „Sudokus and Gröbner bases: Not only a divertimento", Ganzha, Victor G .; Mayr, Ernst W .; Vorozhtsov, Evgenii V. (eds.), Počítačová algebra ve vědeckých výpočtech, 9. mezinárodní seminář, CASC 2006, Kišiněv, Moldavsko, 11. – 15. Září 2006, sborník, Přednášky v informatice, 4194, Springer, str. 155–165, doi:10.1007/11870814_13

[hm-8] Herzberg, Agnes M.; Murty, M. Ram (2007), "Čtverce sudoku a chromatické polynomy" (PDF), Oznámení Americké matematické společnosti, 54 (6): 708–717, PAN 2327972

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]