2
$\begingroup$

For any integer $n$, let ${\cal G}_n$ denote the set of simple, undirected graphs $G = (V, E)$ where $V = \{1,\ldots,n\}$. The Hadwiger number $\eta(G)$ of a finite graph $G$ is the maximum integer $m$ such that the complete graph $K_m$ is a minor of $G$. The expected value $E_n$ of the Hadwiger number of a graph on $n$ vertices is defined by $$E_n = \frac{1}{|{\cal G}_n|}\sum_{G\in{\cal G_n}}\eta(G).$$

Do we have $\lim\sup_{n\to\infty}E_n/n > 0$? If not, what is an example of a non-decreasing function $f:\mathbb{N}\to\mathbb{N}$ such that $0 < \lim\sup_{n\to\infty}\frac{E_n}{f(n)} < \infty$?

Note. The equivalent question for the chromatic number $\chi(\cdot)$ has been treated here and here.

$\endgroup$

0

You must log in to answer this question.