9
$\begingroup$

In their 2009 paper (“On a graph property generalizing planarity and flatness”. In: Combinatorica 29.3 (May 2009), pp. 337–361. issn: 1439-6912. doi: 10.1007/s00493-009-2219-6.), van der Holst and Pendavingh defined a new minor monotone graph invariant $\sigma(G)$ for a graph $G$: the minimal integer $k$ such that every CW-complex whose 1-skeleton is $G$ admits a certain even mapping into $\mathbb R^k$.

They were able to prove $\mu(G)\leq\sigma(G)+2$, where $\mu(G)$ is the Colin de Verdière number of $G$ which is minor monotone as well (Colin de Verdière. “Sur un nouvel invariant des graphes et un critère de planaritè”. In: Journal of Combinatorial Theory, Series B 50.1 (1990), pp. 11–21. issn: 0095-8956. doi: 10.1016/0095-8956(90)90093-F.)

My main interest is in the conjecture of van der Holst and Pendavingh in that paper. They conjectured that actually $\mu(G)\leq\sigma(G)$ might hold. Question: What is known about the status of this conjecture? (I have difficulties tracing it as their new invariant $\sigma(G)$ does not seem to have a commonly agreed name yet).

$\endgroup$
9
$\begingroup$

Kaluza and Tancer have actually proved $\mu(G)\leq\sigma(G)$ in 2019: See their proof in the preprint "Even maps, the Colin de Verdière number, and representations of graphs" on arxiv. Here is the link https://arxiv.org/pdf/1907.05055.pdf

You are right, the invariant $\sigma(G)$ of Holst and Pendavingh does not seem to have an established name yet.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

I would like to add one important aspect: it was known that $\mu(G)$ and $\sigma(G)$ can deviate by a large amount for larger values $k$. Now we have the proof of the improved (sharper) bound $\mu(G)\leq\sigma(G)$, but even though this is an improvement, Kaluza and Tancer also showed that a large gap exists already for small values of $k$: They showed there is a graph $G$ such that $\mu(G)\leq7$ and $\sigma(G)\geq8$ ("Even maps, the Colin de Verdière number, and representations of graphs" on arxiv. Here is the link https://arxiv.org/pdf/1907.05055.pdf).
Now, a suspension of $G$ (adding a new vertex to $G$ and connecting it to all vertices of $G$) increases both $\mu(G)$ and $\sigma(G)$ by exactly one (unless $G$ is the complement of $K_2$). Therefore $\mu(G)\leq7$ and $\sigma(G)\geq8$ implies that for every $k \in\mathbb N$, $k \geq 7$, there must exist a graph $G_k$ with $\mu(G)\leq k$ and $\sigma(G)\geq k+1$, i.e. strict inequality for all large values of $k$. Finally, the authors also show that the gap between $\mu(G)$ and $\sigma(G)$ is asymptotically large.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Op-t´Bevers thank you, this is useful and in a certain sense speaks in favour of keeping with the Colin de Verdière invariant. However, what makes the new Holst Pendavingh invariant very attractive is their "strongly topological" definition with even functions, so they look like the natural generalization of Hanani-Tutte $\endgroup$ – soerenssen Aug 1 at 5:59
  • 2
    $\begingroup$ @soerenssen soerenssen you are right about the strongly topological definition. But I have seen Colin de Verdière characterization of embeddings in projective plane and torus. I have not yet seen such characterization for the new invariant (just flat embeddings in ${\mathbb R}^k$) $\endgroup$ – Béart Aug 1 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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