Recent Comments

Recent Posts
 Hardness of Approximating Vertex Cover, PolytopeIntegralityGap, the AlswedeKachatrian theorem, and More.
 Jacob Fox, David Conlon, and Benny Sudakov: Vast Improvement of our Knowledge on Unavoidable Patterns in Words
 Subhash Khot, Dor Minzer and Muli Safra proved the 2to2 Games Conjecture
 Interesting Times in Mathematics: Enumeration Without Numbers, Group Theory Without Groups.
 Cody Murray and Ryan Williams’ new ACC breakthrough: Updates from Oded Goldreich’s Choices
 Yael Tauman Kalai’s ICM2018 Paper, My Paper, and Cryptography
 Ilan Karpas: Frankl’s Conjecture for Large Families
 Third third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome
 Second third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome
Top Posts & Pages
 Hardness of Approximating Vertex Cover, PolytopeIntegralityGap, the AlswedeKachatrian theorem, and More.
 Subhash Khot, Dor Minzer and Muli Safra proved the 2to2 Games Conjecture
 New Isoperimetric Results for Testing Monotonicity
 Jacob Fox, David Conlon, and Benny Sudakov: Vast Improvement of our Knowledge on Unavoidable Patterns in Words
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Can Category Theory Serve as the Foundation of Mathematics?
 Believing that the Earth is Round When it Matters
 TYI 30: Expected number of Dice throws
 My Book: "Gina Says," Adventures in the Blogosphere String War
RSS
Search Results for: erdos
Micha Perles’ Geometric Proof of the ErdosSos Conjecture for Caterpillars
A geometric graph is a set of points in the plane (vertices) and a set of line segments between certain pairs of points (edges). A geometric graph is simple if the intersection of two edges is empty or a vertex … Continue reading
Jozsef Solymosi is Giving the 2017 Erdős Lectures in Discrete Mathematics and Theoretical Computer Science
May 4 2:303:30; May 7 11:0013:00; May 10 10:3012:00 See the event webpage for titles and abstracts (or click on the picture below).
Polymath 10 post 6: The ErdosRado sunflower conjecture, and the Turan (4,3) problem: homological approaches.
In earlier posts I proposed a homological approach to the ErdosRado sunflower conjecture. I will describe again this approach in the second part of this post. Of course, discussion of other avenues for the study of the conjecture are welcome. The purpose … Continue reading
Polymath 10 Emergency Post 5: The ErdosSzemeredi Sunflower Conjecture is Now Proven.
While slowly writing Post 5 (now planned to be Post 6) of our polymath10 project on the ErdosRado sunflower conjecture, the very recent proof (see this post) that cap sets have exponentially small density has changed matters greatly! It implies … Continue reading
Polymath10: The Erdos Rado Delta System Conjecture
The purpose of this post is to start the polymath10 project. It is one of the nine projects (project 3d) proposed by Tim Gowers in his post “possible future polymath projects”. The plan is to attack ErdosRado delta system conjecture also known as the … Continue reading
Posted in Combinatorics, Polymath10
Tagged Alexandr Kostochka, Joel Spencer, Paul Erdos, Richard Rado
140 Comments
Erdős’ Birthday
Paul Erdős was born on March 26, 1913 2013 a hundred years ago. This picture (from Ehud Friedgut’s homepage) was taken in September ’96 in a Chinese restaurant in Warsaw, a few days before Paul Erdős passed away. The other diners are Svante Janson, Tomasz Łuczack and … Continue reading
János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem
Click here for the most recent polymath3 research thread. Erdős and Pach celebrating another November day many years ago. The Wolf disguised as Little Red Riding Hood. Pach disguised as another Pach. This post is authored by János Pach A … Continue reading
Posted in Combinatorics, Geometry, Guest blogger, Open problems
Tagged Larry Guth, Nets Hawk Katz
13 Comments
Hardness of Approximating Vertex Cover, PolytopeIntegralityGap, the AlswedeKachatrian theorem, and More.
Lior Silberman asked about applications of the new KhotMinzerSafra 2to2 game theorem to hardness of approximation, and James Lee answered mentioning applications to vertex cover. Let me elaborate a little on vertex cover, and other matters. (Here is the pervious … Continue reading
Preview: The solution by Keller and Lifshitz to several open problems in extremal combinatorics
Peter Frankl (right) and Zoltan Furedi The news A new paper by Nathan Keller and Noam Lifshitz settles several open problems in extremal combinatorics for wide range of parameters. Those include the three problems we mention next. Three central open … Continue reading
Posted in Combinatorics, Open problems, Updates
Tagged David Ellis, Ehud Friedgut, Michel Deza, Nathan Keller, Noam Lifshitz, Paul Erdos, Peter Frankl, Zoltán Füredi
1 Comment