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

${\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}$

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. Der Beweis ist in einem peer reviewed Journal publiziert:
• 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.
• Erdős-Vermutung über arithmetische Folgen: Jede Menge ${\displaystyle A}$ mit ${\displaystyle \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 ${\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

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)

Einzelnachweise