To cheer you up in difficult times II: Mysterious matching news by Gal Beniamini, Naom Nisan, Vijay Vazirani and Thorben Tröbst!

Matching is one of the richest gold mines for ideas and results in mathematics, computer science and other areas.  Today I want to briefly tell you about a curious, surprising, mysterious, and cheerful recent result by Gal Beniamini and Noam Nisan and a subsequent work of Vijay Vazirani. It is a result that will cheer up combinatorialists on both sides of the aisle: graph theorists and researchers in extremal and probabilistic combinatorics as well as algebraic and enumerative combinatorialists.  (And it is related to query complexity, Eulerian lattices, Birkhoff’s polytope, a theorem of Lou Billera and Aravamuthan Sarangarajan, evasiveness, analysis of Boolean functions, and various other things.) At the end of the post I will remind you of a central problem in matching theory: that of extending Lovasz’ randomized algorithm for matching to general graphs. (Perhaps methods from algebraic combinatorics can help.)

I will start with sad news. John Horton Conway, an amazing mathematical hero,  passed away a few days ago. There are very nice posts on Conway’s work by Scott Aaronson (with many nice memories in the comments section), by Terry Tao, and by Dick Lipton and Ken Regan. And a moving obituary on xkcd with a touch of ingenuity of Conway’s style. (There is also a question on MO  “Conway’s less known results,” and two questions on the game of life (I, II).)

Another reading material to cheer you up is my paper: The argument against quantum computers, the quantum laws of nature, and Google’s supremacy claims. It is for Laws, Rigidity and Dynamics, Proceedings of the ICA workshops 2018 & 2019 in Singapore and Birmingham. Remarks are most welcome. (Update (May, 25 2020): An interesting discussion on Hacker news.)

Update: starting today, the algebraic combinatorics online workshop.  Here is the schedule for the first week, and for the second week.


Matching theory by Lovasz and Plummer is probably one of the best mathematics books ever written. 

Bipartite Perfect Matching as a Real Polynomial

Bipartite Perfect Matching as a Real Polynomial, by Gal Beniamini and Noam Nisan

Abstract: We obtain a description of the Bipartite Perfect Matching decision problem as a multilinear polynomial over the Reals. We show that it has full degree and (1-o_n(1))\cdot 2^{n^2}  monomials with non-zero coefficients. In contrast, we show that in the dual representation (switching the roles of 0 and 1) the number of monomials is only exponential in \Theta(n \log n)  Our proof relies heavily on the fact that the lattice of graphs which are “matching-covered” is Eulerian.

And here is how the paper starts

Every Boolean function f:\{0,1\}^n\to\{0,1\} can be represented in a unique way as a Real multilinear polynomial. This representation and related ones (e.g. using the {1,−1} basis rather than {0,1}– the “Fourier transform” over the hypercube, or approximation variants) have many applications for various complexity and algorithmic purposes. See, e.g., [O’D14] for a recent textbook. In this paper we derive the representation of the bipartite-perfect-matching decision problem as a Real polynomial.

Definition. The Boolean function BPM_n(x_{1,1},\dots,x_{n,n}) is defined to be 1 if and only if the bipartite graph whose edges are\{(i,j):x_{i,j}=1\} has a perfect matching, and 0 otherwise.

And here are the two main theorems regarding this polynomial and the polynomial for the dual representation:

(For the second theorem you need the notion of totally ordered bipartite graphs.)

And here is a nice picture!

A very interesting open problem is:

Problem: Can the Beniamini-Nisan results be extended to general (non-bipartite) graphs

This reminds me of an old great problem:

Problem: Does Lovasz’ randomized algorithm for matching extend to the non-bipartite case?

For both problems methods of algebraic combinatorics may be helpful.

An Extension by Vijay Vazirani and Thorben Tröbst

A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings, Thorben Tröbst, Vijay V. Vazirani


In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph G \subset K_{n,n} has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function w on the edges of K_{n,n}, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph G \subset K_{n,n} contains one of these minimum weight perfect matchings.

Three more remarks about VVV

Three more VVV remarks: in the Tel Aviv theory fast fest three months ago (it seems like ages ago) Vijay Vazirani gave a lecture about matching. Here is the link to Vijay’s lecture, and to all plenary lectures.  At the end, I asked him how he explains that matching theory is such inexhaustable gold mine and Vijay mentioned the fact that a polynomial-time algorithm for the assignment problem (which is closely related to matching) was already found by Jacobi in 1890. (Unfortunately VJ’s inspiring answer was not recorded). A few years ago Vijay published a simplified proof of a fantastic famous result he first proved with Silvio Micaly 34 years earlier. And here is a most amazing story: a few years ago I went to the beach in Tel Aviv and I discovered Vijay swimming just next to me.  We were quite happy to see each other and Vijay told me a few things about matching, economics and biology. This sounds now like a truly surrealistic story, and perhaps we even shook hands.




This entry was posted in Combinatorics, Computer Science and Optimization and tagged , , , . Bookmark the permalink.

10 Responses to To cheer you up in difficult times II: Mysterious matching news by Gal Beniamini, Naom Nisan, Vijay Vazirani and Thorben Tröbst!

  1. Hi Gil,

    I was thrilled to see that you liked these two papers on real polynomials for matching! For me, the Beniamini-Nisan paper is one of my favorites and it was pure joy to work on these ideas! Two of the three topics I mentioned in our waist-deep sea-meeting in Tel Aviv have come together in my recent work (the third is really my minor suit, even though it excites me every time I see one of its unbelievable revelations about life):

    Click to access 2004.01348.pdf

    Hope you like this one too!


    • Vijay Vazirani says:

      Erratum: VJV –> VVV

      GK: Edited. What the middle V. stands for?

    • Gil Kalai says:

      Dear Vijay, great to see you here! Right, I like this one very much as well. And in general the trinity of matching in combinatorics – matching in economics – matching in theoretical computer science. And right, waist-deep dipping is probably more precise than “swimming,” and as Yuval Rabani mentioned to me, the “Theory fast” was actually a “theory fest”.

  2. Gil Kalai says:

    Usually, what I write and say is what I mean subject to some huge (Z/2)^m group. So a plus, sign is often a minus sign, lower bound is often upper bound, “large” can be “small”, its and it’s are replaceable (and “were” and “where” etc.). This was all rather benign but it turns out that replacing “mute” and “unmute” in Zoom is more problematic.

  3. Vijay Vazirani says:

    I hope in these times of total boredom, when you say “theory fast” you mean we are doing theory faster than before and not that we are fasting on doing theory 😉

    I find that I am cracking more jokes than usual …
    I hope that is not an indication of any other things cracking 🙂

    PS: You don’t seem to allow emojis, so I had to improvise …

  4. Pingback: To cheer you up in difficult times II: Mysterious matching news by Gal Beniamini, Naom Nisan, Vijay Vazirani and Thorben Tröbst! — Combinatorics and more – jair2018

  5. Pingback: Gil’s Collegial Quantum Supremacy Skepticism FAQ | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s