TY - JOUR

T1 - Halfway to Rota's Basis Conjecture

AU - Bucić, Matija

AU - Kwan, Matthew

AU - Pokrovskiy, Alexey

AU - Sudakov, Benny

N1 - Funding Information:
This work was supported in part by SNSF project [178493 to M.K.]; SNSF grant [200021-175573 to B.S.].
Publisher Copyright:
© 2020 The Author(s) 2020. Published by Oxford University Press. All rights reserved. For permissions, please e-mail: journals.permission@oup.com.

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

VL - 2020

SP - 8007

EP - 8026

JO - International Mathematics Research Notices

JF - International Mathematics Research Notices

SN - 1073-7928

IS - 21

ER -