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 B1, B2, …, 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.
Combinatorics and more 
Hey Gil, I asked a question on your latest Preprint: https://scirate.com/arxiv/2008.05188#1518. Please answer it. Thank you.
Hi Victory, thanks for the question, I will think about it…
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.
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.
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?
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.
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?
While looking at section 4.1 and 4.2, i don’t see what gadget you are referring to.
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.
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?
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?
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?
Thank you, Rose, for refining the question!
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.
Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more