A friend wants to have ten meetings of six people every day for five days with no pair of people meeting twice. Is this possible? It appears to be a question about maximal decomposition of a complete graph on 60 vertices into sets of 10 disjoint complete graphs on 6 vertices such that no edge is used twice. Does anyone know a useful theorem or, better, a way of constructing an example?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Ten meetings in total? Ten meetings per day during five days (i.e. 50 meetings)? Does the graph have 60 vertices because there are 60 people in total? What if I partition the graph as you say into disjoint complete graphs of 6 vertices, how does the the number "five" (as in "five days") enter the picture?, etc. I'm sorry but I think this question is very poorly formulated. Maybe you can clarify? $\endgroup$– Pablo LessaFeb 25, 2012 at 6:19
-
$\begingroup$ For some reason I can't edit the question, but here goes: There are 60 people. On each of five days, the people are partitioned into ten groups of six for day-long meetings. Is it possible to find a set of five partitions such that no two people meet twice? $\endgroup$– Andrew D. KingFeb 25, 2012 at 21:07
-
2$\begingroup$ This type of problem is studied in combinatorial design theory, not graph theory. If every pair of people would meet exactly once, or exactly $\lambda$ times, this would be a resolvable block design. If simple divisibility checks are satisfied, you should expect resolvable block designs to exist for large enough numbers of vertices, but unfortunately $59$ is not divisible by $5$ so there is no way to take just part of a resolvable block design with $\lambda=1$ here. Nevertheless, there are many ways to construct resolvable block designs, and you should talk to a design theorist. $\endgroup$– Douglas ZareFeb 27, 2012 at 17:13
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
Look at the edit history for an old idea (if you wish).
Here is a schedule which runs for 8 days. Each row is an agenda for a day. It consists of 60 digits in 6 groups of 10 (for readability). Note that I will usually count days, people and meetings each day starting from 0 ( except that the schedule below starts with day 1.) Day 2 begins 0123456777.8777 which tells us that people 7,8,9,11,12, and 13 make up meeting 7 that day. You may confirm that no two of those six people is ever in a meeting together on another day.
0001000234.5167513847.9497368284.1239662875.3198562431.7649587529 0123456777.8777465293.8508631463.0984282401.9598350211.5946032961 0123456465.2738999699.9630784282.4017578350.2115746032.7615803418 0123456724.0185873502.1999499928.6157034172.6846528375.0763146308 0123456157.4603276158.0341826799.9299950863.1463078428.2401757835 0123456630.7842824017.5783502115.7460399919.9934182674.6527385086 0123456276.1580341826.7465273850.8631463078.4299909997.8350211574 0123456783.5021157460.3276158034.1826746527.3850863149.9979998240
The method of generation is systematic (I thought it might work at least for 5 days and was pleased to get 8). I only sketch it here, still it took less time to do (with Maple) than it does to describe.
Begin with the field of $9$ elements which could be thought of as $\mathbb{Z}_3[i]$, the Gaussian integers $\mod{3}$. Code it somehow, I used $0 \rightarrow 0$ and $(1+i)^{j-1} \rightarrow j$ for $1 \le j \le 8$.
Using the method of Kevin Costello, one can construct a 9 day schedule of meetings for 63 people which has 9 meetings of 7 people each day (and no pair is ever in the same meeting twice.) What we will do is take 80 of those 81 meetings, reduce each one to six people and arrange the 80 meetings into eight days each with ten meetings. Call a meeting big if it has seven people and good once it is reduced to six people.
On day $0$, meeting $j$ has people $7j,7j+1, \cdots,7j+6$ so the ninth meeting (meeting $8$) is $56,57,58,59,60,61,62$ Go through days 1 through 8 and erase people 60,61,62 (note that no two of them are ever in the same meeting after day 0). At this stage each of those eight days has nine meetings, three are good and six are big. We wish to remove one person from each big meeting to make them good and use the removed people for a tenth good meeting. To have a chance of doing this appropriately, we look for a meeting from day 0 which has only one member already in a good meeting. If we manage to do this then the other six people are sure to be distributed one in each big meeting. Use them to make a tenth good meeting.
An example may help: Here is the schedule for day 4 after people $60,61,62$ are removed (note that I have sorted the people in each meeting and sorted the list of meetings according to least person in the meeting)
$\small [0, 10, 18, 26, 34, 50, 58], [1, 11, 20, 21, 31, 37, 54], [2, 8, 19, 28, 39, 45], [3, 16, 27, 35, 47, 53, 57], [4, 9, 24, 36, 42, 55],$ $\small [5, 13, 17, 22, 32, 44, 49],[6, 25, 30, 40, 43, 52, 56], [7, 15, 33, 38, 48, 51], [12, 14, 23, 29, 41, 46, 59]$
The eighteen people who are already in good meetings are:
2 4 * 7 8 9 * 15 19 *24 *28 33 *36 38 39 *42 45 48 51 55 so the only day 0 meeting which only includes one of them is [21,22,23,24,25,26,27]. Removing person 24 from that group and the other six people from their groups yelds
$\small [0, 10, 18, 34, 50, 58], [7, 15, 33, 38, 48, 51], [12, 14, 29, 41, 46, 59], [1, 11, 20, 31, 37, 54], [2, 8, 19, 28, 39, 45],$ $\small [3, 16, 35, 47, 53, 57], [4, 9, 24, 36, 42, 55], [5, 13, 17, 32, 44, 49], [6, 30, 40, 43, 52, 56], [21, 22, 23, 25, 26, 27]$
0123456724.0185873502.1999499928.6157034172.6846528375.0763146308 is the resulting code appearing as line 4 above. The first meeting explains the digit 0 in positions 0,10,18,34,50,58.
As it turns out, each day from 1 to 8 is compatible with exactly one meeting from day 0 and vice versa, perhaps there is an explanation for this, but I am satisfied that it happened this once.
Reviewing this I see that I could have pushed the construction by Kevin to get $10$ days with $90$ meetings (I think.) It does not seem that this would allow 10 days of meetings with $60$ people but I have not carefully checked (nor do I plan to.)
answered Feb 29, 2012 at 8:20
-
$\begingroup$ No, there is no way to extend this. With the exception of , any added meeting would have to be a subset of a congruence class mod 7. perhaps with the addition of one or more of people 56,57,58,59 who were in the unusual meeting with 60,61, and 62. That may be enough for a ninth say with 7 meetings but not for 10. $\endgroup$ Mar 1, 2012 at 10:23
$\begingroup$
$\endgroup$
2
Here is an alternate formulation which you may find easy to implement as a random search: Find 60 five digit numbers (leadng zeroes allowed and required) such that every digit occurs equally often in each position (ones, tens, hundreds, etc.) among the collection, and any two numbers differ in their digits in at least four positions. When you have it coded, you can try seeding it with some small sets like 00000 11111 ... 99999 01234 and see how far you get with random selection. If you succeed in picking 20 such numbers, you may find the candidates for the 21st number to be quite limited, and in some cases show that you can't complete the list with those 20 numbers.
Gerhard "Ask Me About System Design" Paseman, 2012.02.24
answered Feb 24, 2012 at 19:51
-
$\begingroup$ Another idea: Try the same exercise, but use half as many digits for 30 numbers. When you find 30 numbers with a few errors (people meeting more than once) but equal occurrences of digits, clone that solution and see if you can fix the errors by exchanging people with their clones. Gerhard "Double The Freshness And Flavor" Paseman, 2012.02.24 $\endgroup$ Feb 25, 2012 at 5:19
-
$\begingroup$ This is a reasonable idea but does add a further condition that the people come from 6 companies ( 10 from each) and you never have 2 people from the same company in a meeting. It is not obvious that the desired setup is possible, but is it obvious you cant manage 6 days, or 10 or 11 (dropping the restriction) $\endgroup$ Feb 28, 2012 at 0:26
$\begingroup$
$\endgroup$
7
Thanks Gerhard, that is roughly what I am trying. I get very close with four days but have not succeeded with 5. However, the numbers of permutations are very large - other wise I would go through them systematically. I thus wondered if there was some theory or a fast algorithm I could use.
Just as an interesting fact, I note that cycling round through the vertices in multiple of prime numbers (that are not factors of 60) counting off 6 for each group produces quite promising results. However, I guess there is something about working out whether numbers are mutually prime in modulo 60 that I should need to understand.
-
$\begingroup$ Actually I wrote some code on Friday that attempted to generate a solution randomly. It failed spectacularly. I suspect that this schedule is actually impossible, and maybe some structural analysis could prove it. For example, take "person" $v_1$ and a Monday schedule 1-6, 7-12, etc. For the next four days, $v_1$ will meet with 20 other people, and there are 54 available. $v_1$ can't meet with 5 people from any other group, because they would all have to be on different days, so $v_1$ meets with $\leq 4$ people from each other group... $\endgroup$ Feb 27, 2012 at 19:01
-
$\begingroup$ PS Jim you posted an answer where a comment would be more appropriate. $\endgroup$ Feb 27, 2012 at 19:02
-
$\begingroup$ I am not a combinatorial design theorist, so I do not know if difference sets are appropriate here. They seem to me to be similar to your prime number approach, I think they help with avoiding duplicate pairs, and you may find something of use to you if you search for that. Gerhard "Ask Me About System Design" Paseman, 2012.02:27 $\endgroup$ Feb 27, 2012 at 19:32
-
1$\begingroup$ Andrew: I think any "structural analysis" proof may be complicated. For example, if we replace $60$ by $66$ and go for $11$ meetings a day instead of $10$, then we can actually run for $11$ days (associate each person with a pair $(x,y)$ where 0≤x≤5 and 0≤y≤10, and on day j have person $(x,y)$ meet in room $y+jx$ mod 11). With $54$ people, you can work over the field with $9$ elements and do the same thing. So any argument would have to make use of the fact that $10$ is not a prime power. Even for projective planes, such a simple proof isn't known for this case. $\endgroup$ Feb 27, 2012 at 19:36
-
2$\begingroup$ I would be very surprised if it were impossible to construct such a schedule. Random constructions do not do well in this type of problem since the total number of possibilities is much greater than the typically large number of solutions. $\endgroup$ Feb 27, 2012 at 21:58