MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there anything known about the following problem? Which (sub)field to look into for questions of this flavor?

Consider a collection $F$ of subsets of $[n]$, excluding the empty set, with the property that every element of $[n]$ is contained in exactly $n$ sets. The same set might appear more than once in $F$ (The number of sets in $F$ is thus between $n$ and $n^2$ and the sum of cardinalities is $n^2$).

Is there a sequence (possibly with repetitions) of the numbers $1 \dots n$, of length at most $n^\alpha$, such that each set appears somewhere in the sequence in at most $n^\beta$ contiguous blocks.

Here's a small example: F = { {1,2}, {1,3}, {2,3}, {1,2,3} }. In the sequence (1,2,3) the set {1,3} can be mapped to two blocks only. In the sequence (1,2,3,1) all sets can be mapped to a single block.

$\alpha = 1, \beta=1$ works if we use any permutation of the numbers.

$\alpha = 2, \beta =0$ works if we concatenate all sets of F.

Can we get something "in between" ?

EDIT: as an important special case, F could consist of n "partitions" of [n].

share|cite|improve this question
Unfortunately, I do not understand the important special case when $F$ consists of $n$ partitions of $[n] := \{ 1,2,\dots,n \}$. If $F$ is to have size $n$, then necessarily $F$ must consist of $n$-many copies of $\{ 1,2,\dots,n \}$. Right? – Asher M. Kach Jul 2 '12 at 23:08
Yes, if $F$ has size $n$, then $F$ just contains $n$ copies of $[n]$, in other words, $F$ contains $n$ copies of the partition, which is just the whole set itself. In this sense, it contains $n$ partitions of $[n]$ in this case too. For example, for n=3, $F$ could be {{1,2,3},{1,2,3},{1,2,3}} or {{1},{2,3},{1,2},{3},{1,2,3}} or {{1},{2},{3},{1},{2},{3},{1},{2},{3}}, etc. – László Kozma Jul 3 '12 at 8:59
But $F$ is not necessarily of size $n$, it is just $\geq n$ and $\leq n^2$. – László Kozma Jul 3 '12 at 9:01

Your Answer


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

Browse other questions tagged or ask your own question.