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   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   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 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 is defined to be 1 if and only if the bipartite graph whose edges are 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

Abstract:

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 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 , consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph 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.