To cheer you up in difficult times 9: Alexey Pokrovskiy proved that Rota’s Basis Conjecture holds asymptotically

Pokrovskiy’s startling morning  rainbow

Rota’s Basis Conjecture holds asymptotically, by Alexey Pokrovskiy

Abstract: Rota’s Basis Conjecture is a well known problem from matroid theory, that states that for any collection of n bases in a rank n matroid, it is possible to decompose all the elements into n disjoint rainbow bases. Here an asymptotic version of this is proved. We show that it is possible to find n − o(n) disjoint rainbow independent sets of size n − o(n).

A rainbow basis is a basis with one element from each collection.

(I thank Nati Linial for telling me about it.)

Another way to formulate Rota’s basis conjecture (for representable matroids) is that if B1B2, …, Bn are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n × n grid of vectors (vij) such that

1. the n vectors in row i are the members of the ith basis Bi (in some order), and

2. in each column of the matrix, the n vectors in that column form a basis of V.

If all the bases are the standard basis then this reduces to the existence of Latin squares.

Unrelated trivia question:  AGC-GTC-TGC-GTC-TGC-GAC-GATC-? what comes next in the sequence?

We mentioned Rota’s basis conjecture in various earlier posts.  A classic paper on the subject is the 1989 paper by Rosa Huang and Gian Carlo-Rota. Three and a half years ago Timothy Chow lunched a polymath project (Polymath 12) to solve it. (Here is my post on the project with various variants of the conjecture, the first post on the polymath blog, and the wiki). See this post for several famous conjectures by Rota, and this post about the related Alon-Tarsi conjecture.

This entry was posted in Combinatorics, Updates and tagged , , . Bookmark the permalink.

14 Responses to To cheer you up in difficult times 9: Alexey Pokrovskiy proved that Rota’s Basis Conjecture holds asymptotically

  1. Hey Gil, I asked a question on your latest Preprint: https://scirate.com/arxiv/2008.05188#1518. Please answer it. Thank you.

    • Gil Kalai says:

      Hi Victory, thanks for the question, I will think about it…

    • Gil Kalai says:

      Hi Victory, your question is if my theory does not contradict the (excellent) paper ( https://arxiv.org/abs/1904.01502 ) Quantum advantage with noisy shallow circuits in 3D by
      Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel.

      This paper is quite involved but the reason for why if the argument in Section 4 of my paper is correct it will exclude the construction of BGKT appears to be simple. Let’s make an experiment: try to read Sections 4.1 and 4.2 of my paper and see if you see it.

      • Victory Omole says:

        You are saying that the statement I quoted from your paper does not contradict Bravyi Et Al.’s proof? What is BGTK? I can’t find it when I search your paper.

        I have read Sections 4.1 and 4.2 of your paper and i don’t “see it” as you say; because your claim that NISQ devices are low-level classical computational devices goes against what Bravyi Et Al. proved.

      • Gil Kalai says:

        Victory,
        BGTK should be BGKT Bravyi, Gosset, Koenig, and Tomamichel.

        two questions:

        1) Do you regard Bravyi Et Al.’s construction as belonging to the NISQ regime?

        2) There is a specific object needed for Bravy et al. that the argument in Section 4.1 (or 4.2) in my paper asserts that it cannot be constructed. Can you see what it is?

      • Victory Omole says:

        I can’t seem to comment directly on you latest comment.

        You are probably right about Bravyi Et Al.’s not being NISQy and I think the construction that’s needed that you are talking about is that the error threshold is not low enough for NISQ devices to give an advantage.

      • Gil Kalai says:

        Right, Victory. I also would not regard Bravyi et al.’s construction as a construction in the NISQ regime.

        For my second question I refer to specific gadget that Bravi et al. uses and that my argument specifically asserts that it cannot be build. Do you see what I refer to?

      • Victory Omole says:

        While looking at section 4.1 and 4.2, i don’t see what gadget you are referring to.

      • Gil Kalai says:

        Victory, I referred to quantum error-correcting codes. As far as I can see, Bravyi et al. relies on the ability to construct quantum error correcting codes in the NISQ regime.

  2. Vijay Vazirani says:

    Thank you for telling us about a very beautiful result Gil!
    A question:
    Is there always a permutation of the columns of your grid so the diagonal is also a basis?

    • Vijay Vazirani says:

      If the answer is yes to the previous question, how many perfect matchings of this matrix can simultaneously be bases? What are min and max?

    • Rose McCarty says:

      The answer is no when B_1=B_2 is the basis {(1,0), (0,1)} for R^2, becuase the diagonal is forced to have dimension 1. But this is not very satisfying – what about an example where the matroid on n^2 elements is simple?

  3. Gil Kalai says:

    Dear Vijay, these are excellent questions. Unfortunately I dont know the answer even to the first but it might be easy. I hope some reader of the blog could answer. I will think about it.

Leave a Reply

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

WordPress.com Logo

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

Google photo

You are commenting using your Google 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