Thanks, John and Gavin, for a nice puzzle. Surely Gavin’s solution is

the final word in elegance. The following post-final remarks are just

footnotes.

Unless I misunderstand something — that happens quite often — the

complex K is a special case of a hom complex, a central notion in a

long tradition of topological methods in graph theory.

One thing I possibly misunderstood is the complex K itself: as far as

I can see it is not a simplicial complex as claimed but only a

polyhedral one (which is just as good for the argument). This is

because its vertices are not single women or men but couples

consisting of one woman and one man, since otherwise you could not

project onto the simplicial complexes of women and men. So the cells

of K are not simplices but products of simplices. An illustrative

example is the situation where there are 3 women, 2 men, and everybody

has danced with everybody else of the opposite sex. Then K is the

3-dimensional prism.

If this interpretation of K is correct, then K is a basic example of a

hom complex. Namely with G the (directed, non-reflexive) incidence graph

of the ball, we have

K = Hom([1],G).

Here G is the graph with an edge from a man to a woman if they have

danced together, and [1] is the graph 0 -> 1. For this to be true we

need a directed version of the notion of hom complex, whereas the

classical version is non-directed. Let me treat the classical notion,

then K will be precisely half the hom complex.

Here is the classical definition: for (non-directed, non-reflexive)

graphs T and G, the hom complex Hom(T,G) is the polyhedral complex

whose cells are indexed by functions f: V(T) -> P^+(V(G)), such that

for every edge xy in T, every vertex belonging to f(x) is connected to

every vertex belonging to f(y). Here P^+(S) denotes the set of

non-empty subsets of S. The dimension of a cell f is the sum over v in

V(T) of the cardinalities of the sets f(v) minus the cardinality of

V(T). So the 0-cells are precisely the graph maps T -> G. (The

1-cells are the maps from V(T) to 1-or-2-element subsets of V(G) such

that precisely one vertex of T is sent to a 2-element set, all the

others to 1-element sets, subject to the condition. Etc.) Hence each

cell is a product of simplices indexed by V(T), and the imposed

condition selects which products are in.

Now take T=K_2, the complete graph on two vertices, u and v. For G

the incidence graph of the ball (the usual undirected one), Hom(K_2,G)

is twice K: indeed every cell in K appears twice in Hom(K_2,G) since

the two vertices in K_2 can be interchanged.

Now in general, for a graph G, not assumed to be bipartite, Hom(K_2,G)

is the complex of complete bipartite subgraphs.

Here is another classical complex: The neighbourhood complex N(G) is

the simplicial complex whose simplices are the subsets whose elements

have a common neighbour. Hence when G is the incidence graph of the

ball, N(G) = W + M, the complex of all discursive sets. Now for a

general graph we have:

Lemma (Babson and Kozlov): the natural map Hom(K_2,G) -> N(G)

sending f to f(u) is a homotopy equivalence.

The proof is a variation on the theme of contractible fibres. More

formally I think you work with the face posets and apply Quillen’s

theorem A.

Now we can derive something similar to Gavin’s solution from the

lemma by observing that when G is the bipartite graph of women and

men at the ball, the obvious involution on Hom(K_2,G) interchanges

the role of women and men, hence via the homotopy equivalence

interchanges W and M, hence these two complexes must have the same

homotopy type.

(As I said, this is not to compete with Gavin’s argument, just to try

to put it in some perspective. Meta-puzzle: use hom complexes to

construct more complicated puzzles in the style of Gavin’s.)

A few historical remarks: the neighbourhood complex was introduced by

Lovasz in the 1970s in order to prove the Kneser conjecture with

topological methods (which he did). The conjecture (going back to the

1950s) says: For n at least 2k, the chromatic number of the Kneser

graph K_{n,k} is n-2k+2. (The Kneser graph has the k-subsets of n as

vertices, two vertices being incident if the subsets are disjoint.

The chromatic number is the least number of colours needed to colour

the graph (cf. the four-colour problem).) The main ingredient in

Lovasz’s proof is this theorem (Lovasz): If N(G) is k-connected, the

chromatic number of G is at least k+3. Lovasz went on to introduce

hom complexes, and stated the following conjecture: Let G be a graph

and let C be any odd cycle (but not a loop). If Hom(C,G) is

k-connected then the chromatic number of G is at least k+4. The

conjecture was proved recently by Babson and Kozlov, Ann. Math. 2006

— using Stiefel-Whitney classes and spectral sequences and such

frivolous techniques :-)

Cheers,

Joachim

## Re: A Puzzle From Gavin Wraith

For i, j >= 1, let $C_{ij}$ be the number of pairs (M, W) where M is a set of i men, W is a set of j women and every member of i has danced with every members of j. We claim that both sums are equal to

$\sum (-1)^{i+j-1} C_{ij}$.

To see this, group together all the terms coming from the same set M. If M is not discussive, there are no such terms. If M is discussive, let P be the set of women who have danced with every member of M. Then (M,W) appears in the above sum if and only if W is a subset of P.

The total contribution from M is then $\sum_{j=1}^{|P|} (-1)^{|M|+j-1} \binom{|P|}{j} = (-1)^{|M|-1} - (1-1)^{|P|+|M|-1} = (-1)^{|M|-1}$

So each discussive set $M$ of men contributes $(-1)^{|M|-1}$, as desired.