Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids!

 

Milena+Umesh
Milena Mihail and Umesh Vazirani

I thank Nati Linial, Dan Spielman and Karim Adiprasito for telling me about the news.

The Mihail-Vazirani conjecture for matroids and the Feder-Mihail’s theorem

Consider a collection X of n vectors. A basis is a subset of X of linearly independent vectors that span the subspace spanned by X.  We can define a graph whose vertices are all bases and two bases are adjacent if their symmetric difference has two elements. Mihail and Vazirani conjectured that for every set Y of vertices in this graph the number of edges between Y to its complement \bar Y is at least \min (|Y| |,\bar Y|).

If X consists of the elements of the standard basis in \mathbb R^d and their negatives then the graph we obtain is the graph of the discrete n dimensional discrete cube and the assertion of the Mihail-Vazirani conjecture is well known.

The Mihail-Vazirani conjecture was formulated (and have now been proved) for arbitrary matroids. Think about a matroid as a collection K of subsets (the independent sets of the matroid) of some ground set X that closed under taking subsets (hence a simplicial complex) with the following property: For every Y \subset X, the induced simplicial complex on Y denoted by K(Y)  is pure. In other words, for every Y \subset X, all maximal independent subsets of Y have the same cardinality.

In a pioneering 1992 paper Tomás Feder and Milena Mihail proved the conjecture for balanced matroids.

Mihail and Vazirani conjecture for 0-1 polytopes.

An even more general conjecture by Mihail and Vazirani is still open. It asserts that for every 0-1 polytope, for every set Y of vertices, the number of edges between Y to its complement \bar Y is at least \min (|Y|, |\bar Y|).

The new breakthrough

Here is the link to the paper.

Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid by Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant

Let me mention that there was simultaneously another paper by a subset of the authors on related questions, another paper by Brändén and Huh who independently proved the strong log-concavity of several of the polynomials that appear in the ALOV  paper, and there will be several forthcoming papers by these two groups.

Here is the abstract: We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where 0<q<1. Consequently, we can sample random spanning forests in a graph and (approximately) compute the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has expansion at least 1. One of our key observations is a close connection between pure simplicial complexes and multiaffine homogeneous polynomials. Specifically, if X is a pure simplicial complex with positive weights on its maximal faces, we can associate with X a multiaffine homogeneous polynomial p_X such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of p_X.

Spectral negative dependence and Hodge-Riemann

A key paragraph regarding the method is the following:

“Our approach has a close connection to the original plan of Feder and Mihail (1992) who used the negative correlation property of balanced matroids to show that the bases exchange walk mixes rapidly. Unfortunately, most interesting matroids do not satisfy negative correlation. But it was observed [AKH18; HW16; AOV18] that all matroids satisfy a spectral negative dependence property.” AKH18 (a typo, it should be AHK18) is the solution for the Rota-Heron conjecture by Adiprasito, Huh and Katz that relies on the Hodge-Riemann property for matroids that we mentioned in this post. (I still feel in debt for a more detailed blog post about Adiprasito, Huh and Katz’ breakthrough!).”

I think that high dimensional expanders and random walks on them also plays a role in the new development.

 

Advertisements
Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , , , , , | 6 Comments

Igor Pak will give the 2018 Erdős Lectures

 

Next week Igor Pak will give the 2018 Erdős Lectures (delayed from June)

Here is the poster

 

Combinatorics — Erdos lecture: Igor Pak (UCLA) “Counting linear extensions”

Monday December 10  11:00-13:00

Location:  IIAS Hall 130, Feldman building,  Givat Ram

 

 

I will survey various known and recent results on counting the number of linear extensions of finite posets. I will emphasize the asymptotic and complexity aspects for special families, where the problem is especially elegant yet remains #P-complete.

CS Theory — Erdős Lecture: Igor Pak (UCLA) “Counting Young tableaux”

Wednesday, Dec. 12,  2018, 10:30am to 12:00pm

Location: Rothberg (CS building) B-220

The number of standard Young tableaux of skew shape is a mesmerizing special case of the number of linear extensions of posets, that is important for applications in representation theory and algebraic geometry.  In this case there is a determinant formula, but finding their asymptotics is a difficult challenge.  I will survey some of the many beautiful result on the subject, explain some surprising product formulas, connections to Selberg integral, lozenge tilings and certain particle systems.

Colloquium: Erdos lecture – Igor Pak (UCLA) “Counting integer points in polytopes”

Thursday,  Dec 13, 2018 2:30pm to 3:30pm

Location: Manchester Building (Hall 2), Hebrew University Jerusalem

Given a convex polytope P, what is the number of integer points in P? This problem is of great interest in combinatorics and discrete geometry, with many important applications ranging from integer programming to statistics. From a computational point of view it is hopeless in any dimensions, as the knapsack problem is a special case. Perhaps surprisingly, in bounded dimension the problem becomes tractable. How far can one go? Can one count points in projections of P, finite intersections of such projections, etc.?

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , | Leave a comment

PCP fest, Tel Aviv University, 18-20 December 2018

Conference web site

The study of Probabilistically Checkable Proofs, starting with the discovery of the PCP Theorem, is a cornerstone of modern computer science, with impact on complexity theory, algorithms, and cryptography. Born as a purely theoretical notion, mostly used to prove hardness of approximation results, PCPs are now becoming a widely deployed tool in blockchain platforms. The workshop will touch the past, the state of the art, and future of PCPs. Topics will include: hardness of approximation, PCPs in cryptography and blockchains, no-signaling PCPs, PCPs in P, and Boolean function analysis.

Confirmed speakers:

Boaz Barak, Shafi Goldwasser, Eli Ben Sasson, Gil Kalai, Yael Kalai, Guy Kindler, Elchanan Mossel, Christos Papadimitriou, Aviad Rubinstein, Ran Raz, Ronitt Rubinfeld, Oded Schwartz, Irit Dinur, Andrew Yao, and Avi Wigderson.

Organizers:

Nir Bitansky, Esty Kelman, Subhash Khot, Dor Minzer, and Muli Safra

Posted in Combinatorics, Computer Science and Optimization, Conferences, Updates | Tagged | Leave a comment

Exciting Beginning-of-the-Year Activities and Seminars.

Let me mention two talks with very promising news by friends of the blog, Karim Adiprasito and Noam Lifshitz. As always, with the beginning of the academic year there are a lot of exciting activities,  things are rather hectic around,  and I hear a lot of exciting things (both news and things I was supposed to know long ago). I am quite sure that we will return to the topics of the two lectures in later posts and I also welcome discussing them in the comment section. (A few related older posts for Karim’s talk and seminar: F ≤ 4E;  Beyond the g-conjecture.   and for Noam’s seminar: Influence, Threshold and NoiseBoolean functions: Influence, threshold and noise;  .)

Karim Adiprasito’s colloquium talks and course

HUJI Thu, 25/10/2018 – 14:30 to 15:30; TAU 29/10/2018 12:15-13:15

Combinatorics, topology and the standard conjectures beyond positivity

Abstract: Consider a simplicial complex that allows for an embedding into \mathbb R^d. How many faces of dimension d/2 or higher can it have? How dense can they be? This basic question goes back to Descartes. Using it and other rather fundamental combinatorial problems, I will motivate and introduce a version of Grothendieck’s “standard conjectures” beyond positivity (which will be explored in detail in the Sunday Seminar). All notions used will be explained in the talk (I will make an effort to be very elementary)

Sunday’s seminar refer to a HUJI Kazhdan seminar given by Karim on this topic. (3-5 Ross building’s seminar room.)  This is a good opportunity to congratulate Karim Adiprasito and June Huh on receiving the New Horizon Prize, and congratulations also to Vincent Lafforgue who received the breakthrough prize and to all the other winners!

Noam Lifshitz’ combinatorics seminar

When: Monday Oct.29, 11:00–12:45
Where: Rothberg CS building, room B500, Safra campus, Givat Ram

Sharp thresholds for sparse functions with applications to extremal combinatorics. (based on a joint work by Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.)

Abstract:
The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function f to satisfy\mu_p(f)=o(\mu_q(f)), where q = p + o(p), and \mu_p(f) is the probability that f=1 on an input with independent coordinates, each taking the value 1 with probability p.

The dense regime, where \mu_p(f)=\Theta(1), is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where \mu_p(f)=o(1) was out of reach of the available methods. However, the potential power of the sparse regime was suggested by Kahn and Kalai already in 2006.

In this talk we show that if a monotone Boolean function f with \mu_p(f)=o(1) satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval [p,q], with q = p+o(p). More specifically, our mild pseudo-randomness hypothesis is that the p-biased measure of f does not bump up to Θ(1) whenever we restrict f to a sub-cube of constant co-dimension, and our conclusion is that we can find q=p+o(p), such that \mu_p(f)=o(\mu_q(f)).

At its core, this theorem stems from a novel hypercontactive theorem for Boolean functions satisfying pseudorandom conditions, which we call `small generalized influences’. This result takes on the role of the usual hypercontractivity theorem, but is significantly more effective in the regime where p = o(1).

We demonstrate the power of our sharp threshold result by reproving the recent breakthrough result of Frankl on the celebrated Erdos matching conjecture, and by proving conjectures of Huang–Loh–Sudakov and Furedi–Jiang for a new wide range of the parameters.

Alef: Koebe’s Karnaf

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

Aleph’s Corner: T-Shirts

The artist behind Aleph’s corner has now a website offering over 100 T-shirt designs. In addition to a few pictures related to  mathematics there are many in a few other categories: “Jazz,” “Urban,” “Nature,” “Signature design,” and “Sea”. Here are a few of my favorites

 

picaboo

 

 

C*

Continue reading

Posted in Art, Combinatorics | Tagged | Leave a comment

ICM 2018 Rio (3) – Coifman, Goldstein, Kronheimer and Mrowka, and the Four Color Theorem

This post is my third report from ICM 2018. You may remember that I had planned to live-blog on the last four days of the congress but on Monday evening I realized that this was an unrealistic task and decided instead to blog only on a single day – Monday. A little later I realized this was also unrealistic and decided to limit my blogging to a single  lecture  by Peter Kronheimer and Tomasz Mrowka on Knots, three-manifolds and instantons.  But in the end I did not live-blog at all and in this post I will briefly described Tuesday’s morning lectures and give a belated report on Peter and Tomasz’s lecture. I actually arrived in Rio very early  on Saturday morning and attended many talks on Saturday, but  this was not part of my planned blogging  and I was relaxed and did not take lecture notes. Sunday was a day off and I had a great time with friends.

I greatly enjoyed all of Monday’s morning lectures. The first very inspiring lecture by my friend and colleague Rafi (Ronald) Coifman was entitled Harmonic analytic geometry in high dimensions – Empirical models (click for the video). Rafi’s research spans across a wide range of areas many of which he himself created and goes from the very applied (e.g., applications of harmonic analysis to pluming, biology, and finance) to the very pure (e.g., applications of wavelets to classical problems in harmonic analysis). The lecture covered a lot of ground, starting with Fourier’s original ideas and his perception that he had discovered the “language of nature” and continuing  with wide applications to structural and multi-scale analysis of high dimensional data, and to the possibility, pushing Fourier’s vision one step further,  of automatically learning the laws of physics from data.

Toward the third lecture on the history of mathematics by Catherine Goldstein I thought that I could relax and listen to a historical lecture that does not require much mathematical efforts. To my surprise, it was very demanding for me (but fully worth the effort) to follow the mathematics itself.  The historical discussion and insights were great. The title of the lecture was Long-term history and ephemeral configurations  (click for the video) and it started with a famous quote of Poincaré: Mathematics is the art of giving the same name to different things (Poincaré gave the examples of “groups” and “uniform convergence”.)  At the center of the talk was Charles Hermite and the lecture dealt, among other things,  with the very interesting question: Is mathematics a natural science? For Hermite the answer was: Yes! Altogether there were a lot of great insights and great lines. (Pictures from these two lectures at the end of the post.)

Kronheimer and Mrowka: Knots, three-manifolds and instantons

Knots, three manifolds and instantons

The talk was fantastic, it had great results, the slides were great, the presentation was great, thoughtful, with a lot of food for thought, both for the large audience and (I think) also for experts. A main famous theorem by the speakers is:

Theorem: Knots with vanishing Instanton Floer homology and (therefore) also knots with trivial Khovanov’s homology are unknots.

Khovanov’s homology are invariants of groups that refine the famous Jones polynomials and, of course, two problems naturally arise. First, is it the case that the Jones polynomial itself determines unknots? (This is a famous open problem.) And also does Khovanov’s homology or Floer’s homology distinguish different knots? (Maybe the answer for the second bold question is known to be negative…)  The lecture had four parts

Part I (Tomasz): knots, Papakyriakopoulos, and the main theorem.

I was surprised that I had the feeling that I understood everything in the first part. It started with a quick pictorial introduction to what knots are, then looking at the complement of a knot, followed by Dehn’s lemma that was proved by Papakyriakopoulos. (I think but am not sure that Papakyriakopoulos’s proof is still needed for all the stronger results that follow.)

  

So Papakyriakopoulos’ theorem tells you that the fundamental group of the complement of a non-trivial knot is not Abelian, but could we say something stronger? Peter mentioned that for most, but not all non-trivial small knots  the fundamental group maps onto a dihedral group. And the main result is that for all non trivial knots the fundamental group maps onto SO (3). There were two delicate yet important points that were mentioned.  The first is that often SO(3) can or should be replaced by its double cover SU(2), and the second is that there is also a crucial condition (that makes the theorem stronger) about the images of “meridians” (small circles around a point on the knot in its complement).

Part II (Peter): Floer’s instanton homology and many mathematical ideas and tools

The second part was about ideas, notions and tools needed for the proof of the main theorem. Naturally it was more difficult and for various things I only just pleasantly got a general impression together with some pointers on notions that I should (finally) learn. Connections, flat connections, Chern-Simons functionals, Young-Mills equations and their solutions called “instantons”, and the Floer’s (instanton) homology, …  .  As you can see from the fourth slide the list of tools that are actually needed for the proof extends even further and Peter and Tomasz also mentioned connections with Ozsváth and Szabo theory of Heegard Floer homology.

 

 

Part III (Tomasz): Khovanov homology, and skein relations

Surprisingly, the third part dealt with notions that were somewhat easier for me than those of the second part. The Khovanov homology is a refinement of another famous knot-invariant the  Jones polynomial.

  

I remember hearing a few talks about Khovanov homology in the early 2000. Dror Bar Nathan showed how they appear very naturally and how it is a straight forward matter to compute them (alas, not efficiently). In a different talk some years later David Kazhdan showed how, taking a different point of view, those invariants depend on a sequence of amazing miracles.   In any case, the Khovanov homology groups are finite dimensional and the Jones polynomial are just the alternating sums of their dimensions (or Euler characteristics). Like the Jones polynomial themselves there is also some connection (“skein relations“) between the Khovanov homologies of knots when you apply two simple operations on the knots.

 

The skein relations for Khovanov homology are given in terms of a long exact sequence, and similar relations hold for the Floer homology. Moreover there is some relation (a spectral sequence) between these two exact sequences which shows that when Khovanov homology  is not trivial then  Floer (instanton) homology is also non trivial and hence from what we already know about Floer homology the knot is not trivial.

and when part IV came I expected that the discussion will be aimed at real experts in the audience and that I could relax and think about other things. However this was not the case. Below the fold I will tell you about the surprising fourth part, and then proceed to talk about various other really interesting things. Statistics tell me that only about a third of the readers read below the fold but this time I truly recommend it.

Continue reading

Posted in Combinatorics, Geometry, ICM2018 | Tagged , , , | 2 Comments

Ricky and Branko

Two dear friends, and great geometers, Ricky Pollack and Branko Grünbaum  passed away a few weeks ago. Ricky was a close friend that both Mazi my wife and I loved, and we were both fascinated by his wisdom, charm and love of life. Branko was my academic grand father and I met him through his writings many years before I had the privilege and pleasure to meet in person.  Here are some pictures of Ricky and Branko. (If you have more, send me and I will add them.)

In future posts I will tell you a little about their mathematics. See also these posts about stories and math related to Ricky ( A Discrepancy Problem for Planar Configurations;  Many triangulated three-spheres!; Academic Degrees and Sex; GLL: Polls and prediction and P=NP . ) and to Branko ( My Copy of Branko Grünbaum’s Convex Polytopes; The World of Michael Burt: When Architecture, Mathematics, and Art meet; Coloring Simple Polytopes and Triangulations; Budapest, Seattle, New Haven ; How the g-Conjecture Came About; GLL: What are proofs for , anyway.) (Links for blog posts on other blogs are welcome.)

 

    

 

Branko with Janos Pach

The legendary mathematical partnership and friendship of Ricky and Eli Goodman is rare in mathematics.

Five generations in Seattle: Branko was the advisor of Micha A Perles (and also of Joram Lindenstrauss, Moshe Rosenfeld, Joseph Zaks and many others). Micha was my advisor (and also of  Meir Katchalski, Michael Kallay, Nati Linial Noga Alon and many others). Isabella Novik was my student and here we are with four student of Isabella: Michael Goff,  Kurt Luoto,  Andy Frohmaderand, and Steven Klee. (From left to right.)

 

Saugata Basu, Ricky Pollack and  Marie-Francois Roy’s  book Algorithms in real algebraic geometry.

   

Posted in Combinatorics, Convexity, Geometry, Obituary | Tagged , | 3 Comments

Video of my ICM2018 lecture: Noise Stability, Noise Sensitivity, and the Quantum Computer Puzzle

The Video of my ICM2018 lecture is now on the air

Here are the (slightly improved) slides.

I made the mistake of trying to improve my slides in the evening before the lecture and in the morning I discovered that the file disappeared (of course, after the lecture it reappeared) and I had to reconstruct it from an earlier version.

And here is the playlist of all plenary lectures:

 

Posted in Combinatorics, Computer Science and Optimization, ICM2018, Quantum, Updates | Tagged | Leave a comment

Alef’s Corner: Garbanzo Poisson process

Alef’s previous corner: There is still a small gap in the proof.

 

Posted in Art, What is Mathematics | Tagged | Leave a comment

ICM2018: Closing Ceremonies

With Peter Sarnak, Stas Smirnov, and Tadashi Tokieda at  Sugar Loaf (Pão de Açúcar), Rio.

At Sugar Loaf with Stas and Edward Dunne

This is my second report from ICM 2018. Some acronyms are used in this post. ICM = International Congress of Mathematicians; IMU = International Mathematical Union, an organization running the ICMs’ GA = General assembly (of the IMU) a body of representatives from the member countries of the IMU.

And a special bonus at the end of the post: Test your intuition question.

Here is a post from the ICM 2018 web-site about my lecture: Kalai plenary ponders possibilities of quantum computing. And here is the link to the ICM 2018 site itself.

Standing ovation to Ali Nesin, Sevan Nişanyan and the Mathematics Village

The IMU Leelavati Prize is an award for outstanding contribution to public outreach in mathematics. Unlike most prizes “Leelavati” is not a name of a person (a man in most cases) but rather the name of  12th-century Indian mathematical treatise. The story of this year’s laureate, the Turkish mathematicians Ali Nesin and Sevan Nişanyan who built together a mathematical village to educate and advance children, is moving and quite amazing.

A rare standing ovation for Nasin, and Nişanyan

 Nesin (left) and Nişanyan

Atiya,  Nesin, and Nişanyan

A few words on the choice between Saint Petersburg and Paris

 

Some members of the Russian delegation after Saint Petersburg was announced as the winner (left), Stas Smirnov and François Loeser shake hands after the announcement. Both François and Stas were stars of my Hyderabad ICM 2010 reports. (I,II).

Mathematicians love sequences – here is the sequence of cities of post WWII ICMs

Cambridge (MA); Amsterdam, Edinburgh, Stockholm, Moscow, Nice, Vancouver,  Helsinki, Warsaw, Berkeley, Kyoto, Zurich, Berlin, Beijing, Madrid, Hyderabad, Seoul, Rio,…

What is the law governing these choices? All these countries have good mathematics and a few have superb mathematics. Some of these cities represented democratic countries and some did  not, and there are many shades of grey.   The hosting countries also differ in terms of economic systems, human rights, foreign policies and various other things.   If there is an emerging law for the sequence of cities it is that first, except for extreme cases,  it is largely politically blind, and second, that an attempt is made to outreach and make ICMs s truly world wide experience. (The second item also characterizes  other important activities of the IMU.)

This time the choice was between two fantastic cities, Paris and Saint Petersburg. The IMU executive committee had chosen Saint Petersburg,  but this was challenged (for the first time, as far as I know) and at the end the GA democratically voted 83:63 (4 abstentions) for Saint Petersburg. For the full list of resolutions of the GA see this page. My feeling is that also many mathematicians from Russia and the former Soviet Union who live abroad (many also in Israel) were happy with this opportunity of a “mathematical reunion” in 2022. There was one additional GA resolution that caused some controversy that maybe I will mention in a future post.

Anyway, another exciting moment at the closing ceremony was

Andrei and Stas’s invitation to Saint Petersburg

Andrei Okounkov and Stas Smirnov came with matching casual clothes and declared that this was because it was time for them to start working.  I first met Andrei and Stas in Saint Petersburg in a 2004 conference celebrating Anatoly (Tolya) Vershik’s 70th birthday. (Here is a link to Vershik’s amazing home page.) (Picture: ICM 2018 site)

 

Test your intuition

The Guardian (yesterday) 

A TYI question with an answer (below the fold)

With the landmark decision (Thursday, yesterday) of the Indian supreme court, homosexual sexual activity is now legal in every country that ever hosted the ICM.

Test your intuition: When was homosexual  sexual activity nationally legalized first, and by how many years,  in Brazil or in the US.?  (Answer, below the fold.)

Shana Tova Umetuka (Good and Sweet  New Jewish Year) to all our readers.

Continue reading

Posted in Conferences, ICM2018, Updates | Tagged , , , | 6 Comments