Erdős Pál sejtéseinek listája

Erdős Pál a 20. század egyik legkiemelkedőbb és legtermékenyebb matematikusa volt. Rengeteg matematikussal dolgozott együtt a matematika legkülönbözőbb részterületein, számos sejtést fogalmaztak meg, melyek megoldásáért Erdős gyakran pénzdíjat is felajánlott.

Megoldatlan

• Burr–Erdős-sejtés a ritka gráfok Ramsey-számával kapcsolatban.
• Erdős–Faber–Lovász-sejtés gráfok színezésével kapcsolatban (klikkek unióinak színezése)
• Erdős–Gyárfás-sejtés a 3 minimális fokszámú gráfokban található kettőhatvány hosszúságú egyszerű körökről
• Erdős–Hajnal-sejtés arról, hogy egy gráftípus kizárásával definiált gráfcsaládban minden gráf tartalmaz vagy egy nagy klikket vagy egy nagy független halmazt.
• Erdős–Mollin–Walsh-sejtés arról, hogy nem létezik egymást követő három négyzetteljes szám.
• Erdős–Selfridge-sejtés arról, hogy egy lefedőhalmaz legalább egy páratlan számot tartalmaz.
• Erdős–Straus-sejtés, mely kimondja, hogy minden n ≥ 2 egész szám esetén a 4/n racionális szám kifejezhető három egységtört összegeként (4/n = 1/x + 1/y + 1/z).
• Erdős-sejtés számtani sorozatokról, mely kimondja, hogy ha pozitív egészek egy halmazának a reciprokösszege divergál, akkor található a halmazban tetszőlegesen hosszú számtani sorozat. Nem ekvivalens a Szemerédi-tétellel!
• Erdős–Szekeres-tétel, mi szerint bármely nk + 1 darab különböző számból álló sorozatban van vagy egy n-nél hosszabb csökkenő részsorozat, vagy egy k-nál hosszabb növekvő részsorozat.
• Erdős–Turán-sejtés additív bázisokról
• Erdős–Ulam-probléma a sík racionális távolságú sűrű részhalmazairól
• egy sejtés arról, hogy a Sylvester-sorozat reciprokösszege :$\lim _{n\rightarrow \infty }{\frac {a_{n}}{a_{n-1}^{2}}}=1.$.
• egy sejtés Norman Oler-rel a szabályos háromszögbe pakolt körökről arra az esetre, ha a körök száma eggyel kisebb, mint egy háromszögszám.
• a minimális átfedési probléma területén az M(n) határérték becslése.
• Erdős-féle diszkrepanciaprobléma, a ±1-sorozatok részösszegeiről.
  • 2015 szeptemberében Terence Tao adott egy bizonyítást erre a sejtésre, ami jelenleg ellenőrzés alatt áll.
• Erdős–Moser-sejtés, az $1^{n}+2^{n}+\cdots +m^{n}=(m+1)^{n}$ diofantoszi egyenlet megoldásaival foglalkozik.

Megoldott

• Egy sejtés az egyenletes színezéssel kapcsolatban, amit 1970-ben Hajnal András és Szemerédi Endre igazoltak, ettől kezdve neve Hajnal–Szemerédi-tétel.
• Erdős–Lovász-sejtés, amit Michel Deza igazolt 1974-ben.
• Erdős–Heilbronn-sejtés prímek maradékosztályai összegeinek számával kapcsolatban, amit Dias da Silva és Hamidoune bizonyítottak 1994-ben.
• Erdős–Graham-sejtés, mely szerint az egynél nagyobb egész számokat véges darab nemüres részhalmazra bontva valamely részhalmaz egyes elemeinek reciprokösszege kiadja-e az 1-et. Ernie Croot igazolta 2000-ben.
• Erdős–Stewart-sejtés az n! + 1 = p_k^a p_k+1^b diofantoszi egyenletről, 2001-ben Florian Luca oldotta meg.
• Cameron–Erdős-sejtés egészek összegmentes halmazainak számáról, amit 2003–2004-ben egymástól függetlenül Ben Green és Alexander Sapozhenko igazolt.
• Erdős–Menger-tétel végtelen gráfokban lévő útvonalakkal kapcsolatban, amit Ron Aharoni és Eli Berger igazolt 2009-ben.
• Erdős-féle eltérő távolságok problémája. A helyes kitevőt 2010-ben Larry Guth és Nets Katz megadta, de a log n pontos hatványa még kérdéses.
• Erdős–Ginzburg–Ziv-tétel: ha m pozitív egész, akkor 2m−1 db (nem feltétlen különböző) egész szám között biztosan van m darab, melyek összege osztható m-mel.
• Erdős–Anning-tétel: ha egy síkon található végtelen sok pont között páronként egész szám távolság van, akkor azok a pontok egy egyenes mentén fekszenek (kollineárisak).
• Erdős–Fuchs-tétel
• De Bruijn–Erdős-tétel (gráfelmélet)
• De Bruijn–Erdős-tétel (incidencia geometria)
• Erdős–Szőkefalvi-Nagy-tétel

További információk

• Fan Chung, "Open problems of Paul Erdős in graph theory"
• Fan Chung, living version of "Open problems of Paul Erdős in graph theory"