Atomistic, but non-complete lattices

Posted on 2026/02/13 by dominiczypen

The motivation for this post is that these days I am goofing around with lattices arising from subspaces of hypergraphs, which are complete and atomistic.

Let (L, \leq) be a lattice with a bottom element 0. We say that a\in L\setminus\{0\} is an atom if there is no element strictly between a and 0. The lattice (L,\leq) is said to be atomistic if every element x\in L is the supremum of all atoms below x.

This sounds like a “recipe for completeness”: given S\subseteq L, take the set of atoms A lying below some s\in S and use the supremum of A, right?

But the point is, that set A need not have a supremum in L. Which leads to this easy example: Let L:= [\omega]^{<\omega} be the set of finite subsets of \omega. Then the set of atoms are the singletons, and clearly every finite set F\in [\omega]^{<\omega} is the supremum (union) of the singletons contained in F. Note that if we “top L” off and consider [\omega]^{<\omega} \cup\{\omega\}, then this new atomistic lattice is complete.

Which might lead to the following

Conjecture. Every atomistic lattice with a top element is complete.

But it turns out that even this conjecture is false. The only construction of a counterexample to the construction is somewhat involved – so we do a preliminary construction first and then replace 2 elements of the simpler construction for the final construction.

First, we consider two copies of \omega, say (\omega\times\{0\}) and (\omega\times\{1\}). We order (\omega\times\{0\}) as an antichain, and (\omega\times\{1\}) is ordered with the usual chain ordering inherited from \omega. Finally, we connect these two copies by saying that (a,0) < (b,1) whenever a, b\in \omega with $a\leq b$ in the usual ordering. Finally we place an artificial element \bot at the bottom.

Formally, the ground set is L:= (\omega\times\{0\}) \cup (\omega\times\{1\}) \cup \{\bot\}, and the ordering relation on L which we denote by \leq_L defined as follows:

\leq_L = \big\{\big((x,0), (x,0)\big): x \in \omega\big\}\;\;   // comment: order (\omega\times \{0\}) as antichain

\;\; \cup \, \big\{\big((a,1), (b,1)\big): a, b \in \omega, a\leq b\big\}\;\;  // order (\omega\times \{1\}) conventionally

\;\; \cup \, \big\{\big((a,0), (b,1)\big): a, b \in \omega, a\leq b\big\} \;\;  // connect the two copies of \omega

\;\; \cup \, \big\{(\bot, x): x\in L\big\}.\;\;   // add bottom

It is not hard to verify that this construction gives an atomistic lattice. For the final step, we replace \omega with \mathbb{Z}\setminus\{0\}, but ordered with “a hole in the middle” by saying that a\leq b \in \mathbb{Z}\setminus\{0\} if a\leq b in conventional \mathbb{Z} such both are negative or both are positive — and additionally a < b if a is positive and b is negative.

If we replace both \omega-copies in the preliminary construction with copies of \mathbb{Z}\setminus\{0\}, we get the desired counterexample for the conjecture.

Finally, thanks to Jonathan David Farley, who made me aware that I could have saved the effort of constructing the above example by considering

L := [\omega]^{<\omega} \cup\big\{U\subseteq \omega: (\omega\setminus U)\in [\omega]^{<\omega}\big\}

ordered by \subseteq. This is a conceptually much easier counterexample to the conjecture.

Posted in Uncategorized | Tagged , | Leave a comment

Selection principles: “Omega choose T” vs “Omega choose Gamma”

Posted on 2025/08/18 by dominiczypen

Motivation. We show that the space (\aleph_1, \aleph_1\cup\{\aleph_1\}) satisfies the selection principle {\Omega \choose T}, but not {\Omega \choose \Gamma}. This gives a negative answer to the question “{\Omega \choose T} = {\Omega \choose \Gamma}?” in the general setting. Below is a self-contained treatment of the matter.

Let (X,\tau) be a topological space. We say that {\cal U} \subseteq \tau is an open cover, or cover for short, if  X\notin {\cal U} and \bigcup {\cal U} = X. For x\in X we set {\cal U}_x = \{U \in {\cal U}: x\in U\} and call {\cal U}_x the star of x (with respect to {\cal U}).

Thick covers. We call a cover {\cal U}\subseteq \tau
1. large if {\cal U}_x is infinite for every x\in X,
2. an \omega–cover if every finite subset of X is contained in some member of {\cal U},
3. a t–cover if {\cal U} is large, and for all x,y\in X at least one of the
    sets {\cal U}_x\setminus {\cal U}_y and {\cal U}_y\setminus {\cal U}_x is finite, and
4. a \gamma-cover if {\cal U} is infinite, and for every x\in X the set {\cal U} \setminus {\cal U}_x is finite.

Let \Lambda, \Omega, T, \Gamma denote the collections of (open) large covers, \omega-covers, t-covers, and \gamma-covers, respectively. An easy argument shows that every \gamma-cover is large, and therefore a t-cover, so \Gamma \subseteq T.

A selection principle. If {\mathfrak U}, {\mathfrak V} are families of covers of X, we define the property {{\frak U}\choose {\frak V}}, which may or may not hold for the given families:

{{\frak U}\choose {\frak V}} : For each {\cal U}\in {\frak U} there is {\cal V}\subseteq {\cal U} such that {\cal V}\in {\frak V}.

Construction of the space. We consider the space (\aleph_1, \tau) where \aleph_1 is the smallest uncountable cardinal and \tau is the collection of down-sets in the cardinal \aleph_1, that is \tau = \aleph_1\cup\{\aleph_1\}.

Proposition.  If {\cal U}\subseteq (\tau \setminus \{\aleph_1\}) is a cover, then:
1. {\cal U} is a large cover,
2. {\cal U} is an \omega-cover,
3. {\cal U} is a t-cover, but
4. {\cal U} is never a \gamma-cover.

Proof.
(1) Let \alpha\in \aleph_1. Suppose \alpha is only covered by finitely many members U_1,\ldots U_n\in {\cal U}. But then, \beta:=\bigcup{\cal U}\in \aleph_1 is not covered by any member of \{U_1,\ldots, U_n\}. We have \beta > \alpha, and since {\cal U} is a covering of \aleph_1, there is U^* \in {\cal U} covering \beta and therefore \alpha. Clearly U^*\notin \{U_1,\ldots , U_n\}, contradicting the assumption that the only members of {\cal U} covering \alpha are U_1,\ldots, U_n.

(2) Let S\subseteq \aleph_1 be finite, and consider \beta = \bigcup S\in \aleph_1. Then \beta is contained in some U\in {\cal U}, so S \subseteq U.

(3) Let \alpha,\beta\in \aleph_1. We may assume that \alpha<\beta. Then {\cal U}_\alpha\setminus {\cal U}_\beta = \emptyset, which is finite, so {\cal U} is a t-cover.

(4) Suppose that {\cal U}\subseteq \tau\setminus\{\aleph_1\} is a \gamma-cover. So every \alpha\in\aleph_1 is contained in all but finitely many members of {\cal U}. Note that due to the special nature of cardinals, we have {\cal U}\subseteq \aleph_1. So {\cal U} is a well-ordered set such that all members only finitely many predecessors. This implies that {\cal U} is either a finite or countable collection of members of \aleph_1 such that \bigcup{\cal U} = \aleph_1. This contradicts the fact that \aleph_1 is a regular cardinal. \Box

By (2) and (3) from the proposition above, every \omega-cover in the space (\aleph_1,\tau) with \tau = \aleph_1\cup\{\aleph_1\} is a t-cover, so the property {\Omega \choose T} is trivially true. On the other hand, by (4) from above, no cover is a \gamma-cover, therefore property {\Omega\choose \Gamma} is false.

Reference: Boaz Tsaban, SPM (Selection Principles in Mathematics) bulletin No. 1, 2003, https://arxiv.org/pdf/math/0301011

Posted in Uncategorized | Tagged , , , , , | Leave a comment

The Vietoris topology as a functor V : Top -> Top

Posted on 2025/02/17 by dominiczypen

Given a set X and A \subseteq X, we let

    [A]^+ = \{ Z : Z \subseteq A \} and
    [A]^- = \{ Z \subseteq X : Z \cap A \neq \emptyset \}.

If (X,\tau) is a topological space, the Vietoris topology on the ground set {\mathcal P}(X) is the topology generated by the subbasis

    {\mathcal S}=\{\,[ U ]^+: U\in\tau\}\,\cup\,\{\,[ U ]^-: U\in\tau\}

is and denoted by \tau^V_{(X,\tau)}.

Let \mathsf{Top} be the category of topological spaces with continuous maps as morphisms. We define a contravariant functor {\bf V}: \mathsf{Top}\to \mathsf{Top} in the following way:

1. Objects: If (X,\tau) is a topological space, we let {\bf V}(X,\tau) = (\mathcal{P}(X), \tau^V_{(X,\tau)}).

2. Morphisms: If f:X_0\to X_1 is a continous map between topological spaces (X_i, \tau_i) for i \in \{0,1\}, we define {\bf V}(f):\mathcal{P}(X_1) \to \mathcal{P}(X_0) by

    U\in\tau_1\mapsto f^{-1}(U)\in\tau_0.

It is a standard exercise to check that this defines a functor {\bf V}: \mathsf{Top}\to \mathsf{Top}. I am not aware of any reference that studies properties of this functor (pointers are welcome!). Here are several questions arising naturally:

1. If {\bf V}(X) \cong {\bf V}(Y) for topological spaces X, Y, does this entail X\cong Y?
2. What separation axioms does {\bf V} preserve?
3. Does the functor {\bf V}: \mathsf{Top}\to \mathsf{Top} have a right of left adjoint?

Posted in Uncategorized | Leave a comment

The Parity Principle: a pitfall in the use of Zorn’s Lemma

Posted on 2024/12/23 by dominiczypen

Motivation. The three-dimensional cube can be formalized by \mathcal P(\{0,1,2\}) where vertices x,y\in\mathcal P(\{0,1,2\}) are connected by an edge if and only if their symmetric difference x\,\triangle\, y := (x\setminus y) \cup (y\setminus x) contains exactly 1 element. If we want to assign to each vertex one of the colors black and white such that no two vertices connected by an edge get the same color, we use the concept of parity: color any vertices containing an even number of elements black, and the rest white. This “parity algorithm” works for any \mathcal P(X) where X is a finite set. But what happens in the infinite case?

Taking this to infinity. Consider the following statement:

(Parity Principle:) If X\neq \emptyset is a set, then there is \mathcal B\subseteq \mathcal P(X) such that whenever latex a,b\in \mathcal P(X) with a\,\triangle\, b = {x} for some x\in X, then \mathcal B contains exactly one of a, b.

It turns out that this is a consequence of the Axiom of Choice (AC)) – but it is strictly weaker than (AC).

Non-working version. Let X be any set, let A, B\subseteq X. The Hamming distance d_{\text{Ham}}(A, B) of A, B is defined by d_{\text{Ham}}(A, B) = |A \, \triangle \, B|. We say that a family {\mathcal B}\subseteq {\mathcal P}(X) of subsets of a set X is good if the following holds: whenever A, A'\in {\mathcal P}(X) and d_{\text{Ham}}(A,A') = 1 then at most one of A, A' belongs to {\mathcal B}.

Now Zorn’s Lemma implies that there is a maximal good family {\mathcal B}_0 with respect to set inclusion \subseteq. So certainly {\mathcal B}_0 proves the Parity principle, right? Wrong! Consider the X = \{0, 1, 2, 3\}. Then

{\mathcal B}_0 := \big\{\{0\}, X\big\}

is maximal amongst the good families in {\mathcal P}(X), but it does not have the property that whenever A, A'\in{\mathcal P}(X) with |A\, \triangle \, A'| = 1, then exactly one of A, A' belongs to {\mathcal B}_0: Take A=\{1\}, A' = \{1,2\} for example.

So the existence of maximal good families does not prove the Parity Principle.

Proof sketch for the Parity Principle from (AC).

1. Define an equivalence relation \simeq on \mathcal{P}(X) by letting A\simeq B if and only if d_{\text{Ham}}(A, B) is finite.

2. Using (AC), we let \mathcal{R} be a representative system of \simeq.

3. Given any A\in {\mathcal P}(X), there is a unique R(A)\in {\mathcal R} such that d_{\text{Ham}}\big(A, R(A)\big) is finite.

4. Let {\mathcal B}_0 = \{A \in {\mathcal P}(X): d_{\text{Ham}}\big(A, R(A)\big) \text{ is even}\big\}.

Then {\mathcal B}_0 has the following property: Whenever A, A' have Hamming distance 1, that is d_{\text{Ham}}(A, A') = 1, then either A\in {\mathcal B}_0 or A' \in {\mathcal B}_0, which establishes the Parity Principle.

Posted in Uncategorized | Tagged , , | Leave a comment

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 | 3 Comments

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