Poloviční graf - Half graph

Poloviční graf se 14 vrcholy

v teorie grafů, pobočka matematika, a poloviční graf je speciální typ bipartitní graf. Tyto grafy se nazývají poloviční grafy, protože mají přibližně polovinu okrajů a kompletní bipartitní graf na stejných vrcholech. Název tyto grafy pojmenoval Paul Erdős a András Hajnal.^[1]

Definice

Definovat poloviční graf na ${ displaystyle 2n}$ vrcholy ${ displaystyle u_ {1}, tečky u_ {n}}$ a ${ displaystyle v_ {1}, tečky v_ {n}}$ , připojit ${ displaystyle u_ {i}}$ na ${ displaystyle v_ {j}}$ kdykoli o hranu ${ Displaystyle i leq j}$ .^[1]

Stejný koncept lze také definovat stejným způsobem pro nekonečné grafy na dvou kopiích libovolné uspořádané sady vrcholů.^[1]Poloviční graf nad přirozenými čísly (s jejich obvyklým uspořádáním) má vlastnost, že každý vrchol ${ displaystyle v_ {j}}$ má konečný stupeň, nejvíce ${ displaystyle j}$ . Vrcholy na druhé straně bipartice mají nekonečný stupeň.^[2]

Nepravidelnost

Jedna aplikace pro poloviční graf se vyskytuje v Szemerédiho pravidelnost lemma, který uvádí, že vrcholy libovolného grafu lze rozdělit na konstantní počet podmnožin stejné velikosti, takže většina párů podmnožin je pravidelná (okraje spojující pár se chovají určitými způsoby jako náhodný graf určité hustoty). Pokud je tímto způsobem rozdělen poloviční graf na ${ displaystyle k}$ podmnožin, bude počet nepravidelných párů alespoň úměrný ${ displaystyle k}$ . Proto není možné posílit lemma pravidelnosti, aby se ukázala existence oddílu, pro který jsou všechny páry pravidelné.^[3]

Vhodný

Poloviční graf má jedinečný perfektní shoda. To je přímo vidět indukcí: ${ displaystyle u_ {n}}$ musí odpovídat svému jedinému sousedovi, ${ displaystyle v_ {n}}$ a zbývající vrcholy tvoří další poloviční graf. Silněji je každý bipartitní graf s jedinečným dokonalým spojením podgrafem polovičního grafu.^[4]

V grafech nespočetného chromatického čísla

Pokud chromatické číslo grafu je nespočet, potom graf nutně obsahuje jako podgraf poloviční graf přirozených čísel. Tento poloviční graf zase obsahuje všechny kompletní bipartitní graf ve kterém je jedna strana bipartice konečná a druhá strana spočetně nekonečná.^[5]

Reference

^ ^A ^b ^C Erdős, Paul (1984), „Some combineatorial, geomet and and set theoretic problems in measure theory“, in Kölzow, D .; Maharam-Stone, D. (eds.), Teorie měření Oberwolfach 1983Přednášky z matematiky, 1089Springer
^ Nešetřil, Jaroslav; Shelah, Saharon (2003), „V pořadí spočítatelných grafů“, European Journal of Combinatorics, 24 (6): 649–663, arXiv:matematika / 0404319, doi:10.1016 / S0195-6698 (03) 00064-7, PAN 1995579
^ Conlon, David; Fox, Jacobe (2012), „Meze pro pravidelnost grafů a odstranění lemmat“, Geometrická a funkční analýza, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007 / s00039-012-0171-x, PAN 2989432
^ Godsil, C. D. (1985), „Obrácení stromů“, Combinatorica, 5 (1): 33–39, doi:10.1007 / bf02579440. Viz zejména Lemma 2.1.
^ Erdős, Paul; Hajnal, András (1985), "Chromatický počet konečných a nekonečných grafů a hypergrafů" (PDF), Diskrétní matematika, 53: 281–285, doi:10.1016 / 0012-365X (85) 90148-7, PAN 0786496. Výsledek, že grafy nespočetného chromatického čísla obsahují nekonečný poloviční graf, je v tomto příspěvku připsán Hajnalovi a citován v článku 1973 od stejných autorů se Shelahem, ale tento článek uvádí výsledek pouze v slabší formě, že grafy nespočetného chromatického čísla obsahují kompletní bipartitní grafy, kde jedna strana je libovolné konečné číslo a druhá strana je nekonečná.

[e-1] A ^b ^C Erdős, Paul (1984), „Some combineatorial, geomet and and set theoretic problems in measure theory“, in Kölzow, D .; Maharam-Stone, D. (eds.), Teorie měření Oberwolfach 1983Přednášky z matematiky, 1089Springer

[ns-2] Nešetřil, Jaroslav; Shelah, Saharon (2003), „V pořadí spočítatelných grafů“, European Journal of Combinatorics, 24 (6): 649–663, arXiv:matematika / 0404319, doi:10.1016 / S0195-6698 (03) 00064-7, PAN 1995579

[cf-3] Conlon, David; Fox, Jacobe (2012), „Meze pro pravidelnost grafů a odstranění lemmat“, Geometrická a funkční analýza, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007 / s00039-012-0171-x, PAN 2989432

[g-4] Godsil, C. D. (1985), „Obrácení stromů“, Combinatorica, 5 (1): 33–39, doi:10.1007 / bf02579440. Viz zejména Lemma 2.1.

[eh-5] Erdős, Paul; Hajnal, András (1985), "Chromatický počet konečných a nekonečných grafů a hypergrafů" (PDF), Diskrétní matematika, 53: 281–285, doi:10.1016 / 0012-365X (85) 90148-7, PAN 0786496. Výsledek, že grafy nespočetného chromatického čísla obsahují nekonečný poloviční graf, je v tomto příspěvku připsán Hajnalovi a citován v článku 1973 od stejných autorů se Shelahem, ale tento článek uvádí výsledek pouze v slabší formě, že grafy nespočetného chromatického čísla obsahují kompletní bipartitní grafy, kde jedna strana je libovolné konečné číslo a druhá strana je nekonečná.

[1]

[2]

[3]

[4]

[5]