Meeting management

2012-02-24T07:42:52Z

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?

Answer by Gerhard Paseman for Meeting management

2012-02-24T19:51:39Z

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

Answer by Jim Slattery for Meeting management

2012-02-27T14:05:02Z

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.

Answer by Aaron Meyerowitz for Meeting management

2012-02-29T08:20:57Z

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.)

Meeting management - MathOverflow

Meeting management

Answer by Gerhard Paseman for Meeting management

Answer by Jim Slattery for Meeting management

Answer by Aaron Meyerowitz for Meeting management