Halfway to Rota's Basis Conjecture

Matija Bucić, Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)8007-8026
Number of pages20
JournalInternational Mathematics Research Notices
Volume2020
Issue number21
DOIs
StatePublished - Nov 1 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Halfway to Rota's Basis Conjecture'. Together they form a unique fingerprint.

Cite this