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+\dots +(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}|\mathrm{\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: Vorlage: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,\dots ,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\le k\le 2n$. Man schätze $M(n)=\underset{A,B}{\min }\underset{k}{\max }{M}_k$ für hinreichend große $n$ ab.

• Sei $H$ ein ungerichter Graph und ${ℱ}_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 ${ℱ}_H$ eine Clique oder eine stabile Menge der Größe $\mathrm{\Omega }(n^{{\delta }_H})$ enthalten.
• Erdős-Vermutung über arithmetische Folgen: Jede Menge $A$ mit $\sum _{n\in A}\frac{1}{n}=\mathrm{\infty }$ enthält eine arithmetische Folge beliebiger Länge.

Vorlage:Anker 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

Vorlage:Siehe auch 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)