Welcome to MathOverflow

Question

3

Does a 10-element set have 30 3-element subsets such that each pair is in two of these 30 subsets?

edited Jun 19 at 1:41

Gerry Myerson
15.7k●1●47●87

asked Jun 18 at 20:12

David Wasserman
205●4

2

Dear David. I fear that some will tend to think that your question is a homework, and will therefore vote to close it. To avoid that, you should indicate a little bit the context in which your questions arose. In particular, where to the numbers 10 and 30 come from? – André Henriques Jun 18 at 20:28

I light of Douglas Zare's answer, this question did not deserve to be closed. I vote to reopen. – André Henriques Jun 18 at 21:51

I still think the question would benefit from some explanation as to the OP's motivation. It isn't the kind of question that pops into my head at random, although I don't claim to be representative. – Yemon Choi Jun 19 at 0:17

2

This question was motivated by communications scheduling. It concerns a n-node network in which up to m nodes can broadcast at a time; nodes can not receive while sending, but when not sending they can simultaneously receive from all m senders. The goal is to serve all source-destination pairs equally. n=10 and m=3 are arbitrary choices. 30 is the minimum possible because there are n(n - 1) = 90 pairs, n(n - m) = 21 can be served at a time, and lcm(90, 21)/21 = 30. I was assuming the 30 subsets are distinct, but now I see that my application doesn't need that. – David Wasserman Jun 19 at 16:48

Douglas Zare · Accepted Answer · 2012-06-18 21:32:48Z UTC

12

This asks for a $(10,3,2)$ balanced incomplete block design. These are known. There are $960$ different designs with those parameters up to isomorphism according to the CRC Handbook of Combinatorial Designs.

edited Jun 18 at 21:32

answered Jun 18 at 21:24

Douglas Zare
13.2k●3●36●58

	In 394 of these, the designs are simple, which means the triples are distinct. A more natural interpretation of the question would be to add the condition that the block design is simple. – Douglas Zare Jun 18 at 21:44
	If the poster cares to chew up computer cycles, here is one approach: find 10 vectors of length 30, each with entries either 0 or 1, such that each vector has exactly 9 occurrences of 1 and such that any two distinct vectors share exactly two coordinates with ones. A little reasoning allows you to assume the form of the first three vectors (possibly four) and the computer can check for the constraints on the remaining vectors. Gerhard "Ask Me About System Design" Paseman, 2012.06.18 – Gerhard Paseman Jun 18 at 22:27

Gerry Myerson · Answer 2 · 2012-06-19 01:46:00Z UTC

4

If you prefer websites to books, you can go to http://designtheory.org/database/t-designs/ and scroll down to the line that starts 2 10 30 9 3 2, and click on "download" to receive the 960 designs.

answered Jun 19 at 1:46

Gerry Myerson
15.7k●1●47●87

I actually did that first, but after installing and using bunzip I got an xml file in a format I didn't know, and I see documents describing the xml format used, but not a program which will turn it into a humanly readable form. Maybe I overlooked one. – Douglas Zare Jun 19 at 9:24

Does a 10-element set have 30 3-element subsets such that each pair is in two of these 30 subsets?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.