Ordering people with friendship constraints

Solution 1:

Note: This is NOT a full answer; just two upper specific bounds.

Let $f(k)$ denote the greatest value of $n$ for which a good order is guaranteed to exist. Then:

We have $f(2)<6$, since the friendship graph consisting of three pairs of people: {0,1}, {2,3} and {4,5}, where each person from each pair is friends with each person from the next pair (with last pair wrapping back to the first one) admits no good order. More explicitly:

  0 => [2,3];  1 => [2,3];  2 => [4,5];  3 => [4,5];  4 => [0,1];  5 => [0,1]

This graph is nicely regular, which simplifies the analysis considerably. Without loss of generality, the first person in line is person $0$. Its two friends, $2$ and $3$ must be placed right behind (their relative order doesn't matter; it can be $2$ without loss of generality). However, this means at least one of their friends ($4$ and $5$) would be too far to be heard.

We also have $f(3)<9$, as demonstrated by the following friendship graph (with persons numbered $0$ to $8$) in which every person is friends with the next one (wrapping back from $8$ to $0$), plus the following friendship relations:

  0 => 5; 1 => 7; 2 => 0;   3 => 8; 4 => 1; 5 => 3;   6 => 2; 7 => 4; 8 => 6

Unfortunately, I have not managed to represent this graph in a very neat, regular structure like the previous one (although it can still look relatively nice if represented as a $3\times 3$ grid). As such, I have not managed to produce an easy proof of its desired no-good-order property; having only verified it via computer-based exhaustive search (which, of course, could have been implemented incorrectly; feel free to verify it independently).

A wild extrapolation might suggest $f(k)<3k$, although this is only a very wild guess.