2
$\begingroup$

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].

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Asher M. Kach Jul 2 '12 at 23:08
  • $\begingroup$ 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. $\endgroup$ – László Kozma Jul 3 '12 at 8:59
  • $\begingroup$ But $F$ is not necessarily of size $n$, it is just $\geq n$ and $\leq n^2$. $\endgroup$ – László Kozma Jul 3 '12 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.