Ramsey functions, property B, and the Axiom of Choice

Posted on 2023/07/18 by dominiczypen

Let [\omega]^\omega denote the collection of infinite subsets of \omega (the first infinite ordinal) and let c:[\omega]^\omega\to \{0,1\} be any map. We say that a \in [\omega]^\omega is monochromatic with respect to c if c restricted to {\mathcal P}(a)\cap [\omega]^\omega is constant (or, equivalently, if c(b) = c(a) for all b\in [\omega]^\omega with b\subseteq a). We say c: [\omega]^\omega\to \{0,1\} is Ramsey if there is a\in [\omega]^\omega such that a is monochromatic with respect to c.

Certainly, plenty of examples of Ramsey functions c:[\omega]^\omega\to\{0,1\} come to mind, which leads to the question:

Are there non-Ramsey functions c: [\omega]^\omega\to\{0,1\}?

It is indeed a bit tricky to come up with one – the construction I present next needs the Axiom of Choice ( https://en.wikipedia.org/wiki/Axiom_of_choice ). We define a binary relation on [\omega]^\omega by

a\simeq_{\text{fin}} if and only if the symmetric difference a \;\Delta\; b = (a\setminus b) \cup (b\setminus a) is finite.

From “the infinitist’s point of view” two sets are the same if they only differ in finitely many elements. It is easy to check that this an equivalence relation.

Let [\omega]^\omega/\simeq_{\text{fin}} be the set of equivalence classes of [\omega]^\omega with respect to the equivalence relation \simeq_{\text{fin}}. We use the Axiom of Choice to find a set of representatives R\subseteq [\omega]^\omega such that

|R \cap b| = 1 for all blocks b\in [\omega]^\omega/\simeq_{\text{fin}}.

We define the representative function r:[\omega]^\omega\to [\omega]^\omega by assigning to each a\in [\omega]^\omega the unique element r(a)\in R such that a\simeq_{\text{fin}} r(a).

Finally, we define c:[\omega]^\omega\to\{0,1\} by setting c(a) = 0 for a\in [\omega]^\omega if |a\;\Delta\; r(a)| is even, and c(a) = 1 otherwise. It is easy to see that whenever a\in [\omega]^\omega, then a is not monochromatic: As a \;\Delta\; r(a) is finite and a and r(a) are both infinite, pick n_0\in a\cap r(a). So the parity of

|a\;\Delta\; r(a)|\; and \;|(a\setminus\{n_0\}) \;\Delta\; r(a)|

is not the same, therefore c restricted to {\mathcal P}(a)\cap [\omega]^\omega is not constant.

Reformulation with property {\mathbf B}

A hypergraph is a pair H=(V,E) where V is a non-empty set and E\subseteq {\mathcal P}(V). We say that H has property \mathbf{B} if there is S\subseteq V such that S\cap e\neq\emptyset\neq (e\setminus S) for all e\in E. (In other words, S intersects every e\in E, but no e\in E is fully contained in S.)

The question whether there is a non-Ramsey function c: [\omega]^\omega \to \{0,1\} is equivalent to asking whether the hypergraph H_{\text{Ramsey}} = ([\omega]^\omega, E) where

E = \{{\mathcal P}(a)\cap [\omega]^\omega: a\in [\omega]^\omega\}

has property \mathbf{B}.

Further questions

  1. Does the statement “H_{\text{Ramsey}} has property \mathbf{B}” imply the Axiom of Choice? Or does it imply a weaker statement than AC? Or is it provable in ZF alone?
  2. Consider the hypergraph H = ([\omega]^\omega/\simeq_{\text{fin}}, E) where E is built in an analogous manner to the edge set in hypergraph H_{\text{Ramsey}}. Does H have property {\mathbf B}, no matter whether we assume the Axiom of Choice?
  3. What is in {\sf (ZF)} an example of a poset (P,\leq) with no minimal elements such that the hypergraph H_P = (P, E) does not have property {\mathbf B}, where E is the collection of principal down-sets of P? (In other words, (P, \leq) has the property that whenever its elements are colored red or blue, then there is a principal down-set consisting of more than 1 element such that all the elements have the same color.)
Posted in Uncategorized | Leave a comment

A Funny Field

Posted on 2021/01/06 by dominiczypen

Let \omega denote the first infinite cardinal – that is, the set of non-negative integers. Let p_0 = 2 be the smallest prime number, and let (p_n)_{n\in\omega} enumerate all prime numbers in ascending order.

Let \mathcal{U} be a free ultrafilter on \omega. We consider the field

F = \big(\prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z}\big)/{\mathcal U}.

This uses the standard notation for considering the equivalence relation \simeq_{\mathcal U} on \prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z} where we have x\simeq_{\mathcal U}y for x,y \in \prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z} if and only if \{i\in\omega: x(i) =y(i)\} \in \mathcal U. (It is easy to verify that this is an equivalence relation.) On \prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z} we use component-wise addition and multiplication. It is a standard exercise to show that whenever x\simeq_{\mathcal U} x' and y\simeq_{\mathcal U} y' then (x+y)\simeq_{\mathcal U} (x'+y'), and the same holds for multiplication. So the operations are well-defined on the quotient F = \big(\prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z}\big)/\simeq_{\mathcal U} =\big(\prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z}\big)/{\mathcal U}, and it is another standard exercise to show that F is indeed a field (as opposed to \prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z}, which has lots of zero divisors). Moreover, F is uncountable and has characteristic 0.

I don’t know if and where this field has been studied, or if there is a well-known field that is isomorphic to F.

There are several questions I cannot answer, and I would be grateful for any hints on them.

  1. If we take different free ultrafilters {\mathcal U}_1, {\mathcal U}_2, can it happen that (\prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z}\big)/{{\mathcal U}_1} is not isomorphic to (\prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z}\big)/{{\mathcal U}_2}?
  2. If yes: Suppose {\mathcal U}_1, {\mathcal U}_2 are free ultrafilters such that (\prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z}\big)/{{\mathcal U}_1} and (\prod_{n\in\omega}\mathbb{Z}/p_n\mathbb{Z}\big)/{{\mathcal U}_2} are isomorphic fields. What can be said about {\mathcal U}_1, {\mathcal U}_2? For instance, do they have to be in relation with respect to the Rudin-Keisler ordering?
  3. Can F be made into an ordered field?
  4. Are there surjective group homomorphisms from the additive group of F to the additive group of \mathbb{R}, or vice versa? What about the multiplicative group of F\setminus \{0\}?
Posted in Uncategorized | Leave a comment

Making critical graphs as regular as possible

Posted on 2019/12/17 by dominiczypen

Suppose you want to have a graph G = (V,E) with chromatic number \chi(G) equaling some value k, such that G is minimal with this property. So you end up with a k-(vertex-)critical graph.

It is easy to construct critical graphs by starting with some easy-to-verify example like C_5 and then adding points and connecting them to all the vertices already present. But the graphs you get are highly non-regular: some vertices have quite low degree, and the one vertex you added has maximum degree.

I was wondering where the limits for regularity for k-critical graphs are. Here’s an attempt to make this a bit more formal:

For a finite, simple, undirected graph G=(V,E) let \delta(G) and \Delta(G) denote the minimum and maximum degree of G, respectively.

Is there a global constant K\in\mathbb{N} such that whenever n,k are integers with n\geq 4, k\geq 1 and n>k, there is a k-vertex critical graph G=(V,E) with |V|=n and \Delta(G)-\delta(G) \leq K?

I asked this question on MathOverflow a while ago, but it has not been answered yet.

Posted in Uncategorized | Leave a comment

Generalizing the T_0 separation axiom

Posted on 2018/10/11 by dominiczypen

The starting point of this blog post is a slight reformulation of the T_0 separation axiom: A topological space (X,\tau) is T_0 if for all x\neq y\in X there is a set U\in \tau such that

\{x,y\}\cap U \neq \emptyset \text{ and } \{x,y\}\not\subseteq U.

Given a cardinal \kappa \geq 2, we say that a space (X,\tau) is T^{\kappa}_0 if for all subsets S\subseteq X with |S|=\kappa there is a set U\in \tau such that U “splits” S, or more formally

S\cap U \neq \emptyset \text{ and } S\not\subseteq U.

Obviously, if \lambda\geq \kappa\geq 2 and if (X,\tau) is T^\kappa_0, then X is also T^\lambda_0. We say, the space (X,\tau) is minimally T^\kappa_0 if it is T^\kappa_0, but for all cardinals \alpha<\kappa with \alpha\geq 2, the space (X,\tau) is not T^\alpha_0.

Question. Given cardinals \lambda\geq\kappa\geq 2, is there a topological space (X,\tau) such that |X|=\lambda and (X,\tau) is minimally T^\kappa_0?

Posted in Uncategorized | Leave a comment

Basics on towers on the natural numbers

Posted on 2018/08/20 by dominiczypen

For A, B \subseteq \omega we write A \subseteq^* B if A\setminus B is finite, and we write A\simeq^* B if A\subseteq^* B and B\subseteq^* A.

A tower is a collection {\cal T} of co-infinite subsets of \omega such that for all A\neq B\in {\cal T} we have A\not\simeq^*B and either A\subseteq^* B or B \subseteq^* A. (A\subseteq \omega is co-infinite if \omega\setminus A is infinite.)

If {\cal S}, {\cal T} are towers, we say that {\cal S}\leq_t {\cal T} if A\in {\cal S} and B\in{\cal T} with B\subseteq^* A jointly imply that B\in{\cal S}. (In other words, this means that {\cal S} is a down-set or initial segment of {\cal T} with respect to \subseteq^*). It is easy to prove that \leq_t is a partial order on the collection of all towers on \omega.

The remainder of this post is about maximal towers with respect to \leq_t. The proof of the following lemma is routine.

Lemma 1. If {\frak T} is a collection of towers, such that for all {\cal S}, {\cal T}\in {\frak T} we have either {\cal S}\leq_t {\cal T} or {\cal T}\leq_t {\cal S}, then

1. \bigcup {\frak T} is a tower, and
2. {\cal T}\leq_t \bigcup{\frak T} for all {\cal T}\in{\frak T}.

Corollary 1. Zorn’s Lemma and Lemma 1 imply that there is a tower in \omega that is maximal with respect to \leq_t.

Lemma 2. If {\cal A} is a countable tower then {\cal A} is not maximal.

Proof. Let (A_n)_{n\in\omega} be a sequence of co-infinite subsets of \omega such that for all n\in\omega we have A_n \subseteq^* A_{n+1} . We want to show there is A\subseteq \omega co-infinite with A_n\subseteq^* A for all n\in\omega.

Step 1. If k\in \omega, then \bigcup_{i=0}^k A_i is co-infinite.

Step 2. There is f:\omega\to\omega strictly increasing such that f(n) \in \omega\setminus\big(\bigcup_{i=0}^n A_i\big) for all n\in\omega.

Step 3. Set A = \bigcup_{k\in\omega}\big(A_k\setminus [0,\ldots,f(k)]\big).

Then it follows that

1: A_k\subseteq^* A for all k\in \omega since (A_k\setminus A) \subseteq [0,\ldots,f(k)] which is a finite set.

2: A is co-infinite, since for all k\in \omega we have f(k)\notin A, so A\cap \{f(k):k\in\omega\}=\emptyset, and since f is strictly increasing we have \{f(k):k\in\omega\} is infinite, so A is co-infinite.

Letting {\cal A} =\{A_n:n\in\omega\} we get that {\cal A}' = {\cal A} \cup\{A\} is a tower with {\cal A} \leq_t {\cal A}' but {\cal A}' \not\leq_t {\cal A}, so the countable tower {\cal A} is not maximal. \Box

Posted in Uncategorized | Leave a comment

A definition of minor (in graph theory)

Posted on 2018/06/02 by dominiczypen

Many people I talk to about graph theory feel some uneasiness when it comes to the notion of “minor”. I want to try to alleviate this feeling by providing the definiton of minor that I work with.

First an easy definition. If G is a simple, undirected graph and S, T\subseteq V(G) are non-empty and disjoint, we say that S, T are connected to each other if there are s\in S, t\in T such that \{s,t\}\in E(G).

Let G, H be simple, undirected graphs. We say that G is a minor of H if there is a collection {\cal S} of non-empty, mutually disjoint, and connected subsets of V(H) and a bijection \varphi:V(G) \to {\cal S} such that

whenever v,w\in V(G) and \{v,w\}\in E(G) then the sets \varphi(v) and \varphi(w) are connected to each other in H.

Posted in Uncategorized | Leave a comment

Any graph or its complement is connected

Posted on 2018/04/09 by dominiczypen

This is a short note of something that I wasn’t sure whether it is true for infinite graphs. Let G = (V,E) be any simple, undirected graph, finite or infinite, such that V \neq \emptyset. By \bar{G} we denote the complement of G.

Proposition. At least one of G, \bar{G} is connected.

Proof. If V has only 1 element, the statement is trivially true. So suppose that |V| > 1. Let \kappa = |V| and let \varphi:\kappa\to V be a bijection. Suppose that neither G nor \bar{G} is connected. It is easy to see that this implies that there is a smallest \alpha_0\in\kappa such that the induced subgraph G_{\alpha_0} on the set \text{im}(\varphi|_{\{0,\ldots,\alpha_0\}}) = \text{im}(\varphi|_{\alpha_0\cup \{\alpha_0\}}) \subseteq V has the property that neither G_{\alpha_0} nor its complement \bar{G}_{\alpha_0} is connected.

Case 1. \varphi(\alpha_0) has no neighbors in the graph G_{\alpha_0}. But then \varphi(\alpha_0) is connected to every vertex in \bar{G}_{\alpha_0}, so \bar{G}_{\alpha_0} is connected, contradicting our assumption.

Case 2. \varphi(\alpha_0) has no neighbors in the graph \bar{G}_{\alpha_0}. Same contradiction as Case 1.

Case 3. \varphi(\alpha_0) has neighbors in the graph G_{\alpha_0} as well as in the graph \bar{G}_{\alpha_0}. We know that at least one of G_{\alpha_0}\setminus\{\varphi(\alpha_0)\} and \bar{G}_{\alpha_0}\setminus\{\varphi(\alpha_0)\} is connected. We may assume that G_{\alpha_0}\setminus\{\varphi(\alpha_0)\} is connected. But since there is an edge from some point in G_{\alpha_0}\setminus\{\varphi(\alpha_0)\} to \varphi(\alpha_0) by assumption of Case 3, we know that G_{\alpha_0} is connected, contradicting our choice of \alpha_0.

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

Posted in Uncategorized | Leave a comment

Ode to ed (Unix standard text editor)

Posted on 2017/09/12 by dominiczypen

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

Posted on 2017/07/17 by dominiczypen

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

Posted on 2017/07/13 by dominiczypen

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