The n-Category Café

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.

Let C be the complex that some guy on the street described (with the proviso that m and n are positive). Let M be the intersection of C with the simplex spanned by the set of all men, and W the corresponding intersection for women. David Speyer’s calculation showed that these three complexes have equal Euler characteristic.

Let D be the subcomplex of M x W given by a union of products of simplices, such that the product of simplices (m,w) is in D if and only if the vertices of m lie in M, and the vertices of w lie in W, and the union lies in a simplex of C. There are surjective “forget men” and “forget women” maps from D to W and M, respectively, and the fibers are contractible, since they are simplices. C is (topologically) the union of the mapping cylinders glued along D, so all four spaces are homotopy equivalent.

Yay! Scott Carnahan’s solution is very nice, especially because it uses a nontrivial (though basic) result in topology to crack a combinatorics problem. Namely, this version of Whitehead’s theorem: “a map between simplicial complexes with contractible fibers is a homotopy equivalence”.

I guess now is the time to reveal Gavin Wraith’s own solution to the puzzle, which is essentially identical to Scott’s:

Proof. We construct three simplicial complexes $M$, $W$ and $K$. The simplices of $M$ are discussive sets of men, and those of $W$ the discussive sets of women. The vertices of $K$ consist of both men and women, and its simplices are those sets in which each man and each woman in the set have danced together at the ball. There are evident “forgetful” projections

$$M \leftarrow K \rightarrow W.$$

They both have contractible fibres, whence $M$ and $W$ have the same homotopy type, hence the same Euler-Poincaré characteristic.

Slick, eh?

This is an old theorem of Dowker’s on the homology of a relation. Annals of Math. 1952. It can be used to prove the Nerve Lemma.

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

As befits his name, Gavin Wraith is a ghostly visitor to the $n$-Café, who is able to see everything going on, but unable to make himself visible. I receive communications written on slips of pale yellow paper that appear mysteriously in the kitchen next to the espresso machine. And I bring them to you, the customers, along with your checks:

Suppose you have categories $M$ and $W$ and a presheaf $D$ (dances in the Grand Ball?) on $M \times W$. Let

$$p : M\times W \to M, q: M \times W \to W$$

be the projections. Composition with p gives a functor

$$p^* : M\tilde{} \to (M \times W)\tilde{}$$

with right adjoint $p_*$, and similarly for $q$ (I write $C\tilde{}$ for the category of contravariant set-valued functors on $C$, following tradition). We get geometric morphisms

$$M\tilde{}/p_*(D) \leftarrow (M\times W)\tilde{} /D \rightarrow W\tilde{}/q_*(D)$$

induced by $p$ and $q$. These are homotopy equivalences of toposes. To check this for $p$ it is enough, by devissage, to verify isomorphism in cohomology of dimension 0. This is a triviality: for $X$ in $M\tilde{}$ and a natural map $X \to p_*(D)$, we have by adjointness $p^*(X) \to D$ in $(M\times W)\tilde{}$, and vice versa.

This is hardly new and appears in various guises in SGA. Can your readers disentangle this into some categorified version of Dowker’s theorem?

I get lost somewhere around ‘devissage’.