3
$\begingroup$

Let $\mathcal{G}_{<\omega}$ be the set of graphs $G = (V,E)$ such that $V = \{0,\ldots,n\}$ for some $n \geq 0$ and $E \subseteq \mathcal{P}_2(V) = \{\{a,b\} : a,b \in V \textrm{ and } a\neq b\}$. We write $\mathcal{G}_{<\omega}/\cong$ for the set of isomorphism classes. The following defines an ordering relation on $\mathcal{G}_{<\omega}/\cong$:

$[G]_\cong \leq [H]_\cong$ if and only if there is a collection $\mathcal{S}$ of non-empty, connected and pairwise disjoint subsets of $H$ and a bijection $\varphi: G\to \mathcal{S}$ such that whenever $\{v,w\}\in E(G)$ there are $x\in\varphi(v), y\in\varphi(w)$ such that $\{x,y\} \in E(H)$.

In other words, this is the "minor ordering".

Questions:

1) Is $(\mathcal{G}_{<\omega}/\cong, \leq)$ a lattice?

2) If $P$ is a finite poset, is there an order-embedding $e: P\to \mathcal{G}_{<\omega}/\cong$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Re part (1): It's certainly not a lattice. For instance if $G$ is a four-vertex path and $H=K_{1,3}$, a four-vertex star, then the minimal graphs that contain both $G$ and $H$ as minors are a four-vertex graph with a triangle and a tail, or a five-vertex tree. Neither is a minor of the other: the five-vertex tree has too many vertices to be a minor of the four-vertex triangle-and-tail, and in the other direction taking a minor of a five-vertex tree can't produce anything with a cycle. So $G$ and $H$ have no unique least upper bound.

By the way, the way you define minors forces the graphs to be simple. This works, but the theory is often a little simpler (e.g. forbidden minors are smaller) if you allow multiple adjacencies and self-loops instead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.