Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is a conference with $2n+1$ meetings between $6n+1$ professors. The tables in the conference room are round such that one has $4$ seats and the remaining $n$ tables have $6$ seats each. We know that for any two professors, the number of times they sit opposite to each other plus the number of times they sit next to each other does not exceed $1$.

$1.$ Is such a conference possible if $n=1$?

$2.$ For what values of $n>1$ is such conference possible?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

It works for all $n \geq 1$, and can be constructed by near 1-factorisations. (I'm going to assume the "$6n+1$ professors" is a typo for $6n+4$, when all the seats are filled. If not, then just kick three people out of the conference, and the result is still true.)

Label the professors $x$ and $y_{ij}$ for $1 \leq i \leq 2n+1$ and $1 \leq j \leq 3$.

Let $F=\{F_1,F_2,\ldots,F_{2n+1}\}$ be a near 1-factorisation of $K_{2n+1}$ (which exist for all $n \geq 1$; see my answer here for a proof). We will interpret each $F_i=\{a^{(i)}_t b^{(i)}_t\}_{t=1}^{2n}$ to be a set of $2n$ edges between vertices in $\{1,2,\ldots,2n+1\}$.

At meeting $i \in \{1,2,\ldots,2n+1\}$:

  • At the 4-seater table we seat $\{x\} \cup \{y_{ij}\}_{j=1}^3$ where $i$ is the element in $\{1,2,\ldots,2n+1\}$ that is not in an edge in $F_i$.

  • At the $t$-th 6-seater table we seat $\{y_{a^{(i)}_t j}\}_{j=1}^3$ in the three "even" seats $\{y_{b^{(i)}_t j}\}_{j=1}^3$ in the three "odd" seats.

If two professors sit next to, or adjacent from, each other more than once, then $F$ is not a near 1-factorisation.

Here's a drawing for the $n=1$ case:

An $n=1$ example.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.