Seminars

 Algorithm for Polynomially Bounded Intersection of Linearly Representable Matroids Dr T C Vijayaraghavan Chennai Mathematical Institute. 20-11-07 Abstract We study a bounded version of linearly representable matroid intersection problem. As input, we have two matroids \$(S,I_1)\$ and \$(S,I_2)\$ in terms of their linear representations \$M_1\$ and \$M_2\$ respectively, with an assumption that the number of sets of maximum cardinality in the intersection of \$M_1\$ and \$M_2\$, denoted by \$(S,I)\$ is bounded by a polynomial in the size of \$S\$. The problem is to compute the maximum size of any set in \$I\$. We show that this problem is in \$\L ^{\GapL }\$. Also it is possible to check if \$(S,I)\$ so obtained is linearly representable or not in \$\L ^{\GapL }\$. If \$(S,I)\$ is linearly representable, then a polynomial time algorithm is provided to construct a linear representation for \$(S,I)\$ over \$\Q\$, the set of rational numbers. We also show that any matroid \$(S,I)\$ linearly representable over \$\Q\$ is also representable over the field of all integers modulo a prime \$p\$, where size of the prime \$p\$ is \$O(\log |S|)\$.