2
$\begingroup$

Is there for every positive integer $n\in\mathbb{N}$ a finite, simple, undirected graph $G=(V,E)$ with the following property?

$G$ does not have a complete minor with more than $\frac{\delta(G)}{n}$ points (where $\delta(G)$ denotes the minimal degree).

$\endgroup$

1 Answer 1

4
$\begingroup$

Not an answer but an observation: for any fixed order $r$ of the complete minor, your question can be answered by a finite search over the set of all graphs of order at most $c_{\mathrm{Kostochka}}\sqrt{\log r}$: let any $n\in\mathbb{N}$ be given. Let any graph $G=(V,E)$ be given. Let $\delta:=\delta(G)$. Let $c=c_{\mathrm{Kostochka}}>0$ denote the absolute constant in Theorem 7.2.3 of Diestel, Graph Theory, fourth ed. Since $\mathbb{R}_{>1}\to\mathbb{R}$, $r\mapsto cr(\log r)^{1/2}$ is strictly monotone increasing, there exists a unique solution $r=r(\delta)$ to the equation $\delta=cr(\log r)^{1/2}$. Theorem 7.2.3 says that $K^{r(\delta)}\preceq G$. So we may assume that

$r(\delta)\leq \delta/n$

equivalently

$n\leq c(\log r)^{1/2}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .