7
$\begingroup$

What is the maximum number of edges of an $n$-vertex linklessly embeddable graph?

A more general question is the following. What is the maximum number of edges of an $n$-vertex graph with Colin de Verdière number $\mu$?

A related question would be the following. Is there a fixed space (say a 2-manifold) such that graphs which embed linklessly into $\mathbb{R}^3$ are characterized by embedding into that space? This is purely out of curiosity.

Thanks.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

For your first question, Mader proved that all $K_6$-minor-free graphs (which includes all linklessly embeddable graphs) on $n$ vertices have at most $4n-10$ edges (thanks to David Eppstein for the reference).

The answer to your second question is no. This follows because Apex graphs are linklessly embeddable, and one easily checks that they do not have bounded genus.

For your more general question, you can apply the graph minors theory of Robertson and Seymour. That is, for every proper minor-closed class of graphs $\mathcal{M}$, there is a constant $C$, such that every graph in $\mathcal{M}$ with $n$ vertices has at most $Cn$ edges. This is a vast generalization of the fact that planar graphs on $n$ vertices have at most $3n-6$ edges. Most minor-closed classes will not have bounded genus. This essentially follows from the necessity of apex vertices and vortices in the Graph Minors Structure theorem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks Tony. Can you please give me a reference for the $Cn$ bound? Or sketch how a proof would work? $\endgroup$
    – Salman Parsa
    Commented Sep 26, 2014 at 13:16
  • $\begingroup$ The Sachs' paper you referred to leaves the question as an open problem. It just says that there are some graphs linklessly embeddable with that many edges. $\endgroup$
    – Salman Parsa
    Commented Sep 26, 2014 at 13:29
  • 1
    $\begingroup$ For the $Cn$ bound you do not really need the full strength of the Graph Minors Structure. Once you exclude a single graph as a minor, you automatically go down to linear density. This follows from a result of Kostochka and Thomason. That is, there is an absolute constant $C$ such that for all $t$ and all graphs $G$, if $G$ does not have a $K_t$-minor, then $G$ has at most $Ct\sqrt{\log t} |V(G)|$ edges. $\endgroup$
    – Tony Huynh
    Commented Sep 26, 2014 at 13:39
  • $\begingroup$ Thanks for the information on the Sachs' paper. Wikipedia claims that the paper does prove the claim in question, so that might need to be corrected. Perhaps they just linked to the wrong reference though. I'll do some more digging when I have the chance. $\endgroup$
    – Tony Huynh
    Commented Sep 26, 2014 at 13:41
  • 1
    $\begingroup$ Here is a link to the Kostochka/Thomason result (note they proved the same result independently). math.uiuc.edu/~kostochk/docs/old/cca84.pdf $\endgroup$
    – Tony Huynh
    Commented Sep 26, 2014 at 13:44
8
$\begingroup$

The reference given in the Wikipedia article on linkless embedding for the $4n-10$ bound on the number of edges in a linkless embeddable graph is Mader, W. (1968), "Homomorphiesätze für Graphen", Mathematische Annalen 178 (2): 154–168, doi:10.1007/BF01350657. Apparently Mader proves this bound more generally for $K_6$-minor-free graphs. As the Wikipedia article also states, the example of apex graphs shows that this is tight.

As for the Colin de Verdière invariant: it is known to be at least the size of the largest clique minor minus one – e.g. see http://homepages.cwi.nl/~lex/files/cdvsurvey_new2.pdf – and combining this with the Kostochka/Thomason results cited by Tony Huynh shows that the edge density can grow at most slightly superlinearly as a function of the CdV invariant.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks David. I +1ed you, and edited my answer accordingly. $\endgroup$
    – Tony Huynh
    Commented Sep 29, 2014 at 17:15

You must log in to answer this question.

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