### Recent Comments

domotorp on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Thanks for Additivit… on The Kadison-Singer Conjecture… domotorp on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… domotorp on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Gil Kalai on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… -
### Recent Posts

- Polymath10, Post 2: Homological Approach
- Polymath10: The Erdos Rado Delta System Conjecture
- Convex Polytopes: Seperation, Expansion, Chordality, and Approximations of Smooth Bodies
- Igor Pak’s collection of combinatorics videos
- EDP Reflections and Celebrations
- Séminaire N. Bourbaki – Designs Exist (after Peter Keevash) – the paper
- Important formulas in Combinatorics
- Updates and plans III.
- NogaFest, NogaFormulas, and Amazing Cash Prizes

### Top Posts & Pages

- The Kadison-Singer Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
- Polymath10, Post 2: Homological Approach
- Polymath10: The Erdos Rado Delta System Conjecture
- New Ramanujan Graphs!
- The Mystery Piano-Player at the Mittag-Leffler Institute
- 'Gina Says'
- Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
- Extremal Combinatorics III: Some Basic Theorems
- Why Quantum Computers Cannot Work: The Movie!

### RSS

# Category Archives: Combinatorics

## Andriy Bondarenko Showed that Borsuk’s Conjecture is False for Dimensions Greater Than 65!

The news in brief Andriy V. Bondarenko proved in his remarkable paper The Borsuk Conjecture for two-distance sets that the Borsuk’s conjecture is false for all dimensions greater than 65. This is a substantial improvement of the earlier record (all dimensions … Continue reading

## New Ramanujan Graphs!

Margulis’ paper Ramanujan graphs were constructed independently by Margulis and by Lubotzky, Philips and Sarnak (who also coined the name). The picture above shows Margulis’ paper where the graphs are defined and their girth is studied. (I will come back to the question … Continue reading

Posted in Algebra and Number Theory, Combinatorics, Open problems
Tagged Ramanujan graphs
10 Comments

## Andrei

Andrei Zelevinsky passed away a week ago on April 10, 2013, shortly after turning sixty. Andrei was a great mathematician and a great person. I first met him in a combinatorics conference in Stockholm 1989. This was the first major … Continue reading

## Test Your Intuition (19): The Advantage of the Proposers in the Stable Matching Algorithm

Stable mariage The Gale-Shapley stable matching theorem and the algorithm. GALE-SHAPLEY THEOREM Consider a society of n men and n women and suppose that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then … Continue reading

## 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

## Lionel Pournin found a combinatorial proof for Sleator-Tarjan-Thurston diameter result

I just saw in Claire Mathieu’s blog “A CS professor blog” that a simple proof of the Sleator-Tarjan-Thurston’s diameter result for the graph of the associahedron was found by Lionel Pournin! Here are slides of his lecture “The diameters of associahedra” … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Convex polytopes
Tagged Associahedron, Lionel Pournin
1 Comment

## Happy Birthday Ron Aharoni!

Ron Aharoni, one of Israel’s and the world’s leading combinatorialists celebrated his birthday last month. This is a wonderful opportunity to tell you about a few of the things that Ron did mainly around matching theory. Menger’s theorem for infinite … Continue reading

## The Quantum Debate is Over! (and other Updates)

Quid est noster computationis mundus? Nine months after is started, (much longer than expected,) and after eight posts on GLL, (much more than planned,) and almost a thousand comments of overall good quality, from quite a few participants, my … Continue reading

## Looking Again at Erdős’ Discrepancy Problem

Over Gowers’s blog Tim and I will make an attempt to revisit polymath5. Last Autumn I prepared three posts on the problems and we decided to launch them now. The first post is here. Here is a related MathOverflow question. … Continue reading