2
$\begingroup$

Let $S_1,S_2,\ldots S_k$ be a sequence of sets. We will call this sequence expanding if $S_i$ is not covered by $S_1,\ldots S_{i-1}$ i.e. $S_i$ contains at least one new element. Let $C_p$ be a cyclic group of size prime order $p$.

It is easy to show that for every $A\subset C_p$ there exists at least $k=\frac{p}{|A|}$ elements $a_1,\ldots a_k$, such that the sets $A+a_i$ are expanding.(Since each time we cover at most |A| new elements and we can cover all elements)

My question is if it is possible to improve this bound for $A$ of size at most $p/2$ to $k=\frac{p\log|A|}{|A|}$?

$\endgroup$
3
  • $\begingroup$ Here is important that group is of prime order. Else if A is $pC_m$, where p divisor of $m$ than $k=\frac{m}{|A|}$ $\endgroup$ Jan 30, 2012 at 16:13
  • $\begingroup$ Let $a_0,a_1,a_2,\dots,a_k$ be a list of elements from $C_p$, $A \subset C_p$ and $A_i=A+a_i.$ Are you looking to have $A_0,A_0\cup A_1 ,A_0\cup A_1 \cup A_2 \dots?$ an expanding sequence? $\endgroup$ Jan 30, 2012 at 18:25
  • $\begingroup$ By the definition $A_0,A_1,\ldots $ expanding if and only iff $A_0,A_0\cup A_1,A_0\cup A_1\cup A_2,…$ is expanding. I am looking that $A_1,A_2,\ldots$ is expanding. Where $A_i=A+a_i$ $\endgroup$ Jan 30, 2012 at 19:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.