×

Effective versions of two theorems of Rado. (English) Zbl 1448.52011

In 1957, Richard Rado proved that each representative matroid is representable over a finite field \(\mathbb{F}\) (see [R. Rado, Proc. Lond. Math. Soc. (3) 7, 300–320 (1957; Zbl 0083.02302)]). In the present article, the authors ask: if the matroid has \(n\) elements, then how large must \(\mathbb{F}\) be?
Letting \(\mathcal{M}_n\) denote the family of representable matroids on \(n\) elements, define \begin{align*} c(n) &= \max\{c(M) : M\in\mathcal{M}_n\}\\ f(n) &= \max\{f(M) : M\in\mathcal{M}_n\}\,, \end{align*} where \(c(M)\) (resp., \(f(M)\)) denotes the smallest positive characteristic (resp., the smallest order) of a field over which \(M\) is representable.
The authors prove interesting upper and lower bounds for \(c(n)\) and \(f(n)\). Similarly, they prove that each matroid \(M\) on \(n\) elements which is representable over a field of characteristic 0 must also be representable over \(\text{GF}(p)\) whenever \(p\) is a prime satisfying \[ \log_2\log_2\log_2 p > n^5\,. \]

MSC:

52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
05B35 Combinatorial aspects of matroids and geometric lattices

Citations:

Zbl 0083.02302
PDFBibTeX XMLCite
Full Text: DOI arXiv