Combinatorics for lunch

TL;DR

I need help from the mathematics community, specifically from people who have worked in, or are currently working in, the field of combinatorics.

With their help, I am looking to answer the following questions:

• Does the following type of Latin square have a name in the literature?

• Does the following type of Latin square have a name in the literature?

Finally, for these ‘types’ of Latin Squares (those having the prior two types of constraints):

• How many solutions are there for any even order n square?

• What are some efficient ways of sampling the solutions (again, ensuring the constraints are observed)?

I’ve vetted the questions with a combinatorialist already (thank you cammie.tech) - so I believe these to be valid and (hopefully) interesting. If you can connect me with anyone who maybe able to help, please drop me a note here:

dragster [dot] riveting138 [at] mailer [dot] me

If you read the above request for help - thank you!

If you’re interested in what it means, and how I got here, read on.

The gift that keeps on giving

Once upon a time I helped run something called Lunch Roulette. It was the worlds simplest web resource for connecting people, randomly, over lunch. If you worked at one of our Lunch Roulette customers firms, and wanted to meet random co-workers, you’d sign up via the Lunch Roulette web site and then, with some frequency of the customers choosing, you’d be paired with a random co-worker to meet for lunch: your experience of lunch roulette as a participant was a series of 1-on-1 meetings with random co-workers that took place over the course of several weeks/months/years.

You can read a little more about it here. Oder hier, wenn Sie Deutsch lesen.

Sometime during my involvement with Lunch Roulette I was sat in a coffee shop in NYC doodling in a notebook. I was thinking about the process we had in place, of each (say) week determining a random match for someone and I got to wondering if, instead, there weren’t a way to just pre-plan people’s meeting experiences. Could I put all the participants name’s into a virtual ‘pot’ and just pull them out such that their ‘trajectories’ were predetermined, all at once, in one go (also, to be clear, by ‘trajectory’, I mean the set of meetings they would engage in over their participation in the program).

I can make this super clear with an example. Welcome to ACME CORP. a vibrant tech. startup with 4 employees:

In a surprising use of valuable startup dollars, ACME CORP. decide to use a Lunch Roulette like mechanism to randomly pair employees over a course of 1-on-1 meetings. Three such meeting events take place:

During Meeting 1, colleague 1 meets with colleague 2, and colleague 3 meets with colleague 4.

During Meeting 2, colleague 1 meets with colleague 3, and colleague 2 meets with colleague 4.

During Meeting 3, colleague 1 meets with colleague 4, and colleague 2 meets with colleague 3.

Over the course of 3 meetings, each employee has met every other employee exactly once. I realized, in that coffee shop, that I could write this same information a little differently:

The first column contains the ‘person’ (or colleague), and the next three columns contain who that person will meet with. So, if we follow along the first row, the first entry is colleague 1, the second entry of the first row is the first person colleague 1 lunches with (colleague 2), the third entry of the first row is the second person colleague 1 lunches with (colleague 3), and so on.

Now, because that first meeting has colleague 1 meeting with colleague 2, colleague 2 has to be meeting with colleague 1 at the same time. This means that the second entry of the second row has to correspond to the first person colleague 2 meets with (which is colleague 1). The fact that they are unique people and can only be in 1 place at 1 time, imparts structure to the possible solution.

Hopefully this 4 person example is pretty straightforward, but it gets pretty hairy pretty quickly. What about 8 colleagues? What does that look like? Can you write down an 8 person solution that’s consistent with the constraints described above? No worries if not, just click the button below … and then come back for more!

If you tried it yourself, you’ll know that the exercise of filling this out may have felt a lot like completing a Sudoku puzzle. I began to wonder if I couldn’t draw from what was known about Sudoku to help provide me with a general solution to the problem I’d started with.

It’s all latin to me

Turns out, Suduko is a special case of something called a Latin square. What’s a Latin square I hear you dribble? Well, a Latin square consists of sets of the numbers 1 to n arranged in such a way that no row or column contains the same number twice. Latin squares turn up in all kinds of things - design of experiments, error correcting codes etc. Read more, as I did, here.

As you might expect, a lot is known about Latin squares. And, as is the way, as a thing is studied, it is named. It seems that:

• A Latin square with 1s along the main diagonal is called a ‘fixed diagonal’ Latin square

• A Latin square with the first row and column given by {1, 2, …, n} is referred to as a ‘normalized’ Latin square

Because of this, the ‘easiest’ (and first) of my questions to the mathematics community posed above can be refined to be:

• Is a Latin square with 1s along the main diagonal and the first row and column given by {1, 2, …, n} a ‘normalized fixed diagonal’ Latin square’? (Of course, if it is not, my question still stands, what is it called?)

As I played with filling out these Latin squares of various sizes. I noticed that I could always generate a valid solution (for the squares I explored), such that not only did I have 1s along the main diagonal and the first row and column given by {1, 2, …, n}, but that the final column, when read from top-to-bottom, could be organized {n, …3, 2, 1}. This prompted my second question to the combinatorics community: What would that type of Latin square be called?

And then, outside of naming, I was interested in knowing, subsequent to either of those two constraints, how many such Latin squares there were. There are general formulas for the number of normalized Latin squares (you can find references for those in this link and here), but I couldn’t find specific formulas for the more constrained squares that corresponded to the physical act of participating in something like ‘Lunch Roulette’. As a general boggle to the mind, for n=8 there are 535,281,401,856 normalized Latin squares, although it seems with such phenomenally large numbers being involved, just the act of enumeration becomes a bit challenging (see here, for example).

The final question of interest is, for a Latin square of even order n that satisfies either of the above two ‘Lunch Roulette’ constraints, is there a ‘fast’ way of generating an example square? I’m thinking of something akin to this.

I genuinely think this is quite interesting: for a fictitious company, containing an even number n colleagues, who are to meet each other once and only once as part of a ‘lunch roulette’ like activity taking place over n-1 meetings, such a meeting pattern can be constructed from a Latin square of order n such we have 1s along the main diagonal and the first row and column given by {1, 2, …, n}, with an additional optional constraint that the final column, when read from top-to-bottom, could be organized {n, …3, 2, 1}.

Hopefully I’ve explained this clearly enough that someone knowledgeable in the field could help point me in the direction of answers to my questions (as it’s highly likely that this is all known, and exists in the literature somewhere). I just need to find those folks, and hope that they’re generous enough to contribute!

If there’s any kind of epilogue to this story, I’ll be sure and make another follow up post.