Vermutungen von Paul Erdős

Der Mathematiker Paul Erdős hat in seinen Arbeiten viele Vermutungen in verschiedenen Bereichen der Mathematik aufgestellt.

Vermutungen zur Zahlentheorie

Siehe auch: Zahlentheorie

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

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

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

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

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

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

• $\{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 $4,7,15,21,45,75,105$.

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

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

Bis $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 $(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. Der Beweis ist in einem peer reviewed Journal publiziert:
• Erdős-Woods-Vermutung: Gegeben sei eine beliebige ganze Zahl $n$. Dann gibt es eine positive ganze Zahl $k$, so dass $n$ durch die Liste der Primfaktoren von $n,n+1,\dotsc ,n+k$ eindeutig bestimmt wird.

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

• Sei $H$ ein ungerichter Graph und ${\mathcal {F}}_{H}$ die Familie von Graphen, die $H$ nicht als induzierten Teilgraphen enthalten. Dann gibt es ein $\delta _{H}>0$, so dass alle n-Graphen in ${\mathcal {F}}_{H}$ eine Clique oder eine stabile Menge der Größe $\Omega (n^{\delta _{H}})$ enthalten.
• Erdős-Vermutung über arithmetische Folgen: Jede Menge $A$ mit $\sum _{n\in A}{\frac {1}{n}}\ =\ \infty$ enthält eine arithmetische Folge beliebiger Länge.

Vermutungen zur Graphentheorie

• Erdős-Faber-Lovász-Vermutung: Ein Graph, der eine Vereinigung vollständiger Graphen mit $k$ Knoten ist, die paarweise höchstens einen Knoten gemeinsam haben, ist $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 von Erdős stammen oder an denen Erdős beteiligt war, betreffen das Gebiet der Ramsey-Theorie und insbesondere die Ramsey-Zahlen. Als herausragende Beispiele sind die Vermutung von Bondy und Erdős und die Erdős-Sós-Vermutung zu nennen.

Weblinks

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