Ramsey numbers for matroids (Q1363003): Difference between revisions

For positive integers \(s\) and \(t\), the matroid Ramsey number \(n(s,t)\) is the least positive integer \(n\) such that every connected matroid with at least \(n\) elements has either a circuit with at least \(s\) elements or a cocircuit with at least \(t\) elements. The existence of such numbers was established in 1991 by Lovász, Schrijver, and Seymour in response to a question of Robin Thomas. They showed that if \(s\) and \(t\) are positive integers whose sum is at least three, then \(n(s,t) \leq 2^{s+t-3}\). The existence of these matroid Ramsey numbers can also be deduced from a result of \textit{Zs. Tuza} for set systems [Discrete Appl. Math 16, 183-185 (1987; Zbl 0615.05001)]. The main result of the paper under review is that the matroid Ramsey numbers have several attractive properties that are strikingly similar to properties of the classical Ramsey numbers for graphs that were proved by \textit{P. Erdős} and \textit{G. Szekeres} [Compos. Math. 2, 463-470 (1935; Zbl 0012.27010)]. In particular, if \(s\) and \(t\) exceed one, then \(n(s,t) \leq n(s-1,t) + n(s,t-1) - 1\). Using this result and an extension of it, the author proves that \(n(s,t) \leq {{s+t-4}\choose{s-2}} - 1\).