This is a short note of something that I wasn’t sure whether it is true for infinite graphs. Let be any simple, undirected graph, finite or infinite, such that . By we denote the complement of .
Proposition. At least one of is connected.
Proof. If has only 1 element, the statement is trivially true. So suppose that . Let and let be a bijection. Suppose that neither nor is connected. It is easy to see that this implies that there is a smallest such that the induced subgraph on the set has the property that neither nor its complement is connected.
Case 1. has no neighbors in the graph . But then is connected to every vertex in , so is connected, contradicting our assumption.
Case 2. has no neighbors in the graph . Same contradiction as Case 1.
Case 3. has neighbors in the graph as well as in the graph . We know that at least one of and is connected. We may assume that is connected. But since there is an edge from some point in to by assumption of Case 3, we know that is connected, contradicting our choice of .
Remark. The above proof used the well-ordering principle, which is equivalent to the Axiom of Choice (AC). It would be interesting to know whether the statement of the proposition above implies (AC).
Update. Will Brian gave a neat proof of the proposition above without using the Axiom of Choice, so the proposition does not imply (AC).
Encouraged by Eric S. Raymond’s book The Art of Unix Programming I have started using ed. My affection for it keeps growing. To begin with, it is the prime example of minimality, a property that is cherished all over the Unix world (Windows people don’t care about minimality). Also, ed is part of the POSIX standard, so you will find it on virtually every Un*x-like system. It is the standard text editor of Un*x.
Its famously terse interface teaches you a mental discipline that I find helpful in creating files, and I find that my .tex files (math texts, letters, or otherwise) do get more concise when I use ed to edit them.
Moreover, ed is (almost) orthogonal, which means that for many tasks there is *one* way (or very few ways) to do the task. In other editors, such as emacs or vi you have dozens of ways to do things, and you have no chance of remembering all commands. In ed, there are just essentially 24 commands (and you can do almost everything with a subset of 13 commands) every one consisting of a single letter, plus some arguments. You can’t get terser than that!
Also, using ed primarily, you are outside the raging editor wars (usually vi vs emacs), and, in some ways, *above* them. Oh – just one more thing: have you ever wondered what editor the source code of Unix itself was written in…?
Ein Ereignis ist in diesen Sommertagen etwas in Vergessenheit geraten: Vor 2500 Jahren hat der Grieche Heliotides die Sonne entdeckt. Aus heutiger Sicht schwer zu glauben, dass diese Entdeckung eines grossen Kopfes bedurfte – aber schliesslich hatte es auch einen Pythagoras gebraucht, damit wir heute Zahlen haben, mit denen wir Rechnungen im Restaurant begleichen koennen.
Heliotides wurde uebrigens fuer seine Entdeckung in den Stand eines Gottes erhoben. Dies hat das Gewicht von etwa 3 heutigen Nobelpreisen. Schon die Griechen konnten bahnbrechende Entwicklungen in der Grundlagenforschung richtig einordnen.
Mit einem “Cheers!” an den Postillon.
Homogeneous spaces are topological spaces that locally look everywhere the same. Put in mathematical terms, is homogeneous if for any there is an isomorphism
such that .
We can generalize this by not restricting ourselves to a pair of points in the following way:
Let be a cardinal and let be a topological space. We say that is
1. , and
2. whenever are subsets with and is a bijective map, then there is a homeomorphism such that .
A natural question is now to ask whether for cardinals we have
that there is a space that is -homogeneous, but not -homgeneous.
Joel David Hamkins gave this wonderful partial answer, pointing out that the disjoint union of 2 circles is 1-homogeneous but not 2-homogeneous; and moreover that is
2-homogeneous but not 3-homogeneous.
Interestingly, neither Joel nor another mathematician, Andreas Blass, who wrote several comments on Joel’s post, could figure out how to continue from there – which gives rise to the following
Open problem: For integers , are there spaces that are -homogeneous, but not -homogeneous?
(The question has a positive answer given in Joel’s post for cardinals .)
Let be a finite, simple, undirected graph. Hadwiger’s conjecture states that
if then is a minor of .
Let’s call that statement (Hadw). We show that it is equivalent to the following statement:
(Hadw’): If is not a complete graph, then there is a minor of such that
- , and
It is clear that (Hadw) implies (Hadw’). For the other direction, take any finite graph and let . If is complete, we are done. If not, use (Hadw’) and let be a proper minor such that . If is complete, we are done, otherwise use (Hadw’) again to get a proper minor of with . And so on. Since is finite, this procedure is bound to end at for some . We
have , and since the procedure ended at , the graph must be complete. So we get statement (Hadw).