4 ms·

Erdos Problems Collection

82 points by dargscisyhp 2y ago

johnthescott 2y ago
if you like the "book", you may like the scottish book. https://en.wikipedia.org/wiki/Scottish_Book eastern european mathematics ...
- FabHK 2y ago
  And you might like Proofs from THE BOOK: https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK
skinner_ 2y ago
The question of what is an Erdős problem and what is not is not black and white. My team has managed to solve a problem that's sort of an Erdős problem. In the early sixties, Leo Moser asked about the value of some quantity. In a 1985 paper, Erdős commented that the quantity “seems likely” to be less than 1/4. It was known to be at most 2/7. After a long line of improvements by several teams, we were the first ones to go below 1/4. For those who are interested, https://www.sfu.ca/~vjungic/RamseyProjects/section-11.html https://www.sfu.ca/~vjungic/RamseyProjects/section-11.html describes the question. Our answer is at https://arxiv.org/abs/2207.14179 https://arxiv.org/abs/2207.14179, and a popsci account of our result is at https://www.quantamagazine.org/mathematicians-break-bounds-in-coloring-problem-20230719/ https://www.quantamagazine.org/mathematicians-break-bounds-i... .
- throw_pm23 2y ago
  Nice... but was 1/4 here a kind of arbitrary "nice number" threshold? It seems now the final value is somewhere in [0.22, 0.247], right?
  - skinner_ 2y ago
    Very good question! Yes, the final value is somewhere in there. I expect that it's the lowest point, meaning Croft's Tortoise is optimal. Since then we have an unpublished new 0.241 upper bound with the same proof but wider computer search. We don't know what Erdős had in mind when picking 1/4, but we know something that seems to make the 1/4 value special. Many of the earlier attempts to prove Erdős's conjecture were based on a notion called fractional chromatic number. The numbers went down like this: 0.2857, 0.2813, 0.2763, 0.2565, 0.2518, 0.2506. We now have a new preprint that reaches exactly 1/4, not more not less, and we don't know how to improve it: https://arxiv.org/abs/2311.10069 https://arxiv.org/abs/2311.10069 So it seems like the fractional chromatic number based approach has an inherent barrier at 1/4. If that is true, those earlier fractional chromatic number based attempts were doomed, and we only managed to break that barrier because we used some extra ideas. (Namely, Fourier analysis).
    - throw_pm23 2y ago
      Thanks for explaining, and again, nice set of results!
- TFBloom 2y ago
  Added! https://www.erdosproblems.com/232 https://www.erdosproblems.com/232 There are certainly many Erdős problems, broadly interpreted, still to be added. Any suggestions of missing problems to be added are welcome.
  - skinner_ 2y ago
    Awesome, thank you! A seal of approval!
pnielsen2 2y ago
One of my friends from undergrad solved an erdos problem a couple years ago during the first year of his PhD... Absolutely insane.
readyplayernull 2y ago
> Ron Graham bet him $500 that he could not stop taking the drug for a month. Erdős won the bet, but complained that during his abstinence mathematics had been set back by a month: 'Before, when I looked at a piece of blank paper my mind was filled with ideas. Now all I see is a blank piece of paper.' After he won the bet, he promptly resumed his amphetamine use. http://en.wikipedia.org/wiki/Paul_Erd%C5%91s http://en.wikipedia.org/wiki/Paul_Erd%C5%91s
- jiggawatts 2y ago
  Perhaps he was self-medicating for ADHD?
lanstin 2y ago
The owner of this website is asking for software help. https://www.erdosproblems.com/help https://www.erdosproblems.com/help
legedemon 2y ago
I clicked on a random open problem and found https://www.erdosproblems.com/170 https://www.erdosproblems.com/170. The text of the problem didn't make sense. The wikipedia article stated the problem much more nicely which was thankfully linked from the OP's website. Wish the problem could be stated more simply on the main site as well. Will certainly try and help the owner of the website.
- TFBloom 2y ago
  Sorry you found the text confusing; often I have reworded the problem text to give what is, for me, the clearest explanation of the problem. Of course, what the clearest explanation is is very much dependent on one's own background and personal tastes! For example for this problem I think a lot about sumsets and difference sets anyway, so it made sense to phrase it in those terms. If you have a suggestion on how it could be rephrased for clarity then please do email in.

82 points by dargscisyhp 2y ago

if you like the "book", you may like the scottish book. https://en.wikipedia.org/wiki/Scottish_Book eastern european mathematics ...

FabHK 2y ago
And you might like Proofs from THE BOOK: https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK

skinner_ 2y ago

The question of what is an Erdős problem and what is not is not black and white. My team has managed to solve a problem that's sort of an Erdős problem. In the early sixties, Leo Moser asked about the value of some quantity. In a 1985 paper, Erdős commented that the quantity “seems likely” to be less than 1/4. It was known to be at most 2/7. After a long line of improvements by several teams, we were the first ones to go below 1/4. For those who are interested, https://www.sfu.ca/~vjungic/RamseyProjects/section-11.html https://www.sfu.ca/~vjungic/RamseyProjects/section-11.html describes the question. Our answer is at https://arxiv.org/abs/2207.14179 https://arxiv.org/abs/2207.14179, and a popsci account of our result is at https://www.quantamagazine.org/mathematicians-break-bounds-in-coloring-problem-20230719/ https://www.quantamagazine.org/mathematicians-break-bounds-i... .

throw_pm23 2y ago
Nice... but was 1/4 here a kind of arbitrary "nice number" threshold? It seems now the final value is somewhere in [0.22, 0.247], right?
- skinner_ 2y ago
  Very good question! Yes, the final value is somewhere in there. I expect that it's the lowest point, meaning Croft's Tortoise is optimal. Since then we have an unpublished new 0.241 upper bound with the same proof but wider computer search. We don't know what Erdős had in mind when picking 1/4, but we know something that seems to make the 1/4 value special. Many of the earlier attempts to prove Erdős's conjecture were based on a notion called fractional chromatic number. The numbers went down like this: 0.2857, 0.2813, 0.2763, 0.2565, 0.2518, 0.2506. We now have a new preprint that reaches exactly 1/4, not more not less, and we don't know how to improve it: https://arxiv.org/abs/2311.10069 https://arxiv.org/abs/2311.10069 So it seems like the fractional chromatic number based approach has an inherent barrier at 1/4. If that is true, those earlier fractional chromatic number based attempts were doomed, and we only managed to break that barrier because we used some extra ideas. (Namely, Fourier analysis).
  - throw_pm23 2y ago
    Thanks for explaining, and again, nice set of results!
TFBloom 2y ago
Added! https://www.erdosproblems.com/232 https://www.erdosproblems.com/232 There are certainly many Erdős problems, broadly interpreted, still to be added. Any suggestions of missing problems to be added are welcome.
- skinner_ 2y ago
  Awesome, thank you! A seal of approval!

pnielsen2 2y ago

One of my friends from undergrad solved an erdos problem a couple years ago during the first year of his PhD... Absolutely insane.

readyplayernull 2y ago

> Ron Graham bet him $500 that he could not stop taking the drug for a month. Erdős won the bet, but complained that during his abstinence mathematics had been set back by a month: 'Before, when I looked at a piece of blank paper my mind was filled with ideas. Now all I see is a blank piece of paper.' After he won the bet, he promptly resumed his amphetamine use. http://en.wikipedia.org/wiki/Paul_Erd%C5%91s http://en.wikipedia.org/wiki/Paul_Erd%C5%91s

jiggawatts 2y ago
Perhaps he was self-medicating for ADHD?

lanstin 2y ago

The owner of this website is asking for software help. https://www.erdosproblems.com/help https://www.erdosproblems.com/help

legedemon 2y ago

I clicked on a random open problem and found https://www.erdosproblems.com/170 https://www.erdosproblems.com/170. The text of the problem didn't make sense. The wikipedia article stated the problem much more nicely which was thankfully linked from the OP's website. Wish the problem could be stated more simply on the main site as well. Will certainly try and help the owner of the website.

TFBloom 2y ago
Sorry you found the text confusing; often I have reworded the problem text to give what is, for me, the clearest explanation of the problem. Of course, what the clearest explanation is is very much dependent on one's own background and personal tastes! For example for this problem I think a lot about sumsets and difference sets anyway, so it made sense to phrase it in those terms. If you have a suggestion on how it could be rephrased for clarity then please do email in.