Some unfi nished ideas about dense subsets of a discrete set

(pdf copy)

We define the notion of {\epsilon}-dense subsets and enumerate the number {\epsilon}-dense subsets of the finite set {[n]=\{1,2,\dots ,n\}}.

1. Basic

Definition. A subset {S} {(\ne \emptyset)} of {[n]} is said to be {\epsilon}-dense if {\forall \, a\in [n]\, \exists s\in S} such that {\mid s-a\mid \le \epsilon}.

Lemma. The number of compositions of {n} with not more than {p} parts and no part exceeding {\ell} is defined as {f(n,p,l)}. By Inclusion-Exclusion principle,

\displaystyle f(n,p,l)={n+p-1\choose {p-1}}-\sum_{i=1}^{\lfloor \frac{n}{\ell +1}\rfloor} (-1)^{i+1} {p\choose i}{n-(\ell +1)i +p-1\choose {p-1}} \ \ \ \ \ (1)

Definition. {C(n,\epsilon)} is defined as the number of {\epsilon}-dense subsets of {[n]} with least cardinality.

We observe that this least cardinality has to be {k=\lceil \frac{n}{2\epsilon +1}\rceil}.

\displaystyle C(n,\epsilon)=\left \{ \begin{array}{ll} \sum_{x=0}^{2\epsilon}f(x,2,\epsilon)\cdot f(n-k-x,k-1,2\epsilon) & \text{ if }k\ge 2\\ \left. \begin{array}{ll} n & \text{ if } \epsilon \ge n-1\\ \left. \begin{array}{ll} 2\epsilon +2-n & \text{ if }2\epsilon +2-n\ge 1\\ 1 & \text{ if }2\epsilon +2-n\le 1 \end{array} \right \} \text{if }\epsilon <n-1 \end{array} \right \} \text{if }k=1 \end{array} \right. \ \ \ \ \ (2)

2. The open problem

The following matrix shows the {C(n,\epsilon)} values with {1\le n\le 15, 1\le \epsilon \le 15}.

\bigskip

{\left( \begin{array}{ccccccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 1 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 4 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 3 & 1 & 3 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 1 & 9 & 2 & 4 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 \\ 8 & 8 & 1 & 3 & 5 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ 4 & 6 & 16 & 2 & 4 & 6 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 \\ 1 & 3 & 15 & 1 & 3 & 5 & 7 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 \\ 13 & 1 & 13 & 25 & 2 & 4 & 6 & 8 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ 5 & 27 & 10 & 24 & 1 & 3 & 5 & 7 & 9 & 11 & 11 & 11 & 11 & 11 & 11 \\ 1 & 18 & 6 & 22 & 36 & 2 & 4 & 6 & 8 & 10 & 12 & 12 & 12 & 12 & 12 \\ 19 & 10 & 3 & 19 & 35 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 13 & 13 & 13 \\ 6 & 4 & 1 & 15 & 33 & 49 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 14 & 14 \\ 1 & 1 & 64 & 10 & 30 & 48 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 15 \end{array} \right)}

Can we arrive at the values and the values of {\epsilon}‘s where the function maximizes?

(I will write more soon 🙂 )

Advertisements

ನಿಮ್ಮದೊಂದು ಉತ್ತರ

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s