May I sit here?

We do a lot of workshops, as do many of our colleagues. We invite people, or we are invited to a group, to discuss some ideas, develop imaginations of where those ideas might lead, speculate possible futures and then guide a process of imagining the details of life in those situations. We have and will continue to share many of our insights into how to develop such a process and our observations on what has worked and what hasn’t. What feels like a suitable arts-based research result and what feels applicable further away; both are things that we hope we can share.

One issue that we often have is arranging people in small groups for conversations. There are two important factors in these conversational round-tables. One is that people are brought into different meetings. We have observed that often people will develop a rapport with another person, or the opposite, and if they are then discussing at another table, then that relationship can dominate the conversation. Thus we try, where possible, to have people mixed. So we ask questions such as: can we arrange a series of sittings so that no two people share a table more than once? So that every pair of persons meets at least once? So that every pair of persons meets exactly once?

How to arrange who sits where, for some idea of best mixing?

It turns out that this problem can be well formulated mathematically. However it also turns out that there are not too many situations where the solution can be created that works perfectly. Thus we need to look at approximations and then even heuristics.

The exact case

Let’s look at a tiny example. Suppose we have 4 people and two coffee tables for two people each. Let’s call our people Alex, Beth, Chris and Dot. In the first round, or sitting, Alex and Beth share a table, Chris and Dot the second table. For the second round, Alex and Chris share a table, with Beth and Dot on the second table. The third round then has Alex and Dot on one table, with Beth and Chris on the second one. It works! So we know it is possible to arrange people this way. It is also nice that the process to create the seating arrangements was quite straightforward; we did not have to solve a Sudoku in order to get the appropriate arrangements.

Let’s try and formulate what happened here. We have a number of visitors to our event, let’s call this number v. We want to arrange them on several coffee tables, each the same size. The German word for coffee is Kaffee, so let’s say there are k people on each table. We want each pair of people to sit at the same table exactly once. In the literature of combinatorics, such an arrangement is called a Balanced Incomplete Block Design (BIBD) for reasons that originally come from the theory and practice of agricultural experiments. The Block is what we are calling our table, Incomplete means that we do not have everybody sitting at one table. Balanced refers to the requirement that everybody meets the other people the same number of times. And Design means that we have thought about it. The special numbers here mean that we have a (v,k,1) BIBD. But we also have another special condition. We want, in every round of the conversation, to have everybody sitting down at a table. This means that we want to partition the visitors onto the tables. Such a BIBD is called resolvable.

In the tiny example above, we have v=4 and k=2. The blocks are (suitably abbreviated) AB,AC,AD, BC, BD,CD. The first partition is AB|CD, the second is AC|BD and the third is AD|BC.

We also see some quick numerical restrictions. The size of the tables k must divide the number of visitors v. At each sitting, one person will meet k-1 other people. So in order to meet every other person exactly once, of which there are v-1, k-1 must divide v-1, and we will have (v-1)/(k-1) rounds or sittings in our event.

Suppose we have a speed dating night, or an event like the Schwarzmarkt für nützliches Wissen und Nicht-Wissen with all people being experts. It order to have everybody meet everybody else exactly once, how many people can we have? The table size is k=2, so v must be an even number. k-1=1 so this divides v-1 for all values of v. And it turns out that, for all even v, we can create a resolvable (v,2,1) BIBD. Another way to write this is to say that v=2n for some integer n.

What about tables of size 3? Then v must be divisible by 3, and v-1 must be divisible by k-1=2. It is not too hard to see that v=6n+3 for some integer n satisfies these requirements, and that any v that satisfies these requirements is of this form.

(Okay, let’s see why this is true. This is a quick introduction to how mathematicians think. Please skip this parenthesis if you don’t need or want to know how mathematicians think. We have two things to look at: showing that these values of v work, and that all value of v that work, have this form. First we look at the claim that v=6n+3 satisfies the requirements. We re-write to see that v = 3(2n+1) so v is divisible by 3. Then v-1=6n+3-2=6n+2 = 2(3n+1) so v-1 is divisible by 2. Done. Now for the other requirement. For v to be divisible by 3, v=3m for some integer m. For v-1 to be divisible by 2, v-1=2l for some integer l, so v=2l+1. How can we make these fit together? Well, m is either even or odd. So m is either 2M or 2M+1 for some (other) integer M. So either v=6M or v=6M+3. This means that v has remainder 0 or 3 when divided by 6. Similarly l is either 3L, 3L+1 or 3L+2 for some integer L. In each case v=6L+1, v=6L+2+1=6L+3 or v=6L+4+1=6L+5. So v has remainder 1,3 or 5 when divided by 6. From primary school we know that every integer has a unique remainder when divided by another integer, so the remainder must be 3. So v=6M+3 for some integer M, which is the same as saying that v=6n+3 for some integer n.

We hope that this little walk into how mathematicians think was not too hard. And perhaps offers a small insight into the pedantic but often useful ways that mathematicians go about what they do.)

This is called a necessary condition. If we are able to arrange a series of sittings so that our visitors can all meet each other around tables of size three, then the number of visitors must be 6n+3 for some integer n, thus v=9, 15, 21, 27, etc. This does not mean that we can actually make such an arrangement, that such a design exists.

We shall shift into a slightly higher gear for this paragraph. For those who have had enough technical mathematics, please jump ahead. We can find an example of a resolvable (v,k,1) BIBD for all v=p^2 and k=p, for p a prime number, in the following way. We write Zp for the integers 0,1,…,(p-1) and we add and multiply them normally, but if, when we add or multiply them, we get a number that is p or larger, we subtract p. So for p=3, 1+1=2, and 1×2=2 but 2+2=4=4-3=1 and strangely enough, 2 x 2 = 4 = 4-3 =1 as well. You may know these as the “integers modulo p” because we say that 1 and 4 are the same modulo 3, meaning they have the same remainder when we divide by 3. Give each visitor a unique card with two numbers from Zp on them, written (a,b). Label the tables with the numbers in Zp as well. For the first round, everybody goes to the table marked with their a. For the second round, they go to the table marked with their b. For the third round, they go to the table marked with a+b modulo p. For the next, they go to the table a+2b modulo p. They carry on until they go to the table marked a+(p-1)b modulo p. Some calculations show that no two people share a table more than once. By this stage, we have had p+1 rounds of sitting, each person has met (p-1) other people at each sitting, so they have met (p+1)(p-1) =p^2-1 other people, which is everyone else. So we have a resolvable (p^2,p,1) BIBD. We note that this can be extended to q being a prime power (e.g. 3^3=27) and we use Galois Field multiplication, but this is actual university algebra and not for here. What we have created here is a finite affine geometry. We write this as AG(2,p) to reflect that is two dimensional and we are using Zp. Here we have parallel lines (which is where the affine comes in) which give us our resolvable criterium. This is a way to see that a whole family of examples exist, for the case when our table sizes are a prime power (k= 2,3,4,5,7,8,9,11,13,16,…) and we have v=k^2 visitors to our workshop. For those who care, there is, up to re-labelling, only one way to do this.

Here we see an example of a resolvable (9,3,1) BIBD created from AG(2,Z3). The four sittings are shown with each table being a line joining 3 participants, each represented as dots. We leave the people dots in the same place and change the lines (tables), for clarity. Below we show how to calculate the table for each person based on their (a,b) label, and the tables are also numbered in the upper diagram. For example the person with label (1,2) will sit at tables 1,2,0 and 2 in that order.

More general problems like this have raised interest. In 1850 a certain Thomas Kirkman asked the following (now rather dated) question. We have 15 schoolgirls who need to walk from their boarding house to school every day, and do so in 5 rows of 3 girls each. Can we arrange them so that every girl walks next to different girls each day for a week? Kirkman was asking for a resolvable (15,3,1) BIBD. We saw above that v=15 satisfies the necessary conditions for this problem. It has been shown that there are 7 essentially different ways of doing this, up to renaming the schoolgirls.

It turns out that for every integer n, a resolvable (6n+3,3,1) BIBD exists. Which means that if we are working with tables of size three and have 9,15,21,27,… visitors to our workshop, we can have everybody sit and talk with everybody else exactly once. It will however take 3n+1 sittings, so 4,7,10,13,… which might try the patience of our participants.

Similar results exist in the combinatorics research literature for tables of size 4: the necessary condition is that v=12n+4 and it has been shown that this condition is also sufficient, so with tables of size 4 we can have 16,28,40,… visitors to the workshop and have everybody meet everybody else, in 4n+1 sittings, so 5,9,13,.…

We expect that a similar result will hold for k=5, also for 7,8 and 9, at which point the tables start to get a bit unwieldy. However the whole situation collapses for k=6. Because 6 is not a prime power, there is no standard affine geometry of this order. It can be shown by the Bruck-Ryser Theorem that there is no affine geometry, even if it were to be constructed some other way than with finite fields. If one attempts the construction above, one can create three sittings, with the person labelled (a,b) going to tables a, b and then a+b. It turns out that there is no other solution, because there are no pairs of Mutually Orthogonal Latin Squares of order 6 (link). This is some deeper combinatorics that we shall not delve into here.

We have seen that, for several combinations of table size and numbers of participants, we can create a situation where each visitor meets each other one exactly once over a series of table sittings. In the next section, we will look at the way that we can loosen these expectations in order to get workable solutions for more general situations.

Some non exact cases

In this section we will look at some nonexact solutions as well as some more general statements of the problem. Hopefully some of these will work out to be useful.

The first approximation is when we do not quite have enough people. Say we had a workshop set up for 25 people who will do 6 rounds of sitting at tables of size 5, using a resolvable (25,5,1) BIBD. Then two people get sick and do not turn up. The solution here is clear: we use the same seating arrangements, the same design, but some tables will only have 4 people on them, and at one point, one table will only have three people seated at it, because both the sick people would have sat here. How far can we push this idea? There is the danger that, if we only had 21 people, that one block contains all four of the missing persons, so we would have one person sitting by themselves at a table. This is not the sort of solution we want.

Here we find that some higher combinatorics comes into play. By looking at the intricacies of finite geometry, we find that some people have looked at transferring other ideas there from more classical geometry. One of those is the idea of an arc. We know that given two points in Euclidean geometry, we can find a unique line through them. Whereas three points do not necessarily lie on one line. If they do, then those three (or more) points are called collinear. One of the interesting properties of a circle is that any line intersects the circle in 0, 1 or 2 points, but not more. There are never three collinear points in a circle. This idea has been translated into finite geometries. A k-arc is a collection of k points so that no three of them are collinear.

We can use this idea to help us create more general solutions. For q even we can construct (q+2)-arcs, for q odd we can construct (q+1)-arcs. If we remove the points of an arc from our set of points representing participants, then we will remove at most two from any one table. This still means that with 9 participants, we might end up with a person sitting alone. But for q four or more, we get at least two people per table. We can have tables of 2,3,4 with 10-16 participants, tables of size 3,4,5 with 19 to 25 participants, tables of size 5,6,7 with 41 to 49 participants, tables of size 6,7,8 with 54 to 64 participants and tables of size 7,8,9 with 71-81 participants. And still get everyone to meet everyone else.

We noted above, that we often would need to have many rounds of table sittings in order for everyone to meet everyone else. Perhaps this is too many, perhaps we should be happy with fewer sittings. Thus we could relax our requirements so that we require only that no two people meet more than once at a table. We saw above that with 6 tables of size 6, we could only have 3 sittings without people beginning to sit with each other again. This would lead to a partial BIBD, so that we require that some people meet once and some do not meet. These are also called m-nets in the literature: we require only m sittings instead of the (v-1)/(k-1) that we need for all people to meet.

One last generalisation that is of value is to consider various table sizes. In workshops, while we often want people to work together on tables where good conversations can arise, so from 5 to 8 people per table, some exercises need smaller groups and others larger groups. There is a version of this problem that is referred to as the Oberwolfach Problem, named after a well known mathematical conference centre in Germany. In the cafeteria there are a number of tables of different sizes. The question has been posed, whether a symposium over several days can be so arranged, that each mathematician sits next to all the others once. This can be modelled as a graph covering problem, where we want to cover Kv, the complete graph on v vertices, with a number of cycle graphs. One could try to cover Kv with some other graphs representing the way beople can interact at a dining table. There are so many ways to think about this!

Sometimes this idea can work and be useful. Let us imagine we have 16 participants and have run 3 rounds of 4 people per table. We now want them to work in pairs to develop certain ideas. From the affine geometry described above, we can say that we would have needed 5 rounds of tables of 4 to have everybody interact. So we leave two rounds out and for simplicity, let us imagine they are the two rounds with horizontal and vertical “lines” representing the tables.

Two sitttings of 4 tables with 4 people on each
We can see one sitting as 4 copies of K4, written 4.K4, each copy being one table and K4 representing that each person is connected with each other person.

Then each person needs to work with the 3 other people in one row and the 3 other people in their column. So we need 6 more rounds of pairs. This can be easily done:

So one sitting of 4.K4 can be replaced by 3 sittings of 8.K2. The second sitting above can similarly be replaced by 8.K2, with all the graphs rotated 90 degrees.

This can be described as a graph covering problem. A table of size 4 can be seen as K4, the complete graph on 4 nodes, because all 4 of the people at the table have interacted. 4 tables of size 4 is then 4.K4. So our original problem of having 16 people all meet exactly once corresponds to the question whether we can cover K16 with 5 copies of 4.K4. Our new problem is whether we can cover K16 with 3 copies of 4.K4 and then 6 copies of 8.K2. And we see that we can.

Conclusion

Arranging people onto tables in an optimal fashion for interactions is difficult, but there are some mathematical tools that can help. We looked at the numerical restrictions and then some more aspects of solving the problem exactly. It turns out that, in order to do this exactly, there are strong restrictions on the numbers of people and the size of our tables.

Using arcs from finite geometry we were able to deal with a few less people than exact solutions would require. We also saw that we probably do not want to do all interactions, but can look at having people interact at most once and get some more flexible results. In the final section we looked at the possible more varied seating arrangements, which would probably arise in an actual workshop process.

Another requirement that becomes clear is that it is complex to organise such an arrangement of people. One solution might be to re-imagine a rather old fashioned idea, that of the dance card. While a lady in late 19th century Vienna, or 1930s Melbourne, collected the names of dance partners in a small, decorative dance card in the first part of an evening while attending a ball, the workshop version might indicate the places for each participant to move to or the table for a section of activities. This dance card would be handed out in the housekeeping or ice breaker section of the event. And it might be a nice souvenir.

Acknowledgements

The question has been floating around for a while when Nik Gaffney of Foam Earth made the topic relevant recently in a discussion. With any luck he might develop some software to implement at least part of the solution. Other colleagues such as Ariella Helfgott at Collaborative Futures have also prodded us to try and make these ideas more explicit. I would also like to thank Tim Penttila who introduced me to the ideas of arcs and other peculiar structures in finite geometries many years ago. I never thought they would be (for me) anything more than a technically interesting avenue of research.

These ideas were first presented at the LARD symposium at the Johannes Kepler University in December 2021.

This reflection is part of Curiouser and Curiouser, cried Alice: Rebuilding Janus from Cassandra and Pollyanna (CCA) a artbased research project from the Institute for Design Investigations at the University of Applied Arts Vienna und Time’s Up. It is supported by the Programme for Arts-based Research (PEEK) from Austrian Science Fund (FWF): AR561.

Leave a Reply

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 )

Connecting to %s