Vermutungen von Paul Erdős

Der Mathematiker Paul Erdős h​at in seinen Arbeiten v​iele Vermutungen i​n verschiedenen Bereichen d​er Mathematik aufgestellt.

Vermutungen zur Zahlentheorie

Siehe auch: Zahlentheorie

• Erdős-Moser-Vermutung: Sie besagt, dass die Gleichung

${\displaystyle 1^{n}+2^{n}+\ldots +(m-1)^{n}=m^{n}}$

nur die Lösungen ${\displaystyle (n,m)=(0,2)}$ und ${\displaystyle (1,3)}$ hat.

• Erdős-Straus-Vermutung: Sie besagt, dass die Gleichung

${\displaystyle {\frac {4}{n}}={\frac {1}{a}}+{\frac {1}{b}}+{\frac {1}{c}}}$

für jede natürliche Zahl ${\displaystyle n>1}$ eine Lösung in natürlichen Zahlen ${\displaystyle a,b,c}$ hat.

• ${\displaystyle \{n\in \mathbb {N} |\forall \;k\in \mathbb {N}$ :\;\;2^{k}<n\Rightarrow n-2^{k}\in \mathbb {P} \}=\{4,7,15,21,45,75,105\}}

Betrachten wir die Menge S aller natürlichen Zahlen n mit folgender Eigenschaft:

Für jede natürliche Zahl k mit k>0 und 2^k < n ist n - 2^k eine Primzahl.

Dann enthält S sicherlich die Zahlen ${\displaystyle 4,7,15,21,45,75,105}$.

Zum Beispiel ist 45 in S, weil die Zahlen ${\displaystyle 45-2=43}$, ${\displaystyle 45-4=41}$, ${\displaystyle 45-8=37}$, ${\displaystyle 45-16=29}$, ${\displaystyle 45-32=13}$ alles Primzahlen sind.

Die Vermutung besagt nun, dass S nur aus diesen 7 Zahlen besteht.

Bis ${\displaystyle n=2^{77}}$ ist diese Vermutung nachgerechnet worden, d. h., es gibt sicherlich keine Zahlen in S außer den genannten, die kleiner als 2⁷⁷ sind.

Jede Zahl n in S (außer 4) liefert automatisch einen Primzahlzwilling, nämlich ${\displaystyle (n-2,n-4)}$.

Siehe auch: Folge A039669 in OEIS

• Erdős-Divergenz-Vermutung: Sie besagt, dass es für jede unendliche Folge der Zahlen +1 und −1 äquidistante Samples endlicher Länge gibt, die sich zu einer betragsmäßig beliebig großen Summe addieren. Terence Tao hat 2015 einen Beweis vorgelegt.[1] Der Beweis ist in einem peer reviewed Journal publiziert:[2]
• Erdős-Woods-Vermutung: Gegeben sei eine beliebige ganze Zahl ${\displaystyle n}$. Dann gibt es eine positive ganze Zahl ${\displaystyle k}$, so dass ${\displaystyle n}$ durch die Liste der Primfaktoren von ${\displaystyle n,n+1,\dotsc ,n+k}$ eindeutig bestimmt wird.

• Seien ${\displaystyle A={a_{i}}}$ und ${\displaystyle B={b_{j}}}$ komplementäre n-elementige Teilmengen von ${\displaystyle {1,...,2n}}$. Sei ${\displaystyle M_{k}}$ die Menge der Lösungen ${\displaystyle a_{i}-b_{j}=k}$ mit ${\displaystyle -2n\leq k\leq 2n}$. Man schätze ${\displaystyle M(n)=\min _{A,B}\max _{k}M_{k}}$ für hinreichend große ${\displaystyle n}$ ab.

• Sei ${\displaystyle H}$ ein ungerichter Graph und ${\displaystyle {\mathcal {F}}_{H}}$ die Familie von Graphen, die ${\displaystyle H}$ nicht als induzierten Teilgraphen enthalten. Dann gibt es ein ${\displaystyle \delta _{H}>0}$, so dass alle n-Graphen in ${\displaystyle {\mathcal {F}}_{H}}$ eine Clique oder eine stabile Menge der Größe ${\displaystyle \Omega (n^{\delta _{H}})}$ enthalten.

Vermutungen zur Graphentheorie

• Erdős-Faber-Lovász-Vermutung: Ein Graph, der eine Vereinigung vollständiger Graphen mit ${\displaystyle k}$ Knoten ist, die paarweise höchstens einen Knoten gemeinsam haben, ist ${\displaystyle k}$-chromatisch.
• Erdős-Gyárfás-Vermutung: Jeder Graph, dessen Knoten alle mindestens Grad 3 haben, enthält einen Kreis, dessen Länge eine Zweierpotenz ist.

Vermutungen zur Ramsey-Theorie

Siehe auch: „Vermutungen“ im Artikel Satz von Ramsey

Viele Vermutungen, welche v​on Erdős stammen o​der an d​enen Erdős beteiligt war, betreffen d​as Gebiet d​er Ramsey-Theorie u​nd insbesondere d​ie Ramsey-Zahlen. Als herausragende Beispiele s​ind die Vermutung v​on Bondy u​nd Erdős u​nd die Erdős-Sós-Vermutung z​u nennen.

Weblinks

• F. R. K. Chung: Open problems of Paul Erdos in graph theory (PDF; 323 kB)

Einzelnachweise

1. Chris Cesare: Maths whizz solves a master’s riddle. Nature News, 25. September 2015.
2. Terence Taos Beweis der Divergenzvermutung in der Fachzeitschrift Discrete Analysis, mit Link zu einem Video von einem Vortrag darüber