Chennai Mathematical Institute

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|)$.