# 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

* 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$^{77}$ 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

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.