Pół wykresu

14-wierzchołkowy półgraf

W teorii grafów , gałęzi matematyki , wykres połówkowy jest szczególnym typem wykresu dwudzielnego . Grafy te nazywane są grafami połówkowymi, ponieważ mają mniej więcej połowę krawędzi pełnego grafu dwudzielnego na tych samych wierzchołkach. Nazwy tych wykresów nadali Paul Erdős i András Hajnal .

Definicja

Aby zdefiniować półwykres na wierzchołkach $Displaystyle u_ {1}, \ kropki u_ {n}}$$\$$n}}$ … ${1}$$\ displaystyle v_ {j}$ , połącz krawędzią za każdym razem, gdy u $}} v jot$$}$ .

To samo pojęcie można również zdefiniować w ten sam sposób dla nieskończonych grafów na dwóch kopiach dowolnego uporządkowanego zestawu wierzchołków. Półwykres liczb naturalnych (z ich zwykłą kolejnością) ma tę właściwość, że każdy wierzchołek $ma$ skończony stopień , najwyżej $j}$ . Wierzchołki po drugiej stronie dwupodziału mają nieskończony stopień.

Nieruchomości

Dopasowanie

Półwykres ma unikalne idealne dopasowanie . $Można$ łatwo zobaczyć za pomocą indukcji: być dopasowany do swojego jedynego sąsiada, $wykresu$ pozostałe wierzchołki tworzą kolejną połowę Co więcej, każdy graf dwudzielny z unikalnym doskonałym dopasowaniem jest podgrafem wykresu połówkowego.

W grafach o niezliczonej liczbie chromatycznej

Jeśli liczba chromatyczna grafu jest niepoliczalna , to wykres koniecznie zawiera jako podgraf półwykres liczb naturalnych. Z kolei ten półwykres zawiera każdy pełny graf dwudzielny , w którym jedna strona dwudzielnego podziału jest skończona, a druga przeliczalnie nieskończona.

Aplikacje

Prawidłowość

Jedno zastosowanie wykresu połówkowego występuje w lemacie o regularności Szemerédiego , który stwierdza, że ​​wierzchołki dowolnego grafu można podzielić na stałą liczbę podzbiorów o równej wielkości, tak że większość par podzbiorów jest regularna (krawędzie łączące parę zachowują się w w określony sposób, jak losowy wykres o określonej gęstości). Jeśli półwykres zostanie podzielony w ten sposób na podzbiory, liczba nieregularnych par będzie co najmniej proporcjonalna do $displaystyle$$k}$ . Dlatego nie jest możliwe wzmocnienie lematu o regularności, aby pokazać istnienie podziału, dla którego wszystkie pary są regularne. Z drugiej strony, dla dowolnej liczby $są$ grafy, które nie mają $wykresu$ jako podgrafu indukowanego, z mocniejszą wersją lematu o regularności bez nieregularnych par.

Stabilność

o niestabilnej formule Saharona Shelaha w teorii modeli charakteryzuje stabilne teorie ( pełne teorie , które mają kilka typów ) przez nieistnienie przeliczalnie nieskończonych grafów połówkowych. Shelah definiuje kompletną teorię jako mającą właściwość porządku , jeśli istnieje model teorii, formuła ${\ Displaystyle \ phi ({\ bar {x}}$$($ na dwóch skończonych krotkach wolnych zmiennych $\$$displaystyle {\ bar {y}}}$ oraz systemie przeliczalnie wielu wartości $displaystyle {\ bar {x}} _ {i}}$ \ i ${\ Displaystyle {\ bar {y}} _ {i}}$ dla tych zmiennych tak, że pary ${\ Displaystyle {\ bigl \ {} ({\ bar {x}} _ {i}, {\ bar {y}} _ {i}) \ mid M \ modele \ phi ( {\ bar {x}} _ {i}, {\ bar {y}} _ {j}) {\ bigr \}}} tworzą krawędzie przeliczalnego półgrafu$ na wierzchołkach ${\ Displaystyle {\ bar {x}} _ {i}} i$$\ Displaystyle {\ bar {y}} _ {i}}$ { . Intuicyjnie istnienie tych półgrafów pozwala na konstruowanie nieskończonych uporządkowanych zbiorów w ramach modelu. Twierdzenie o niestabilnej formule mówi, że kompletna teoria jest stabilna wtedy i tylko wtedy, gdy nie ma właściwości porządku.