Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $X$ be a set, let $\mathcal{C}$ be a collection of subsets of $X$, and let $x_1, \dots , x_k \in X$. Say that the sequence $\{x_i\}_{i=1\dots k}$ is a sequential transversal (of length $k$) through $\mathcal{C}$ if there exist $S_i \in \mathcal{C}$ for which $x_i\in S_i$ but $x_i \notin S_j$ if $j\lt i$. Say that $\{x_i\}$ is a sequential antitransversal (of length $k$) through $\mathcal{C}$ if there exist $S_i \in \mathcal{C}$ for which $x_i\notin S_i$ but $x_i \in S_j$ if $j\lt i$, that is, if $\{x_i\}_{i=1\dots k}$ is a sequential transversal of length $k$ through the collection of complements of elements of $\mathcal{C}$.

Are there known conditions on $\mathcal{C}$ or the elements of $\mathcal{C}$ that guarantee the existence of a long sequential transversal, or that guarantee the existence of either a sequential transversal or a sequential antitransversal of some minimum length?

I found the term sequential transversal here. Is there another, more common, name for it in the literature, or a not-too-general general setting for which this is a specific case? A number of similar properties seem to be well-studied in combinatorics and order theory, but not this exact one.

share|improve this question
1  
Without mentioning any $x_i$, you can just say that $S_i$ is a sequence of sets in $\mathcal C$ whose series of unions is strictly increasing (starting with the empty union; i.e. $S_1$ is non-empty) or whose series of intersections is strictly decreasing (starting with the empty intersection $X$; i.e. $S_1$ is not all of $X$). If you make a $\{0,1\}$ incidence matrix $M$ with columns indexed by $X$ and rows indexed by $\mathcal C$, you are asking for the size of the largest square submatrix in $M$ or its complement which is permutation equivalent to lower triangular invertible. –  Tracy Hall Feb 16 '11 at 19:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.