Category Archives: Combinatorics

Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture

Borsuk asked in 1933 if every bounded set K of diameter 1 in can be covered by d+1 sets of smaller diameter. A positive answer was referred to as the “Borsuk Conjecture,” and it was disproved by Jeff Kahn and me in 1993. … Continue reading

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

Analysis of Boolean Functions – week 1

Home page of the course. In the first lecture I defined the discrete n-dimensional cube and  Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets. 1) The largest possible intersecting family … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Teaching | Tagged , , , | 1 Comment

Poznań: Random Structures and Algorithms 2013

   Michal Karonski (left) who built Poland’s probabilistic combinatorics group at Poznań, and a sculpture honoring the Polish mathematicians who first broke the Enigma machine (right, with David Conlon, picture taken by Jacob Fox). I am visiting now Poznań for the 16th … Continue reading

Posted in Combinatorics, Conferences, Open problems, Philosophy, Probability | Tagged , | Leave a comment

Lawler-Kozdron-Richards-Stroock’s combined Proof for the Matrix-Tree theorem and Wilson’s Theorem

   David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics” A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchho ff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading

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

Some old and new problems in combinatorics and geometry

Paul Erdős in Jerusalem, 1933  1993 I just came back from a great Erdős Centennial conference in wonderful Budapest. I gave a lecture on old and new problems (mainly) in combinatorics and geometry (here are the slides), where I presented twenty … Continue reading

Posted in Combinatorics, Geometry, Open problems | Tagged | 4 Comments

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

Posted in Combinatorics, Geometry, Open problems | Tagged , , , , | 2 Comments

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

Posted in Algebra and Number Theory, Combinatorics, Obituary | Tagged | 5 Comments

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

Posted in Combinatorics, Games, Probability, Test your intuition | Tagged , , , , , , | 7 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

Posted in Combinatorics | Tagged | 3 Comments