On Abstract Integral Dependence

The concept of a tag system is introduced. In its general form the combinatorial structure of a dual pair of tag systems arises through composition of blocking pairs of clutters. This leads to a “painting” characterization for dual pairs of tag systems which is useful for establishing combinatorial theorems of the alternative for certain classes of tag systems. Integral tag systems arise as a natural combinatorial abstraction of integral linear dependence properties of rational vectors in analogy with the manner in which matroids arise from linear dependence properties. Tag systems subsume matroids and several characterizations of matroids as tag systems are given; however, tag systems are shown to be generally less tractable computationally than matroids by establishing NP-completeness for the problem of determining a smallest base for an integral tag system.