Twierdzenie Erdősa-Gallai

Erdősa -Gallai jest wynikiem teorii grafów , gałęzi matematyki kombinatorycznej . Dostarcza jednego z dwóch znanych podejść do rozwiązania problemu realizacji grafu , tj. podaje warunek konieczny i wystarczający, aby skończony ciąg liczb naturalnych był ciągiem stopni grafu prostego . Sekwencja spełniająca te warunki nazywana jest „graficzną”. Twierdzenie zostało opublikowane w 1960 roku przez Paula Erdősa i Tibora Gallai , od którego pochodzi.

Oświadczenie

$reprezentowana$ nieujemnych liczb może jako ciąg stopni skończonego n wierzchołkach wtedy tylko re ${\ Displaystyle d_ {1} + \ cdots + d_ {n}}$ parzyste i

${\ Displaystyle \ suma _ {i = 1} ^ {k} d_ {i} \ równoważnik k(k-1)+\suma _{i=k+1}^{n}\min(d_{i},k)}$

obowiązuje dla każdego k w ${\ Displaystyle 1 \ równoważnik k \ równoważnik n}$ .

Dowody

Nietrudno wykazać, że warunki twierdzenia Erdősa-Gallai są konieczne, aby ciąg liczb był graficzny. Wymóg, aby suma stopni była parzysta, jest lematem dotyczącym uścisku dłoni , użytym już przez Eulera w jego artykule z 1736 r. o mostach w Królewcu . Nierówność między sumą $stopni$ a sumą pozostałych stopni można ustalić przez podwójne liczenie : lewa strona podaje liczbę przylegań krawędzi i wierzchołków między najwyższymi ${\ displaystyle k$$po$ dwoma punktami końcowymi wysokiego stopnia, stronie daje maksymalną możliwą liczbę krawędzi- sąsiedztwa wierzchołków, w których oba punkty końcowe mają wysoki stopień, a pozostały wyraz po prawej górnej granicy to liczba krawędzi, które mają dokładnie jeden punkt końcowy wysokiego stopnia. Zatem trudniejszą częścią dowodu jest wykazanie, że dla dowolnego ciągu liczb spełniającego te warunki istnieje wykres, dla którego jest to ciąg stopni.

Oryginalny dowód Erdősa i Gallai (1960) był długi i skomplikowany. Choudum (1986) cytuje krótszy dowód Claude'a Berge'a , oparty na idei przepływu sieciowego . Zamiast tego Choudum dostarcza dowodu za pomocą indukcji matematycznej na sumie stopni: pozwala $być$ pierwszym indeksem liczby w sekwencji, dla której ${\ displaystyle d_ {t}$ (lub przedostatnia liczba, jeśli wszystkie są równe), wykorzystuje analizę przypadku, aby pokazać, że sekwencja utworzona przez odjęcie jednego od i od ostatniej liczby w sekwencji $\ displaystyle d_ {t}}$ (i usunięcie ostatniej liczby, jeśli to odejmowanie spowoduje, że stanie się ona zerem) jest ponownie graficzne i tworzy wykres przedstawiający pierwotną sekwencję poprzez dodanie krawędzi między dwiema pozycjami, z których jedna została odjęta.

Tripathi, Venugopalan i West (2010) rozważają sekwencję „podrealizacji”, wykresów, których stopnie są ograniczone w górę przez daną sekwencję stopni. Pokazują one, że jeśli G jest podrealizacją, a i jest najmniejszym indeksem wierzchołka w G , którego stopień nie jest równy d _i , to G można zmodyfikować w sposób, który daje kolejną podrealizację, zwiększając stopień wierzchołka i bez zmieniając stopnie wcześniejszych wierzchołków ciągu. Powtarzane kroki tego rodzaju muszą ostatecznie doprowadzić do realizacji danej sekwencji, dowodząc twierdzenia.

Relacja do partycji całkowitych

Aigner i Triesch (1994) opisują bliskie powiązania między twierdzeniem Erdősa – Gallai a teorią podziałów całkowitych . Niech ${\ Displaystyle m = \ suma d_ {i}}$ ; wtedy posortowane sekwencje liczb całkowitych sumujące się do $m}$ być interpretowane jako partycje $displaystyle$ . W przypadku większości ich sum przedrostków partycje tworzą siatkę , w której minimalna zmiana między pojedynczą partycją a inną partycją znajdującą się niżej w kolejności partycji polega na odjęciu jednego od jednej z liczb i re ja {\ $}}$ i dodaj go do liczby $displaystyle$ o co najmniej dwa ( może wynosić zero). $d_ {j}$ Jak pokazują Aigner i Triesch, operacja ta zachowuje właściwość bycia graficznym, więc aby udowodnić twierdzenie Erdősa-Gallai, wystarczy scharakteryzować sekwencje graficzne, które są maksymalne w tym porządku majoryzacji. Zapewniają taką charakterystykę w postaci diagramów Ferrersa odpowiednich podziałów i pokazują, że jest ona równoważna twierdzeniu Erdősa – Gallai.

Sekwencje graficzne dla innych typów grafów

Podobne twierdzenia opisują ciągi stopni prostych grafów skierowanych, prostych grafów skierowanych z pętlami i prostych grafów dwudzielnych ( Berger 2012 ). Pierwszy problem charakteryzuje twierdzenie Fulkersona – Chena – Anstee . Te dwa ostatnie przypadki, które są równoważne, charakteryzują się twierdzeniem Gale'a-Rysera .

Mocniejsza wersja

Tripathi i Vijay (2003) udowodnili, że wystarczy rozważyć taką nierówność, że $Displaystyle 1 \ równoważnik k <n}$$\$ z ${\ displaystyle$ i dla ${\ displaystyle k = n}$ . Barrus i in. (2012) ograniczają zestaw nierówności dla grafów o przeciwnym ciągu. Jeśli ciąg dodatni d o sumie parzystej nie ma powtarzających się wpisów innych niż maksimum ${\ Displaystyle l = \ max \ {k \ mid d_ {k} \ geq k \}}$ minimum (a długość przekracza największy wpis), wystarczy sprawdzić tylko tę $nierówność$ , gdzie .

Uogólnienie

Skończone ciągi nieujemnych liczb całkowitych ${\ Displaystyle (d_ {1}, \ cdots, d_ {n})}$ z $d_ {n}}$${\ Displaystyle d_ {1} \ geq \$${\ Displaystyle (c_ {1}, \ cdots, c_ {n})}$$parzysty$ jeśli i istnieje to jest graficzne i majorizes ${\ Displaystyle (d_ {1}, \ cdots, d_ {n})}$ . Wynik ten podali Aigner i Triesch (1994) . Mahadev i Peled (1995) wymyślili to na nowo i podali bardziej bezpośredni dowód.

Zobacz też

• Algorytm Havla-Hakimiego

•   Aigner, Marcin ; Triesch, Eberhard (1994), „Realizacja i wyjątkowość na wykresach”, Discrete Mathematics , 136 (1–3): 3–20, doi : 10.1016/0012-365X (94) 00104-Q , MR 1313278 .
• Barrus, doktor medycyny; Hartke, SG; Jao, Kyle F.; West, DB (2012), „Progi długości list graficznych przy ustalonych największych i najmniejszych wpisach oraz ograniczonych lukach” , Discrete Mathematics , 312 (9): 1494–1501, doi : 10.1016/j.disc.2011.05.001
• Berger, Annabell (2012), Związek między liczbą realizacji dla sekwencji stopni a majoryzacją , arXiv : 1212,5443 , Bibcode : 2012arXiv1212.5443B
•   Choudum, SA (1986), „Prosty dowód twierdzenia Erdősa – Gallai o sekwencjach grafów”, Biuletyn Australijskiego Towarzystwa Matematycznego , 33 (1): 67–70, doi : 10.1017 / S0004972700002872 , MR 0823853 .
• Erdős, P. ; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF) , Matematikai Lapok , 11 : 264–274
• Mahadev, NVR; Peled, ONZ (1995), Wykresy progowe i tematy pokrewne , Elsevier
•   Tripathi, Amitabha; Vijay, Sujith (2003), „Uwaga na temat twierdzenia Erdősa i Gallai”, Matematyka dyskretna , 265 (1–3): 417–420, doi : 10,1016 / s0012-365x (02) 00886-5 , MR 1969393
•   Tripathi, Amitabha; Venugopalan, Sushmita; West, Douglas B. (2010), „Krótki konstruktywny dowód charakterystyki list graficznych Erdősa – Gallai” , Discrete Mathematics , 310 (4): 843–844, doi : 10.1016/j.disc.2009.09.023 , MR 2574834