3
$\begingroup$

Consider a uniform vector matroid $M(0)=U_{m,n}$ of rank $m$ with $n$ points, $n>m>2$ (you can think of it as a set of $n$ points in general position in vector space $F^m$ for some large field $F$). We perform a series of $T$ consecutive independent random transformations of $M(0)$ to obtain matroid $M(T)$.

At $t$-th transformation we choose a random set of $3$ points $x,y,z$ uniformly out of $n$ points of the $M(t-1)$-th ground set. We delete $z$ from $M(t-1)$ (obtaining $M(t-1)\backslash \{z\}$) and add a new point $z'$ freely to the closure of $\{x,y\}$. Equivalently, the new $z$ becomes a linear combination of $x,y$ in general position. The new matroid $M(t)=M(t-1)\backslash \{z\}+_{\textrm{cl}\{x,y\}} z'$ still has $n$ points, but, possibly, lower rank.

How to analyze the evolution of $\textrm{rank }M(t)$ with $t$? Specifically, I am interested in estimating the average $t$ for which the rank becomes $m-1$. Any references to related topics would also be greatly appreciated.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.