TY - JOUR
T1 - Halfway to Rota's Basis Conjecture
AU - Bucić, Matija
AU - Kwan, Matthew
AU - Pokrovskiy, Alexey
AU - Sudakov, Benny
N1 - Publisher Copyright:
© 2020 The Author(s) 2020. Published by Oxford University Press. All rights reserved. For permissions, please e-mail: [email protected].
PY - 2020/11/1
Y1 - 2020/11/1
N2 - In 1989, Rota made the following conjecture. Given $n$ bases $B_{1},\dots, B_{n}$ in an $n$-dimensional vector space $V$, one can always find $n$ disjoint bases of $V$, each containing exactly one element from each $B_{i}$ (we call such bases transversal bases). Rota's basis conjecture remains wide open despite its apparent simplicity and the efforts of many researchers (e.g., the conjecture was recently the subject of the collaborative "Polymath"project). In this paper we prove that one can always find $\left (1/2-o\left (1\right) \right) n$ disjoint transversal bases, improving on the previous best bound of $\Omega \left (n/\log n\right) $. Our results also apply to the more general setting of matroids.
AB - In 1989, Rota made the following conjecture. Given $n$ bases $B_{1},\dots, B_{n}$ in an $n$-dimensional vector space $V$, one can always find $n$ disjoint bases of $V$, each containing exactly one element from each $B_{i}$ (we call such bases transversal bases). Rota's basis conjecture remains wide open despite its apparent simplicity and the efforts of many researchers (e.g., the conjecture was recently the subject of the collaborative "Polymath"project). In this paper we prove that one can always find $\left (1/2-o\left (1\right) \right) n$ disjoint transversal bases, improving on the previous best bound of $\Omega \left (n/\log n\right) $. Our results also apply to the more general setting of matroids.
UR - http://www.scopus.com/inward/record.url?scp=85081207825&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85081207825&partnerID=8YFLogxK
U2 - 10.1093/imrn/rnaa004
DO - 10.1093/imrn/rnaa004
M3 - Article
AN - SCOPUS:85081207825
SN - 1073-7928
VL - 2020
SP - 8007
EP - 8026
JO - International Mathematics Research Notices
JF - International Mathematics Research Notices
IS - 21
ER -