Uniform families and count matroids (Q5956108)

Given an \(r\)-graph \(G\) on \([n]\), new \(r\)-graphs with at least \(l\) edges and at most \(m\) vertices appear, by adding consecutively new edges to \(G\). The author presents, for all sets of parameters \(n\), \(r\), \(l\), \(m\), a construction of \(G\) such that \(G\) is a minimal graph for which it is possible to do it. The minimality of the graph \(G\) is connected with a property of the matroids for which all \(r\)-graphs of size \(l\) are circuits: they admit many polynomials in \(n\) as the rank function. These matroids are called count matroids, the same name as in the case of linear rank functions. The author applies count matroids to verify his conjecture of minimality for some sets of parameters, although the question is still far from being solved in the full generality. In particular, a problem posed by Erdős of characterizing the extremal graphs with \(r+1\) vertices and 3 edges is solved.