## Two-dimensional convergence

Here is something that I was certain would have an easy-to-prove positive answer; but it turns out that there is an exceedingly simple counterexample.

Let $\omega$ be the first infinite ordinal; its successor is $\omega + 1 = \omega \cup \{\omega\}$.We consider a map $M: (\omega+1) \times (\omega+1) \to \mathbb{R}$, or put differently, a $(\omega+1) \times (\omega+1)$-Matrix $M$ of real numbers.

We assume that $M$ has the following properties:
(1) For all $k\in \omega$ we have $\lim_{n\to\infty} M(k, n) = M(k,\omega)$, or more informally, we have “convergence to the right”.
(2) For all $k\in \omega$ we have $\lim_{n\to\infty} M(n, k) = M(\omega, k)$, or more informally, we have “convergence to the bottom”.
(3) $\lim_{n\to\infty} M(n,\omega) = M(\omega,\omega)$, or more informally, the right-hand entries of $M$ converge to the bottom right element $M(\omega,\omega)$.

Question: Does this imply that $\lim_{n\to\infty} M(\omega,n) = M(\omega,\omega)$, that is, do the bottom entries of $M$ also converge to  $M(\omega,\omega)$?

Answer: There is, surprisingly (to me, at least) an easy example showing that the answer is No. Let $M: (\omega+1)^2 \to \mathbb{R}$ be defined by $(\alpha,\beta)\mapsto 0$ if $\alpha \leq \beta$ and $(\alpha,\beta)\mapsto 1$ otherwise. It is easy to verify that (1), (2), (3) above are satisfied. Note that the right-hand entries $M(n, \omega)$ are all 0, and they trivially converge to $M(\omega,\omega) = 0$; but we have $M(\omega, n) = 1$ for all $n\in\omega$ therefore $\lim_{n\to\infty} M(\omega,n) = 1\neq 0 =M(\omega,\omega)$.

For the kind of two-dimensional convergence we are looking for we need some form of “simultaneous” convergence (conceptually related to uniform convergence), which I might address in a later post.

## A mathematical view on the notion of “median”

These days we hear about medians of all kinds of things: household income, lifetime of items such as lightbulbs, and so on. It’s time to get a rigorous grip on the concept.

Definition. Suppose $X\neq \emptyset$ is a set, $(C, \leq)$ a totally ordered set, and $f: X \to C$ a function. Then $m\in C$ is said to be a median of $f$ if the sets $\{x \in X : f(x) \leq m\}$ and  $\{x \in X : f(x) \geq m\}$ have equal size.

It is a reflex of mathematicians to ask about existence and uniqueness of any concept they stumble upon. (Note that I wrote “a median” and not “the median” above.) Indeed, as much as the definition above seems to make sense: Even for simple example, the median needs not exist. Let $X = \{1,2,3\}$ and let $f:X\to \mathbb{R}$ be defined by $f(1) = f(2) = 0$ and $f(3) = 1$. Then $f$ has no median according to the definition above. On the other hand, if $X = \{1,2\}$ and $f:X\to \mathbb{R}$ is the inclusion map, then every element of the open interval $]1,2[$ is a median!

There are many common fixes to the problems of existence and uniqueness, but no definition is really elegant. (Most resort to listing the elements in ascending order and to pick the arithmetical middle of the “middle elements” in the list or something similar.)

Other difficulties arise when we want to pick medians of infinite sample sets. Let $(C,\leq)$ be a totally ordered set. We say that $m\in C$ is a median of $C$ if the sets $\{c \in C : c \leq m\}$ and  $\{c \in C : c \geq m\}$ have equal cardinality. Note that in $\mathbb{R}$ every element is a median, but $\mathbb{N}$ has no median at all!

Beim Anzünden der Kerzen unseres Adventskranzes heute morgen hat es mich gestört, keinen guten Algorithmus zu haben, dass die Kerzen möglichst gleichmässig “belastet” werden. Das hat mich zu folgendem vereinfachten Rätsel inspiriert:

In Adventswoche $k$ (für $k = 1,\ldots, 4$) werden $k$ Kerzen gewählt, angezündet, und so lange brennen gelassen, bis sie 1cm an ihrer Höhe eingebüsst haben. (Die Kerzen sind initial $n$ cm hoch.)

Woche 4 ist ein No-Brainer – da werden immer alle Kerzen angezündet. Ich muss also auf Anfang der Woche 4 “Gleichstand” erreicht haben.

Für $k = 1,2,3$ sei $m_k$ die Anzahl Male, die ich die Kerzen in Woche $k$ anzünde und genau 1cm abbrennen lasse. Für welche Tupel $(m_1, m_2, m_3)$ kann ich für den Anfang der Woche 4 Gleichstand erreichen, sodass die Kerzen am Ende der Adventszeit schön gleichzeitig abbrennen?

## Math facts with simple proofs that are still (somewhat) surprising

Sometimes it happens to me that I become aware of a mathematical fact that surprises me – and the proof for the fact would even fit in a tweet.

When goofing around with graph homomorphisms, I realised that the following is true:

Fact. If $f:G\to H$ is a graph homomorphism, then $\chi(G) \leq \chi(H)$ — no matter whether the graphs involved are finite or infinite.

Proof. Colorings are homomorphisms to complete graphs. If $c: H\to K_{\chi(K)}$ is a homomorphism, then so is $c \circ f : G \to K_{\chi(K)}$.

The funny thing is: If I had been told just the statement of the fact “out of the blue”, I would have said that you probably need some condition on the homomorphism $f:G\to H$, like it being surjective etc. So I find it a bit surprising that the statement holds in this generality — even if there is a tweet-length proof for it.

## Sometimes a maximality principle is true even if Zorn’s Lemma fails

A famous and straightforward result in general topology says that any compact $T_2$ space is

• maximally compact: any finer topology isn’t compact any more;
• minimally $T_2$: any coarser topoology isn’t $T_2$ any more.

A natural pair of questions that arises from this is the following: Is every compact topology contained in a maximally compact one? (Dually: does every Hausdorff topology contain a minimal Hausdorff topology?).

This short post is only concerned with the former of the two questions. Unfortunately, a direct application of Zorn’s Lemma doesn’t lead us anywhere. Let $\mathbb{N}$ denote the set of positive integers. We define a chain of compact topologies on $\mathbb{N}$ by setting

$\tau_n = \mathcal{P}(\{1,\ldots,n\}) \cup \{\mathbb{N}\}$ for every $n\in \mathbb{N}$. (By $\mathcal{P}(.)$ we denote the power set.)

Now every $\tau_n$ is compact, but the topology generated by the union of this chain is the discrete topology on $\mathbb{N}$, which is not compact. So we cannot apply Zorn’s Lemma for this question.

It turns out that even if we can’t apply ZL, the statement that every compact topology is contained in a maximally compact one is true, which answered an old question. The result can be seen in this paper by Martin Maria Kovar.

## On empty Hom-sets between graphs

In many categories such as Set, Group, Top (topological spaces) there is a morphism between any two objects, usually in both directions. (If one object is “empty”, like the empty space, or the empty set, there is the “empty” morphism from $\emptyset$ to the other object, but not the other way round.)

However in the category Graph it is possible that non-empty graphs $G,H$ have no graph homomorphism between them in either direction:

Let $K_3$ be the complete graph on 3 points and let $H$ be any triangle-free graph with $\chi(H) > 3$, for instance the Grötzsch graph, which has chromatic number 4.

Since $H$ is triangle-free, there is no graph homomorphism $\varphi: K_3 \to H$ and if there were a homomorphism $\eta : H \to K_3$, this map would be an $n$-coloring of $H$ for some $n \leq 3$.

## On the topological closure of the diagonal of a space

When we take a class in general topology and learn about $T_2$-spaces, one of the standard exercises we do is:

Prove that a space $X$ is Hausdorff if and only if the diagonal $\Delta_X = \{(x,x) : x \in X\}$ is closed in the product topology of $X \times X$.

Given any topological space $X$, the closure of the diagonal, that is $cl(\Delta_X)$, is a binary relation, which in the case of Hausdorff spaces is pretty boring. So a natural question to ask is: Which binary relations on a set $X$ arise as the closure of the diagonal for a suitable topology $\tau$ on $X$? We will call those binary relations topologically realizable.

It is easy to see that for any topology, $cl(\Delta_X)$ is reflexive and symmetric, and it turns out that a large class of reflexive and symmetric relations are topologically realizable:

Proposition. Any equivalence relation is topologically realizable.

Proof. Let $X$ be a set and $R \subseteq X\times X$ be an equivalence relation. We set $\textrm{Block}(R)=\{[x]_R : x \in X\}$ — so it is the set of equivalence classes or “blocks” that $R$ induces. Using the Axiom of Choice we pick for each block $B \in$ $\textrm{Block}(R)$ a representative $r(B) \in B$ and we define

$\tau = \{ U\subseteq X :$ for all $B \in$ $\textrm{Block}(R)$ : if $U\cap B \neq \emptyset$ then $r(B)\in U\}$.

It is not hard to verify that $\tau$ is indeed a topology. We need to show that $cl(\Delta_X) = R$.

$cl(\Delta_X) \subseteq R$: Let $(x,y) \in (X\times X)\setminus R$. So $U= [x]_R$ and $V= [y]_R$ are disjoint open sets, therefore $U\times V$ is an open neighborhood of $(x,y)$ that does not intersect $\Delta_X$, so $(x,y)$ is not in $cl(\Delta_X)$.

$cl(\Delta_X) \supseteq R$: Let $(x,y) \in R$ that is $[x]_R = [y]_R$. By construction of the open sets, every open neighborhood of $x$ and every open neighborhood of $y$ contains $z := r([x]_R) = r([y]_R)$. Therefore every open neighborhood of $(x,y)$ in the product space $X\times X$ contains $(z,z) \in \Delta_X$ which implies that  $(x,y) \in cl(\Delta_X)$.

Does the converse hold? We might wonder whether conversely, every topologically realizable relation is transitive. It turns out that this is not true; see Example 4.1. in this paper by Maria-Luisa Colasante and me.

I would like to see the following: Is there a set $X$ and a reflexive, symmetric relation $R \subseteq X\times X$ such that $R$ is not topologically realizable?