Ode to ed (Unix standard text editor)

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…?

Posted in Uncategorized | Leave a comment

Coloring connected Hausdorff spaces

Motivation. I stumbled over the following hypergraph coloring concept when reading about an old (and open) problem by Erdos and Lovasz. Let H=(V,E) be a hypergraph such that for all e\in E we have |e| > 1, and let Z \neq \emptyset be a set. Then a map c:V\to Z is said to be a (hypergraph) coloring if for all e\in E the restriction c|_e is not constant (that is, the vertices pertaining to any edge are colored with more than 1 color). Trivially, for any nonempty hypergraph with no singleton edges, the identity map \text{id}:V\to V is a coloring. The chromatic number of a hypergraph with no singleton edges is the least cardinal \kappa such that there is a coloring c:V\to \kappa.

Equivalent topological formulation. If (X,\tau) is a connected Hausdorff space such that |X| > 1, we can use this to color the associated hypergraph (X,\tau\setminus\{\emptyset\}). (Indeed we can apply it to any topological space without isolated points.)

We can reformulate this in topological terms in the following way: Let (X,\tau) be a connected Hausdorff space. We define the nowhere dense covering number \nu(X) to be the minimum cardinality of a set {\cal N} of nowhere dense subsets of X such that \bigcup {\cal N} = X. It is not hard to see that \nu(X) equals the chromatic number of the hypergraph (X,\tau\setminus\{\emptyset\}).

For many standard connected Hausdorff spaces X we have \nu(X) = 2. For instance, if X = \mathbb{R} with the Euclidean topology, let {\cal N} = \{\mathbb{Q}, \mathbb{R}\setminus\mathbb{Q}\}. It took some effort to see that there are connected Hausdorff spaces X with \nu(X) > 2.

Question. For which cardinals \kappa > 2 is there a connected Hausdorff space (X,\tau) such that \nu(X) = \kappa?

Many more natural questions arise in this context, such as how does \nu(\cdot) behave with topological products, and so on. So far I haven’t found a reference studying this concept of “Hausdorff space coloring”.

Posted in Uncategorized | Leave a comment

Ihm ging ein Licht auf: Grieche entdeckte vor 2500 Jahren die Sonne

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.

Posted in Uncategorized | Leave a comment

Homogeneous spaces generalized – and an open problem

Homogeneous spaces are topological spaces (X,\tau) that locally look everywhere the same. Put in mathematical terms, (X,\tau) is homogeneous if for any x,y\in X there is an isomorphism
\varphi:X\to X such that \varphi(x)=y.

We can generalize this by not restricting ourselves to a pair of points (x,y) in the following way:

Let \kappa>0 be a cardinal and let (X,\tau) be a topological space. We say that X is
\kappahomogeneous if

1. |X| \geq \kappa, and
2. whenever A,B\subseteq X are subsets with |A|=|B|=\kappa and \psi:A\to B is a bijective map, then there is a homeomorphism \varphi: X\to X such that \varphi|_A = \psi.

A natural question is now to ask whether for cardinals \alpha<\beta we have
that there is a space that is \alpha-homogeneous, but not \beta-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 \mathbb{R}^2 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 n\geq 5, are there spaces that are n-homogeneous, but not (n+1)-homogeneous?

(The question has a positive answer given in Joel’s post for cardinals \kappa\geq\aleph_0.)

Posted in Uncategorized | Leave a comment

Two notions of continuity in the space of natural sequences

In this presentation by Martín Escardó I came across a nice concept of continuity in the set of all functions (\mathbb{N} \to \mathbb{N}) := \mathbb{N}^\mathbb{N}.

For n\in \mathbb{N} and \alpha, \beta \in (\mathbb{N}\to \mathbb{N}) we say that

\alpha =_{(n)} \beta if and only if for all i\leq n we have \alpha(i) = \beta(i).

Then we define f: (\mathbb{N}\to \mathbb{N}) \to (\mathbb{N}\to \mathbb{N}) to be finitely continuous if

\forall \alpha \in (\mathbb{N}\to \mathbb{N}).\forall n\in \mathbb{N}. \exists m\in \mathbb{N}. \forall \beta \in (\mathbb{N}\to \mathbb{N}).

(\alpha =_{(m)}\beta\implies f(\alpha) =_{(n)} f(\beta)).

So if you want to know the first n positions of the output sequence f(\alpha), it suffices to know the first m positions of the input sequence \alpha.

It turns out that this definition is equivalent to topological equivalence of functions f: (\mathbb{N}\to \mathbb{N}) \to (\mathbb{N}\to \mathbb{N}), where \mathbb{N} is endowed with the discrete topology and (\mathbb{N}\to \mathbb{N}) carries the interval topology.

Nice, isn’t it?

Posted in Uncategorized | Leave a comment

A reformulation of Hadwiger’s conjecture

Let G = (V,E) be a finite, simple, undirected graph. Hadwiger’s conjecture states that

if n = \chi(G) then K_n is a minor of G.

Let’s call that statement (Hadw). We show that it is equivalent to the following statement:

(Hadw’): If G is not a complete graph, then there is a minor M of G such that

  1. M \not \cong G, and
  2. \chi(M) = \chi(G).

It is clear that (Hadw) implies (Hadw’). For the other direction, take any finite graph G and let n = \chi(G). If G is complete, we are done. If not, use (Hadw’) and let M_1 be a proper minor such that \chi(M_1) = n. If M_1 is complete, we are done, otherwise use (Hadw’) again to get a proper minor M_2 of M_1 with \chi(M_2) =n. And so on. Since G is finite, this procedure is bound to end at M_k for some k\in\mathbb{N}. We
have \chi(M_k) = n, and since the procedure ended at k, the graph M_k must be complete. So we get statement (Hadw).

Posted in Uncategorized | Leave a comment

Accumulation without converging subsequence

“Any sequence with an accumulation point also has a subsequence converging to that point” — right? I believed this until yesterday when I stumbled over the following curious, and countable, Hausdorff space.

Endow \omega\times\omega with the following topology:

  • (\omega\times\omega)\setminus\{(0,0)\} is given the discrete topology;
  • U \subseteq \omega\times \omega is a neighborhood of (0,0) if (0,0)\in U and for almost every n\in \omega the set \bar{U}_n := \{k\in\omega: (n,k) \notin U\} is finite.
  • It is routine to verify that this is a topology on \omega\times\omega.

    Observation 1: No sequence in (\omega\times\omega)\setminus\{(0,0)\} converges to (0,0).
    Proof: Let a:\omega \to (\omega\times\omega)\setminus\{(0,0)\} be any sequence. We distinguish two cases:
    Case 1: For all n\in \omega the set \textrm{im}(a) \cap (\{n\}\times \omega) is finite. Then we set U = (\omega\times\omega) \setminus \textrm{im}(a). This is easily seen to be an open nbhood of (0,0) and clearly a doesn’t converge to (0,0).
    Case 2: There is n_0\in \omega such that V:=\textrm{im}(a) \cap (\{n_0\}\times \omega) is infinite. Then U = (\omega\times\omega) \setminus V is an open nbhood of (0,0), because for all n\in \omega with n\neq n_0 we have \bar{U}_n = \emptyset. Moreover, by the conditition described in the statement of Case 2, the sequence a keeps “popping out” of U and therefore does not converge to (0,0).

    Observation 2: There is a sequence b in (\omega\times\omega)\setminus\{(0,0)\} such that (0,0) is an accumulation point of b.
    Proof: Since (\omega\times\omega)\setminus\{(0,0)\} is countable, there is a bijection from \omega to (\omega\times\omega)\setminus\{(0,0)\} and we let b be that bijection.

    So the sequence b we constructed in Observation 2 has (0,0) as an accumulation point, but no subsequence of b converges to (0,0) because of Observation 1!

    Posted in Point-set topology | 2 Comments