Twierdzenie Turana - Turán's theorem

W teorii grafów , twierdzenie turána ograniczającą liczbę krawędzi, które mogą być zawarte w undirected wykresu , który nie posiada pełną podgrafu danego rozmiaru. Jest to jeden z głównych wyników teorii grafów ekstremalnych , obszar badający największe lub najmniejsze grafy o określonych właściwościach i jest szczególnym przypadkiem problemu zakazanego podgrafu na maksymalnej liczbie krawędzi w grafie, który nie ma danego podgrafu .

Przykładem - wierzchołek wykres, który nie zawiera klika -Vertex mogą być utworzone przez podział zbiór wierzchołków w części o tej samej lub prawie takiej samej wielkości, łączący dwa wierzchołki, przez krawędź, gdy należą do dwóch różnych części. Powstały wykres to wykres Turána . Twierdzenie Turána mówi, że graf Turána ma największą liczbę krawędzi spośród wszystkich grafów K _{r +1} -free n -vertex. ${\ Displaystyle n}$${\ Displaystyle (r+1)}$${\ Displaystyle K_ {r+1}}$${\ Displaystyle n}$${\ Displaystyle r}$ ${\displaystyle T(n,r)}$

Twierdzenie Turána i grafy Turána przedstawiające jego skrajny przypadek zostały po raz pierwszy opisane i zbadane przez węgierskiego matematyka Pála Turána w 1941 roku. Specjalny przypadek twierdzenia dla grafów bez trójkątów jest znany jako twierdzenie Mantela ; stwierdził w 1907 roku holenderski matematyk Willem Mantel.

Komunikat

Twierdzenie Turána mówi, że każdy graf z wierzchołkami, który nie zawiera jako podgrafu, ma liczbę krawędzi co najwyżej ${\ Displaystyle G}$${\ Displaystyle n}$${\ Displaystyle K_ {r+1}}$

${\ Displaystyle {\ Frac {R-1} {R}} \ cdot {\ Frac {n ^ {2}} {2}} = \ po lewej (1-{\ Frac {1} {R}} \ po prawej) \cdot {\frac {n^{2}}{2}}.}$

Ta sama formuła podaje liczbę krawędzi w grafie Turána , więc jest równoważna twierdzeniu Turána w postaci, że wśród prostych grafów -wierzchołków bez -klik, ma maksymalną liczbę krawędzi. ${\displaystyle T(n,r)}$${\ Displaystyle n}$${\ Displaystyle (r+1)}$${\displaystyle T(n,r)}$

Dowody

Aigner i Ziegler (2018) wymieniają pięć różnych dowodów twierdzenia Turána.

Oryginalny dowód Turána wykorzystuje indukcję na liczbie wierzchołków. Biorąc pod uwagę -Vertex -Darmowy wykres z więcej niż wierzchołki i maksymalna liczba krawędzi, dowód znajdzie klika (która musi istnieć przy maksymalności), usuwa się i nakłada się indukcji pozostałej -Vertex podgrafu. Każdy wierzchołek pozostałego podgrafu może sąsiadować z co najwyżej wierzchołkami kliki, a sumując liczbę otrzymanych w ten sposób krawędzi z indukcyjną liczbą krawędzi w podgrafie -wierzchołkowym daje wynik. ${\ Displaystyle n}$${\ Displaystyle K_ {r+1}}$${\ Displaystyle r}$${\displaystyle K_{r}}$${\ Displaystyle (nr)}$${\displaystyle r-1}$${\ Displaystyle (nr) (r-1)}$${\ Displaystyle (nr)}$

Inny dowód autorstwa Paula Erdősa znajduje wierzchołek maksymalnego stopnia z grafu wolnego i używa go do skonstruowania nowego grafu na tym samym zestawie wierzchołków poprzez usunięcie krawędzi między dowolną parą niesąsiadujących elementów i dodanie krawędzi między wszystkimi parami sąsiadów i nie sąsiad. Nowy wykres pozostaje -wolny i ma co najmniej tyle krawędzi. Powtarzanie tej samej konstrukcji rekurencyjnie na podgrafie sąsiadów w końcu daje graf w takiej samej postaci jak graf Turána (zbiór niezależnych zbiorów, z krawędziami między każdymi dwoma wierzchołkami z różnych niezależnych zbiorów), a proste obliczenia pokazują, że liczba krawędzie tego grafu są maksymalizowane, gdy wszystkie niezależne rozmiary zbiorów są tak bliskie, jak to możliwe. ${\displaystyle v}$${\ Displaystyle K_ {r+1}}$${\displaystyle v}$${\ Displaystyle K_ {r+1}}$${\displaystyle v}$${\displaystyle p}$

Motzkin i Straus (1965) udowadniają twierdzenie Turána metodą probabilistyczną , szukając dyskretnego rozkładu prawdopodobieństwa na wierzchołkach danego grafu wolnego, który maksymalizuje oczekiwaną liczbę krawędzi w losowo wybranym podgrafie indukowanym , z każdym wierzchołkiem zawartym w podgrafie niezależnie z danym prawdopodobieństwem. W przypadku rozkładu z prawdopodobieństwem dla wierzchołka ta oczekiwana liczba to . Każdy taki rozkład można modyfikować, wielokrotnie przesuwając prawdopodobieństwo pomiędzy parami niesąsiadujących ze sobą wierzchołków, tak aby wartość oczekiwana nie malała i jedyne wierzchołki z niezerowym prawdopodobieństwem należą do kliki, z czego wynika, że ​​maksymalna oczekiwana wartość jest równa większość . Dlatego też oczekiwana wartość rozkładu równomiernego, czyli dokładnie liczba krawędzi podzielona przez , również wynosi co najwyżej , a sama liczba krawędzi wynosi co najwyżej . ${\ Displaystyle K_ {r+1}}$${\displaystyle p_{i}}$${\displaystyle v_{i}}$${\ Displaystyle \ textstyle \ suma _ {(v_ {i}, v_ {j}) \ w E (G)} p_ {i} p_ {j}}$${\ Displaystyle (r-1)/2r}$${\ Displaystyle 1/n ^ {2}}$${\ Displaystyle (r-1)/2r}$${\displaystyle n^{2}(r-1)/2r}$

Dowód Nogi Alona i Joela Spencera z ich książki Metoda probabilistyczna rozważa losową permutację wierzchołków grafu swobodnego i największą klikę utworzoną przez przedrostek tej permutacji. Obliczając prawdopodobieństwo, że dowolny wierzchołek zostanie uwzględniony, jako funkcję jego stopnia, można wykazać, że oczekiwany rozmiar tej kliki wynosi , gdzie jest stopniem wierzchołka . Musi istnieć klika przynajmniej tej wielkości, więc . Niektóre algebraiczne manipulacje tą nierównością za pomocą nierówności Cauchy'ego-Schwarza i lemat uzgadniania potwierdzają wynik. Zobacz Metoda prawdopodobieństw warunkowych § Twierdzenie Turána po więcej. ${\ Displaystyle K_ {r+1}}$${\ Displaystyle \ textstyle \ suma 1/(n-d_ {i})}$${\displaystyle d_{i}}$${\displaystyle v_{i}}$${\ Displaystyle \ textstyle r \ geq \ suma 1/(n-d_ {i})}$

Aigner i Ziegler nazywają ostatni z pięciu dowodów „najpiękniejszym ze wszystkich”; jego początki są niejasne. Opiera się on na lemie, że dla maksymalnie wolnego grafu niesąsiedztwo jest relacją przechodnią , bo gdyby było odwrotnie i nie sąsiadowały ze sobą i sąsiadowały ze sobą, można by skonstruować graf o większej liczbie krawędzi, usuwając jeden lub dwa z tych trzech wierzchołków i zastąpienie ich kopiami jednego z pozostałych wierzchołków. Ponieważ nieprzyległość jest również symetryczna i zwrotna (żaden wierzchołek nie sąsiaduje ze sobą), tworzy relację równoważności, której klasy równoważności dają każdemu maksymalnemu grafowi taką samą formę jak graf Turána. Podobnie jak w drugim dowodzie, proste obliczenia pokazują, że liczba krawędzi jest maksymalizowana, gdy wszystkie niezależne rozmiary zbiorów są tak bliskie, jak to tylko możliwe. ${\ Displaystyle K_ {r+1}}$${\displaystyle (u,v)}$${\displaystyle (v,w)}$${\ Displaystyle (u, w)}$${\ Displaystyle K_ {r+1}}$

Twierdzenie Mantela

Szczególnym przypadkiem twierdzenia Turána jest twierdzenie Mantela: Maksymalna liczba krawędzi w grafie bez trójkątów -wierzchołków wynosi Innymi słowy, aby otrzymać graf bez trójkątów , należy usunąć prawie połowę krawędzi . ${\displaystyle r=2}$${\ Displaystyle n}$${\displaystyle \lpiętro n^{2}/4\rpiętro.}$${\ Displaystyle K_ {n}}$

Wzmocniona forma twierdzenia Mantela stwierdza, że ​​każdy graf Hamiltona z przynajmniej krawędziami musi być albo kompletnym grafem dwudzielnym, albo musi być pancykliczny : nie tylko zawiera trójkąt, ale musi również zawierać cykle o wszystkich innych możliwych długościach aż do liczby wierzchołków na wykresie. ${\ Displaystyle n ^ {2}/4}$ ${\ Displaystyle K_ {n/2, n/2}}$

Kolejne wzmocnienie twierdzenia Mantela mówi, że krawędzie każdego grafu -wierzchołkowego mogą być pokryte co najwyżej klikami, które są albo krawędziami, albo trójkątami. W konsekwencji numer przecięcia grafu (minimalna liczba klik potrzebnych do pokrycia wszystkich jego krawędzi) wynosi co najwyżej . ${\ Displaystyle n}$${\displaystyle \lpiętro n^{2}/4\rpiętro}$ ${\displaystyle \lpiętro n^{2}/4\rpiętro}$

Zobacz też

• Twierdzenie Erdősa-Stone , uogólnienie twierdzenia Turána z zakazanych klik do zakazanych wykresów Turána

Bibliografia