Halv graf

En halvgraf med 14 vertex

Inom grafteorin , en gren av matematiken , är en halv graf en speciell typ av tvådelad graf . Dessa grafer kallas halvgraferna eftersom de har ungefär hälften av kanterna på en komplett tvådelad graf på samma hörn. Namnet gavs till dessa grafer av Paul Erdős och András Hajnal .

Definition

För att definiera den halva grafen på $2n$ hörn $u_{1},\dots u_{n}$ och $v_{1}, \dots v_{n}$ , koppla $u_{i}$ till $v_{j}$ med en kant närhelst $i\leq j$ .

Samma koncept kan också definieras på samma sätt för oändliga grafer över två kopior av valfri ordnad uppsättning av hörn. Den halva grafen över de naturliga talen (med deras vanliga ordning) har egenskapen att varje vertex $v_{j}$ har finit grad , högst $j$ . Topparna på andra sidan av dubbelpartitionen har oändlig grad.

Egenskaper

Motsvarande

Den halva grafen har en unik perfekt matchning . Detta är enkelt att se genom induktion: $u_{n}$ måste matchas till sin enda granne, $v_{n}$ , och de återstående hörnen bildar ytterligare en halv graf. Mer starkt är att varje tvådelad graf med en unik perfekt matchning är en subgraf till en halv graf.

I grafer med oräkneliga kromatiska tal

Om det kromatiska talet för en graf är oräkneligt , så innehåller grafen nödvändigtvis som en undergraf en halv graf över de naturliga talen. Denna halva graf innehåller i sin tur varje komplett tvådelad graf där ena sidan av tvådelad uppdelning är ändlig och den andra sidan är oändlig.

Ansökningar

Regelbundenhet

En tillämpning för den halva grafen förekommer i Szemerédi regularity lemma , som anger att hörnen på vilken graf som helst kan delas upp i ett konstant antal delmängder av samma storlek, så att de flesta par av delmängder är regelbundna (kanterna som förbinder paret beter sig i vissa sätt som en slumpmässig graf med en viss densitet). Om den halva grafen är uppdelad på detta sätt i $k$ delmängder, kommer antalet oregelbundna par att vara åtminstone proportionellt mot $k$ . Därför är det inte möjligt att förstärka regularitetslemma för att visa existensen av en partition för vilken alla par är regelbundna. Å andra sidan, för alla heltal $k$ , följer de grafer som inte har en $2k$ -vertex halvgraf som en inducerad subgraf en starkare version av regularitetslemma utan oregelbundna par.

Stabilitet

Saharon Shelahs instabila formelsats i modellteorin kännetecknar de stabila teorierna ( kompletta teorier som har få typer ) genom att det inte finns uträkneligt oändliga halvgrafer. Shelah definierar en komplett teori som att den har orderegenskapen om det finns en modell $M$ av teorin, en formel $\phi ({\bar {x}},{ \bar {y}})$ på två ändliga tuplar av fria variabler ${\bar {x}}$ och ${\bar {y}}$ , och ett system med oräkneligt många värden ${\bar {x}}_{i}$ och ${\bar {y}}_{i}$ för dessa variabler så att paren ${\displaystyle {\bigl \{}({\bar {x}}_{i},{\bar {y}}_{i })\mid M\models \phi ({\bar {x}}_{i},{\bar {y}}_{j}){\bigr \}}} bildar kanterna på en räknebar halvgraf$ på hörn ${\bar {x}}_{i}$ och ${\bar {y}}_{i}$ . Intuitivt tillåter existensen av dessa halvgrafer en att konstruera oändligt ordnade uppsättningar inom modellen. Den instabila formelsatsen säger att en komplett teori är stabil om och endast om den inte har orderegenskapen.