Category Archives: Combinatorics

The story of Poincaré and his friend the baker

Posted on October 13, 2019 by

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

Posted on October 13, 2019 by

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

Posted on September 23, 2019 by

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.

Posted on September 22, 2019 by

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

Posted on September 17, 2019 by

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!

Posted on September 9, 2019 by

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

Posted on September 1, 2019 by

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

Posted on August 23, 2019 by

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

Posted on August 19, 2019 by

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

Posted on August 4, 2019 by

  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