Search Results for: erdos

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 , | 13 Comments

Polymath Reflections

Polymath is a collective open way of doing mathematics. It  started over Gowers’s blog with the polymath1 project that was devoted to the Density Hales Jewett problem. Since then we  had Polymath2 related to Tsirelson spaces in Banach space theory , an  intensive Polymath4 devoted … Continue reading

Posted in Mathematics over the Internet, Open discussion | 2 Comments

A Discrepancy Problem for Planar Configurations

Yaacov Kupitz and Micha A. Perles asked: What is the smallest number C such that for every configuration of n points in the plane there is a line containing two or more points from the configuration for which the difference between the … Continue reading

Posted in Combinatorics | Tagged , | Leave a comment

Polymath5 – Is 2 logarithmic in 1124?

 Polymath5 – The Erdős discrepancy problem – is on its way. Update: Gowers’s theoretical post marking the official start of Polymath 5 appeared. Update (February 2014): Boris Konev and Alexei Lisitsa found a sequence of length 1160 of discrepancy 2 … Continue reading

Posted in Mathematics over the Internet | Tagged | 2 Comments

Four Derandomization Problems

Polymath4 is devoted to a question about derandomization: To find a deterministic polynomial time algorithm for finding a k-digit prime.  So I (belatedly) devote this post to derandomization and, in particular, the following four problems. 1) Find a deterministic algorithm for primality 2) Find … Continue reading

Posted in Computer Science and Optimization, Probability | Tagged , , | 4 Comments

Vitali Fest

Last week I took part in a lovely and impressive conference on the state of geometry and functional analysis, celebrating Vitali Milman’s 70th birthday. The conference started in Tel Aviv, continued at the Dead Sea, and returned to Tel Aviv. I gave a … Continue reading

Posted in Conferences | 5 Comments

The Cap-Set Problem and Frankl-Rodl Theorem (C)

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here … Continue reading

Posted in Combinatorics, Open problems | Tagged , , | Leave a comment

Extremal Combinatorics on Permutations

  We talked about extremal problems for set systems: collections of subsets of an element sets, - Sperner’s theorem, the Erdos-Ko-Rado theorem, and quite a few more. (See here, here and here.) What happens when we consider collections of permutations rather … Continue reading

Posted in Combinatorics | Tagged , , | 9 Comments

Polymath1: Success!

 “polymath” based on internet image search And here is a link to the current draft of the paper. Update:  March 26, the name of the post originally entitled “Polymath1: Probable Success!” was now updated to “Polymath1: Success!” It is now becoming … Continue reading

Posted in Blogging, Combinatorics, What is Mathematics | Tagged , | 10 Comments

Frankl-Rodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A)

Voita Rodl I would like to tell you about a research project in progress with Roy Meshulam. (We started it in the summer, but then moved to other things;  so far there are interesting insights, and perhaps problems, but not substantial … Continue reading

Posted in Combinatorics, Open problems | Tagged , , , | 6 Comments