Category Archives: Combinatorics

The story of Poincaré and his friend the baker

Google’s supremacy stone soup Here is a little update on the Google supremacy claims that we discussed in this earlier post (see especially this remark). Don’t miss our previous post on combinatorics. Recall that a quantum supremacy demonstration would be … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability, Quantum, Statistics | Tagged , , | 9 Comments

Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures

Gérard Cornuéjols Gérard Cornuéjols‘s beautiful (and freely available) book from 2000 Optimization: Packing and Covering is about an important area of combinatorics which is lovely described in the preface to the book The integer programming models known as set packing … Continue reading

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

Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).

A 2017 cartoon from this post. Update (October, 18, 2019): To the best of my judgement the results on quantum supremacy in the Google paper are fundamentally flawed. The researchers apparently calibrated parameters of the quantum computer as to improve … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Quantum, Updates | Tagged | 57 Comments

Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.

Three isoperimetric papers by Michel Talagrand (see the end of the post) Discrete isoperimetric relations are of great interest on their own and today I want to tell you about a new  isoperimetric inequality by Jeff Kahn and Jinyoung Park … Continue reading

Posted in Combinatorics | Tagged , , | 3 Comments

Alef’s corner: Bicycles and the Art of Planar Random Maps

The artist behind Alef’s corner has a few mathematical designs and here are two new ones. (See Alef’s  website offering over 100 T-shirt designs.)   which was used for the official T-shirt for Jean-François Le Gall’s birthday conference. See also … Continue reading

Posted in Art, Combinatorics, Geometry, Probability | Tagged | Leave a comment

Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, and Marius Tiba: Flat polynomials exist!

Béla Bollobás and Paul Erdős at the University of Cambridge in 1990. Credit George Csicsery (from the 1993 film “N is a Number”) (source) (I thank Gady Kozma for telling me about the result.) An old problem from analysis with a … Continue reading

Posted in Analysis, Combinatorics | Tagged , , , , , | 1 Comment

Richard Ehrenborg’s problem on spanning trees in bipartite graphs

Richard Ehrenborg with a polyhedron In the Problem session last Thursday in Oberwolfach, Steve Klee presented a beautiful problem of Richard Ehrenborg regarding the number of spanning trees in bipartite graphs. Let be a bipartite graph with vertices on one … Continue reading

Posted in Combinatorics, Open problems | Tagged | 4 Comments

Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture

WOW! The new paper https://arxiv.org/abs/1908.08483 improved bounds for the sunflower lemma gives the most dramatic progress on the sunflower conjecture since it was asked. Congratulations to Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang. (Written on my smartphone will expand … Continue reading

Posted in Combinatorics, Uncategorized | 6 Comments

Equiangular lines with a fixed angle and other breakthroughs from Yufei Zhao’s blog

Today I would like to report about some breakthroughs in the area of combinatorics, and about blog posts in Yufei Zhao’s blog that describe these remarkable results (better than I can). Many of the coauthors in these breakthroughs are undergraduate … Continue reading

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

Avi Wigderson’s: “Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!” (An invitation for a discussion.)

  The cover of Avi Wigderson’s book “Mathematics and computation” as was first exposed to the public in Avi’s Knuth Prize videotaped lecture. (I had trouble with 3 of the words: What is EGDE L WONK 0?  what is GCAAG?GTAACTC … Continue reading

Posted in Academics, Combinatorics, Computer Science and Optimization, Open discussion, Philosophy, What is Mathematics | Tagged | 16 Comments