## 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
$\kappa$homogeneous 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$.)

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

## 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).

## 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

## Measuring subsets of N

Recently I tried to put a measure on the powerset of the natural numbers $\mathcal{P}(\mathbb{N})$, but it was pointed out in a comment that the map I defined is not even finitely additive.

Question: Is there a map $\mu:\mathcal{P}(\mathbb{N}) \to [0, 1]$ with the following properties:

• $\mu(\mathbb{N}) = 1$;
• if $A, B\subseteq\mathbb{N}$ such that $A\cap B = \emptyset$ then $\mu(A\cup B) = \mu(A)+\mu(B)$;
• $\mu$ is translation-invariant, that is $\mu(A+n) = \mu(A)$ for $A\subseteq \mathbb{N}$ and $n\in\mathbb{N}$ where $A+n = \{a+n: a \in A\}$.
Posted in Uncategorized | 3 Comments

Recently I was trying to put a “meaningful” measure on the set $\mathbb{N}$ of natural numbers. The first idea was to measure the density of a subset $A \subseteq \mathbb{N}$ on natural intervals $\{1,\ldots,n\}$ and take the limit of it, that is

$\lim_{n\to\infty}\frac{|\{1,\ldots,n\} \cap A|}{n}.$

However, the limit does not always exist (examples?). So here is a modification and we define a map $\mu:\mathcal{P}(\mathbb{N}) \to [0,1]$ by

$\mu(A) := \lim\inf_{n\to\infty}\frac{|\{1,\ldots,n\} \cap A|}{n}$ for all $A \subseteq \mathbb{N}$.

Question: is $\mu$ additive, that is for $A,B\subseteq \mathbb{N}$ with $A\cap B = \emptyset$ do we have $\mu(A\cup B) = \mu(A) + \mu(B)$? There is a surprising answer that I’ll post in a few days.

Posted in Uncategorized | 9 Comments

## Exceptions to the Friendship Paradox

The Friendship Paradox says that your friends are likely to have more friends on average than you do. I was wondering whether there are settings in which the statement of the Friendship Paradox does not hold. Below we think about this question in precise mathematical terminology.

Friendships, social networks, and the like are often modelled using simple graphs. People are represented by vertices, and each edge denotes a pair of friends. The set of friends, or neighbors, of a vertex $v$ is defined to be $N(v) = \{w \in V(G) : \{v,w\} \in E(G)\}$. The number of friends, or the degree of $v\in V(G)$ is set to be $\textrm{deg}(v) = \textrm{card}(N(v)$ and the average number of the friends of a person’s friends is defined by $\textrm{ad}(v) = \textrm{avg}\{\textrm{deg}(w) : w \in N(v)\}$.

We say that a person (or vertex) $v$ is proud if $\textrm{deg}(v) > 0$ and $\textrm{deg}(v) > \textrm{ad}(v)$. One interesting version of the question above is: Do there exist graphs such that more than half of the people are proud?

The following insight is elementary, but it was still a surprise for me: It turns out that the share of proud people can be arbitrarily close to $1$.. In order to prove this, take any integer $m > 4$ and consider the complete graph on $m$ points with one edge removed. It is easy to see that the 2 people adjacent to the sole edge that was removed are the only ones that are not proud. So the share of proud people is $\frac{m-2}{m}$ which converges to $1$ as $m$ grows large.