July 16, 2009

A Puzzle From Gavin Wraith

Posted by John Baez Gavin Wraith proposed this puzzle for the $n$-Café:

Problem: Suppose we are given two finite sets, say one of men, the other of women, and a relation — e.g. a Grand Ball at which men and women dance in couples. After the ball the men like to discuss the women and the women the men. Let us call a group “discussive” if there is a person of the opposite sex with whom each member of the group has danced at the ball. Let $M_n$ be the number of discussive groups of $n$ men, and $W_n$ the number of discussive groups of $n$ women. Show that the alternating sums

$M_1 - M_2 + M_3 - \cdots$

and

$W_1 - W_2 + W_3 - \cdots$

are equal.

His solution is wonderfully high-powered and abstract, which is why he thought it would amuse us. He wrote:

Programmers have their obfuscated code competitions. At school we had a similar kind of thing proving elementary results of Euclidean Geometry using projective geometry and only at the last minute whipping out of the hat the circular points at infinity. I am afraid this kind of thing left me with the taste for frivolity that I still have.

But instead of just telling you his solution, I’ll let you take a crack at it yourself first!

Posted at July 16, 2009 8:52 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2016

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.

Posted by: David Speyer on July 16, 2009 10:15 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

Very nice, David!

So, the high-powered proof is not necessary… but it’s still fun. Perhaps instead of giving it away, I’ll just try to nudge people towards it.

Hint: the alternating sums $M_1 - M_2 + M_3 - \cdots$ and $W_1 - W_2 + W_3 - \cdots$ should remind us of something.

Posted by: John Baez on July 17, 2009 2:16 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

Euler characteristic?

Posted by: David Corfield on July 17, 2009 3:13 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

Well, I was thinking of declaring a simplicial complex generated by having an $(m+n-1)$-simplex for every set of $m$ men and $n$ women, for whom the “danced-with” relation is a $K_{m,n}$ — NOT an Eilenberg-Mac_Lane space! — with the obvious generating inclusions. And then the subcomplex only meeting men is (geometrically) a deformation retract of the complement of the subcomplex meeting only women; vice-versa, similarly. I’m feeling afraid that I’ll have to take the barycentric decomposition of something ~ ~ ~ but really I ought to be grading exams!
Posted by: some guy on the street on July 17, 2009 3:52 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

You’re definitely on the right track: a simplicial complex is just a fancy name for a set $X$ equipped with a collection of finite subsets $S \subseteq X$ with the property that if $S$ is in the collection, so is any subset of $S$. To crack this problem, we should prove that two simplicial complexes are homotopy equivalent and thus have the same Euler characteristic.

I’m feeling afraid that I’ll have to take the barycentric decomposition of something…

Gavin Wraith’s proof is very elegant; no need for barycentric subdivision.

When you do it his way, you really feel that all those courses on homotopy theory weren’t a waste of money after all!

Posted by: John Baez on July 17, 2009 4:04 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

To crack this problem, we should prove that two simplicial complexes are homotopy equivalent and thus have the same Euler characteristic.

So you’re getting us to think of a male and a female simplicial complex of discussive groups. But why are these complexes homotopy equivalent?

Looks like one is the dual simplicial complex of the other.

Posted by: David Corfield on July 17, 2009 6:21 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

David C. wrote:

Looks like one is the dual simplicial complex of the other.

If you’re right, my somewhat displeased reaction to somebody’s mention of ‘barycentric subdivision’ might have been sort of dumb.

Posted by: John Baez on July 17, 2009 6:43 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

Maybe it’s a bit trickier.

Posted by: David Corfield on July 17, 2009 7:16 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

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.

Posted by: Scott Carnahan on July 18, 2009 6:33 AM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

I was just thinking that to reduce any perceived heteronormativity of the math puzzle corpus, we could call the sets Jets and Sharks. I already have a strong mental association between those names and dancing.

Posted by: Scott Carnahan on July 18, 2009 8:03 PM | Permalink | Reply to this

heterodox!

An off-topic remark deserves an off-topic reply;

As I understand it, the notion of “Heteronormativity”, and fear of its referent, can be a dangerous meme tending to ignore various basic facts of anthropology (I’m humpty-dumptying this to mean “human nature”), with potential consequences undermining society in general.

I don’t mean to suggest that dancing is fundamentaly an activity shared by one man and one woman; that would be silly and ignorant. Nonetheless, I believe some important things are precisely an activity shared by one man and one woman, and that this is a Good Thing.

Posted by: some guy on the street on July 24, 2009 5:23 AM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

Now that we’ve heard from both sides on this issue, further discussion of heteronormativity, what Spencer and Tracy did later that night, and so on, will be deleted.

Posted by: John Baez on July 24, 2009 8:33 AM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

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?

Posted by: John Baez on July 18, 2009 1:01 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

That’s a very elegant proof of the statement. Completely useless to generalize or to understand the dynamics between men and women, but nifty all the same.

Posted by: Haelfix on July 19, 2009 8:50 AM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

Actually you are very wrong on that, Haelfix! Strangely enough Dowker’s ideas were the basis for R. Atkin’s introduction of what is known as Q-analysis in the social sciences. Some of what has been written on that area is fairly empty of content, but analysis of social networks, traffic, and loads of other areas have been applications of the basic representation of a relation as a simplicial complex and the use of quite elementary techniques of algebraic topology in those areas.

Posted by: Tim Porter on July 20, 2009 10:36 AM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

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.

Posted by: Robert Ghrist on July 18, 2009 10:59 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

The result of Dowker is mentioned in the nLab entry on the Vietoris complex:

I have always considered that to be a very beautiful and important result.

I hope to include more precise details and a proof in a subsequent nLab entry.

Posted by: Tim Porter on July 19, 2009 10:32 AM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

I added a link from the $n$Lab entry to this puzzle by Gavin Wraith. Unfortunately that entry does not state Dowker’s theorem. Does that theorem say that the two simplicial complexes coming from a relation are homotopy equivalent? (In the $n$Lab you call them $V(R)$ and $C(R)$). If so, I guess the proof was sketched by Gavin.

Posted by: John Baez on July 19, 2009 11:05 AM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

Yes, that is the right result but Gavin’s proof is not the same as Dowker’s.

Dowker’s proof is that there are two maps from the double subdivision of one back to it, one is a sensible subdivision map the other uses the other complex. The two maps are contiguous so this sandwiches the homotopy type of the second complex neatly.

Posted by: Tim Porter on July 19, 2009 12:37 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

I have put a version of Dowker’s proof on the nLab.

The detailed reference for the original is

C. H. Dowker, Homology Groups of Relations , Annals of Maths, 56, (1952), 84–95

http://ncatlab.org/nlab/show/Dowker%27s+Theorem

Posted by: Tim Porter on July 19, 2009 9:55 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

The result that Gavin used together with essentially that proof was also used to good effect in a paper by Abels and Holz, `Higher generation by Subgroups’ J. Alg. 160 (1993)310 - 341.

Their results gave new information on generation of linear groups and may be of interest to readers of other threads in this Café. They used homotopy colimit techniques and could calculate information on resolutions of a group by examining the homotopy colimits of resolutions of a covering family of subgroups.

Posted by: Tim Porter on July 21, 2009 3:13 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

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(,G).

Here G is the graph with an edge from a man to a woman if they have
danced together, and  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

Posted by: Joachim Kock on July 21, 2009 2:41 PM | Permalink | Reply to this

Re: A Puzzle From Gavin Wraith

A propos to my previous post, there was just today a new preprint on hom complexes and graph colourings:

Dochtermann and Schultz:
Topology of Hom complexes and test graphs for bounding chromatic number
(arXiv:0907.5079)

It contains an interpretation of hom complexes in terms of enriched categories.

I also came across two papers by Zivaljevic, which combine the theory of hom complexes with some of the keywords of this blog, like holonomy and parallel transport:

Combinatorial groupoids, cubical complexes, and the Lovasz conjecture (arXiv:math/0510204)

Parallel transport of $Hom$-complexes and the Lovasz conjecture (arXiv:math/0506075)

Cheers,
Joachim.

Posted by: Joachim Kock on July 30, 2009 8:25 AM | Permalink | Reply to this

Categorified Dowker?

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’.

Posted by: John Baez on July 21, 2009 10:49 PM | Permalink | Reply to this

Re: Categorified Dowker?

Gavin responds:

By “devissage” I mean that if two functors are naturally isomorphic their right-derived functors are too. If $p : A \to B$ is a geometric morphism of toposes, we have a natural map

$Hom_B(1,X) \to Hom_A(1,p^*(X))$

given by applying $Hom_B(1,-)$ to the unit of the adjunction $p^* -| p_*$ at X. This is the map

$H^0(p,X) : H^0(B,X) \to H^0(A,p^*(X))$

If it is an isomorphism for all $X$ then we can deduce that $H^n(p,X)$ is an isomorphism for all $n$, and a fortiori an isomorphism for constant $X$. Hence $p$ is a homotopy equivalence.

Posted by: John Baez on July 22, 2009 8:20 AM | Permalink | Reply to this

Re: Categorified Dowker?

At this point in this delightful ‘sarabande’, can I suggest another interesting query?

We had a lot of discussion, last November, in the Café on Euler characterisitics, cardinality etc. and their categorification. Taking a ‘leaf from that book’, or whatever the analogous ‘modern’ e-based version of that phrase is, what about introducing some more probabilistic aspect into the dance.

The context could be rewritten to replace the relation by a binary Chu space

$M\times W \to \{0,1\}$

and then generalised by whatever $K$-valued Chu space you like. (Put your favorite structure on $K$. I will just give a fairly ‘classical’ instance and take $K = [0,1]$ with some sort of $t$-norm as one finds in Pattern Recognition, or with its monoid structure if you want some definite choice.)

You can form the simplicial complexes (almost), but the fun thing is that whilst in the original problem we had an simplex was either there or not, we now have a ‘probability’ that is there. (I leave you to imagine what the interpretation is for the dancers, perhaps there are several identical twins amongst the men so the women are not certain who they danced with!)

Here ‘probability’ is not intended in any definite sense because I did not put any definite restriction on the structure of $K$.

The question is then can we find a useful relation between some invariants of the M and W structures.

(Similar structures have been studied, I think, in the theory (and application) of concept lattices, and also by some people working in artificial intelligence.)

On another tack, we could replace the relation by a span and think of things in terms of enriched categories, categorifying as we go. That is not that far away from my $K$-based idea once we pass to generalised metric spaces à là Lawvere.

Posted by: Tim Porter on July 22, 2009 8:20 AM | Permalink | Reply to this

Post a New Comment