combinatorics or coding theory question

Thread View: sci.math.research

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Gerard J. Rinkus Sun, 24 Jan 1993 19:27

#185

Author: Gerard J. Rinkus
Date: Sun, 24 Jan 1993 19:27

47 lines
2224 bytes



Hi,

I have a combinatorics question that I have been unable to solve.
I have asked a number of mathematics professors, and otherwise
mathematically sophisticated people as well and no one has
been able to show me the general solution to the following
problem.  This question arose to me in connection with a 
neural net model of spatio-temporal memory that I'm working on.

Suppose you have N groups of cells.  Each group contains K cells.
Now suppose you make choices consisting of one cell chosen from
each of the N groups.  Let each such choice be called a vector.
Clearly there are K^N unique vectors.

My question is:  what is the largest set of vectors you can pick
such that no two of the vectors overlap (i.e. have the same cell)
at more than Q of the groups (where Q < N)?

The answer for the special case of Q = N-1 is K^N.  This follows
immediately from the fact that if there are K^N unique vectors
then each vector must be different from any other vector in at
least one group (and therefore no two vectors (in the entire space
of K^N vectors) can overlap at more than N-1 groups).

I've also found for various small special case, that the answer is
K^(Q+1).  

But I haven't been able to figure out the general solution, or
prove that it is K^(Q+1) if in fact it is.

Thanks in advance for any help on this.

Rod Rinkus
Dept. of Cognitive and Neural Systems
Boston University
Boston, MA 02215
email: rinkus@park.bu.edu


--
Gerard J. Rinkus
Dept. of Cognitive and Neural Systems
Boston Univ.
rinkus@cns.bu.edu

Re: combinatorics or coding theory question

#188

Author: Steve Linton
Date: Mon, 25 Jan 1993 15:56

31 lines
1688 bytes

|> Suppose you have N groups of cells.  Each group contains K cells.
|> Now suppose you make choices consisting of one cell chosen from
|> each of the N groups.  Let each such choice be called a vector.
|> Clearly there are K^N unique vectors.
|> 
|> My question is:  what is the largest set of vectors you can pick
|> such that no two of the vectors overlap (i.e. have the same cell)
|> at more than Q of the groups (where Q < N)?

In more usual language, you want your vectors to differ in at least N-Q places. I
shall call this number D.

You are looking for the largest code with minimum distance D among your K^N
vectors.

Each vector has       (N+D)   neighbours  at diostance less than D, so a 
		      ( D )
		(K-1)^

simple upper bound on the size of your code is  

			  -(N+D/2)	
		K^N (K-1)^ ( D/2 )

(that's K to the N times (K-1) to the N+D/2 choose D/2).

Anyway, you want to look at Codes, Groups and Sphere Packings by J.H.Conway and
N.J.A. Sloane.

		Steve Linton

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads