Michi’s blog » archive for 'Combinatorics'

Homological Inclusion-Exclusion and the Mayer-Vietoris sequence

  • January 9th, 2009

This blogpost is inspired to a large part by comments made by Rob Ghrist, in connection to his talks on using the Euler characteristic integration theory to count targets detected by sensor networks.

He pointed out that the underlying principle inducing the rule
\chi(A\cup B) = \chi(A)+\chi(B)-\chi(A\cap B)
goes under many names, among those \emph{Inclusion-Exclusion}, favoured among computer scientists (and combinatoricists). He also pointed out that the origin of this principle is the Mayer-Vietoris long exact sequence
\cdots\to H_{n}(A\cap B)\to H_{n}(A)\oplus H_{n}(B)\to H_{n}(A\cup b)\to\cdots

In this blog post, I’d like to give more meat to this assertion as well as point out how the general principle of Inclusion-Exclusion for finite sets follows immediately from Mayer-Vietoris.

Inclusion-Exclusion, and the passage from two sets to many

The basic principle of Inclusion-Exclusion says that if we have two sets, A and B, then the following relationship of cardinalities holds:
|A\cup B| = |A| + |B| – |A\cap B

This is a preview of Homological Inclusion-Exclusion and the Mayer-Vietoris sequence. Read the full post (1668 words, 131 images)

More on Lichtenstein

  • October 28th, 2008

It turns out that there is even more to say on the communes of Lichtenstein.

First of all, there is a 5-clique in the communal graph, as Brian Hayes pointed out. But there are two different excluded subgraphs for planarity – so if we aren’t looking specifically for the chromatic number, but rather how this graph fails to be a “normal” land map, we might want to see whether it realizes BOTH.

It turns out that it does.

The following are two highlighted versions of the Liechtenstein communal graph.


The embedded K5 with edges in blue.


The embedded K33 with blue and red vertices.

(105 words, 2 images)

On the chromatic number of Lichtenstein

  • October 28th, 2008

Following the featuring of the internal political structure of Lichtenstein on the Strange Maps blog, Brian Hayes asks for the chromatic number of Lichtenstein.

Rahul pointed out that I made errors in transferring the map to a graph. Specifically, I missed the borders Schellenberg-Eschen and Vaduz-Triesen. The post below changes accordingly.

Warning: This post DOES contain spoilers to Brian’s question. If you do want to investigate it yourself, you’ll need to stop reading now. Apologies to those on my planet feeds.

As a first step, we need to build a graph out of it. I labeled each region in turn with the exclaves numbered higher than the “main” region of each organizational unit. And then I build a .dot file to capture them all:

This is a preview of On the chromatic number of Lichtenstein. Read the full post (580 words, 4 images)

High school topology restarting

  • November 16th, 2007

Today, I told my two bright students about abstract and geometric simplicial complexes, about the boundary map and the chain complex over a ring R associated with a simplicial complex Δ, and assigned them reading out of Hatcher’s Algebraic Topology.

The next couple of weeks will be spent doing homology of simplicial complexes, singular homology, equivalence of the two, neat things you can do with them; and then we’ll start moving towards a Borsuk-Ulam-y topological combinatorics direction.

I might end up pulling combinatorics papers from my old “gang” in Stockholm on graph complexes, and graph property complexes, and poke around those with them.

(104 words)

Enumerating the Saneblidze-Umble diagonal in Haskell

  • June 11th, 2007

IMPORTANT: Note that the implementation herein is severely flawed. Do not use this.

One subject I spent a lot of time thinking about this spring was taking tensor products of A∞-algebras. This turns out to actually already being solved – having a very combinatorial and pretty neat solution.

Recall that we can describe ways to associate operations and homotopy of associators by a sequence of polyhedra Kn, n=2,3,.., called the associahedra. An A∞-algebra can be defined as being a map from the cellular chains on the Associahedra to n-ary endomorphisms of a graded vector space.

If this was incomprehensible to you, no matter for this post. The essence is that by figuring out how to deal with these polyhedra, we can figure out how to deal with A∞-algebras.

This is a preview of Enumerating the Saneblidze-Umble diagonal in Haskell. Read the full post (2258 words)

looksay – today’s Haskell snippet

  • April 18th, 2007

nextLookSay = foldr (\xs -> ([length xs, head xs]++)) [] . group
lookSay = iterate nextLookSay [1]
 

Conway’s Look-and-say sequence

(23 words)

Borsuk-Ulam and West Wing

  • February 7th, 2006

In West Wing 4×20, CJ states that there are two antipodal points with identical temperature on the earth, as an argument why it should be possible to imagine that an egg could stand on its end at the spring equinox. This particular plotline also has her most emphatically claiming that this should not be possible at the autumn equinox. Why this particular physics is complete idiocy will be left as an exercise to the interested reader, and instead I will focus on the other claim.

This is, in fact, true. It’s a corollary to one of the prettiest theorem conglomerates I have ever seen: the Borsuk-Ulam theorem(s). Alas, I haven’t got my sources on it here at the moment, so I won’t give you the deep indepth survey I want to give; but I do want to give a bit of overview as to why the claim CJ supports her insane theory with is actually true.

This is a preview of Borsuk-Ulam and West Wing. Read the full post (609 words, 15 images)

post navigation
about
Michi is a recent PhD working in homological algebra and applied algebraic topology. This blog is his outlet for texts with some manner of thought put into them. Over at his LiveJournal intimate details and streams of consciousness might be found.
Not all here is mathematics. All here, though, are my personal thoughts and opinions. Please read the about page (linked above) for more details.
This blog uses statcounter.com for logging and traffic analysis. In order to identify return visitors, this site will issue a cookie on viewing the blog.
RSS Travel plans
Recent Comments
Tags
Categories
Blogroll
Family
Mathematician blogs
Archives
the rdc* theme