All Questions
Tagged with graph-minors infinite-combinatorics
7 questions
0
votes
1
answer
99
views
Countable graph with $2^{\aleph_0}$ non-isomorphic induced minors
Let $G=(V,E)$ be a simple, undirected graph. If $S, T\subseteq V$ are disjoint sets, 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$. We say a ...
- 48.8k
0
votes
1
answer
80
views
Infinite complete minor in $\min,\max$-graph on $\mathbb{N}$
Let $[\omega]^2 =\big\{\{x,y\}:x\neq y \in \omega\big\}$ denote the collection of all 2-element subsets of the non-negative integers. Let $$E=\big\{\{p,q\} : p,q \in [\omega]^2 \text{ and } \max(p)=\...
- 48.8k
0
votes
1
answer
107
views
Hadwiger number of the Hadwiger-Nelson graph on $\mathbb{R}^2$
If $G =(V,E)$ is a simple, undirected graph (finite or infinite), and $\kappa \neq \emptyset$ is a cardinal, we say that the complete graph $K_\kappa$ is a minor of $G$ if there is a collection ${\...
- 48.8k
0
votes
0
answers
61
views
Hadwiger numbers of (-1)-isomorphic graphs
We say that simple, undirected graphs $G, H$ are (-1)-isomorphic if there is a bijection $\varphi:V(G)\to V(H)$ such that for all $v\in V$ we have that the induced subgraphs $G\setminus\{v\}$ and $H\...
- 48.8k
0
votes
1
answer
172
views
Is every finite graph an induced minor of $\omega^2$?
Let $G=(V,E)$ be a simple, undirected graph. Suppose that ${\cal S}$ is a collection of non-empty, connected, and pairwise disjoint subsets of $V$. Let $G({\cal S})$ be the graph with vertex set ${\...
- 48.8k
2
votes
1
answer
154
views
Induced minors of $\{0,1\}^\omega$
Let $G=(V,E)$ be a simple, undirected graph. Suppose that ${\cal S}$ is a collection of non-empty, connected, and pairwise disjoint subsets of $V$. Let $G({\cal S})$ be the graph with vertex set ${\...
- 48.8k
2
votes
1
answer
93
views
Compactness of Hadwiger number
Is there an infinite, simple, undirected graph $G=(V,E)$ such that there is $n\in\mathbb{N}$ with the following properties?
$K_n$ is a minor of $G$, but $K_{n+1}$ is not a minor of $G$, and
if $F$ ...
- 48.8k