### Recent Comments

Muhamed on In And Around Combinatorics: T… Ehud on Ehud Friedgut: Blissful ignora… wvandernoort on Ehud Friedgut: Blissful ignora… Yiftach Barnea on Test your intuition 24: Which… Gil Kalai on Test your intuition 24: Which… Yiftach Barnea on Test your intuition 24: Which… Yiftach Barnea on Test your intuition 24: Which… Gil Kalai on Test your intuition 24: Which… Gil Kalai on Test your intuition 24: Which… Gabor Pete on Test your intuition 24: Which… chun-xuan jiang on Polymath 8 – a Succ… domotorp on Test your intuition 24: Which… -
### Recent Posts

- Test your intuition 24: Which of the following three groups is trivial
- School Starts at HUJI
- A lecture by Noga
- Ehud Friedgut: Blissful ignorance and the Kahneman-Tversky paradox
- In And Around Combinatorics: The 18th Midrasha Mathematicae. Jerusalem, JANUARY 18-31
- Mathematical Gymnastics
- Media Item from “Haaretz” Today: “For the first time ever…”
- Jim Geelen, Bert Gerards, and Geoﬀ Whittle Solved Rota’s Conjecture on Matroids
- Media items on David, Amnon, and Nathan

### Top Posts & Pages

- Test your intuition 24: Which of the following three groups is trivial
- Believing that the Earth is Round When it Matters
- When It Rains It Pours
- Happy Birthday Ron Aharoni!
- A lecture by Noga
- יופיה של המתמטיקה
- János Pach: Guth and Katz's Solution of Erdős's Distinct Distances Problem
- Andriy Bondarenko Showed that Borsuk's Conjecture is False for Dimensions Greater Than 65!
- In how many ways you can chose a committee of three students from a class of ten students?

### RSS

# Search Results for: erdos

## 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 Cap sets, Frankl-Rodl theorem, polymath1
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 Erdos-Ko-Rado theorem, Extremal combinatorics, Permutations
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 Density Hales-Jewett theorem, polymath1
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 Cap sets, Extremal combinatorics, Intersection theorems, polymath1
6 Comments

## Mathematics, Science, and Blogs

Michael Nielsen wrote a lovely essay entitled “Doing science online” about mathematics, science, and blogs. Michael’s primary example is a post over Terry Tao’s blog about the Navier-Stokes equation and he suggests blogs as a way of scaling up scientific conversation. Michael is writing … Continue reading

Posted in Blogging, What is Mathematics
Tagged Blogs, Michael Nielsen, Open science, polymath1, Tim Gowers
5 Comments

## Lior, Aryeh, and Michael

Three dear friends, colleagues, and teachers Lior Tzafriri, Aryeh Dvoretzky and Michael Maschler passed away last year. I want to tell you a little about their mathematics. Lior Tzafriri ( 1936-2008 ) Lior Tzafriri worked in functional analysis.

## Extremal Combinatorics IV: Shifting

Compression We describe now a nice proof technique called “shifting” or “compression” and mention a few more problems. The Sauer-Shelah Lemma: Let . Recall that a family shatters a set if for every there is such that … Continue reading

## Extremal Combinatorics III: Some Basic Theorems

. Shattering Let us return to extremal problems for families of sets and describe several basic theorems and basic open problems. In the next part we will discuss a nice proof technique called “shifting” or “compression.” The Sauer-Shelah (-Perles -Vapnik-Chervonenkis) Lemma: (Here we write .) … Continue reading

## Pushing Behrend Around

Erdos and Turan asked in 1936: What is the largest subset of {1,2,…,n} without a 3-term arithmetic progression? In 1946 Behrend found an example with Now, sixty years later, Michael Elkin pushed the the factor from the denominator to the enumerator, … Continue reading

Posted in Combinatorics, Updates
Tagged Arithmetic progressions, Roth's theorem, Szemeredi's theorem
10 Comments

## Extremal Combinatorics I: Extremal Problems on Set Systems

The “basic notion seminar” is an initiative of David Kazhdan who joined HU math department around 2000. People give series of lectures about basic mathematics (or not so basic at times). Usually, speakers do not talk about their own research and not even … Continue reading