2
$\begingroup$

For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the line graph $L(K_n)$ of the complete graph $K_n$ as follows:

  • $V(L(K_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b \big\}$;
  • $E(L(K_n)) = \big\{\{x,y\}: x,y\in V(L(K_n)) \text{ and } x\cap y \neq \emptyset\big\}$.

For any graph $G=(V,E)$ the Hadwiger number $\eta(G)$ is the largest $n\in \omega$ such that $K_n$ is a minor of $G$.

In this post it is shown that $\eta(L(K_5)) \geq 6$, and it's easy to see that $\eta(L(K_n)) \geq n+1$ for $n\geq 5$.

Question: Given a positive integer $k\in\mathbb{N}$, is there $n\in \mathbb{N}$ such that $\eta(L(K_n)) \geq k\cdot n$?

$\endgroup$
1
  • $\begingroup$ You have $K_5$ in the expression following "easy to see" which seems wrong. $\endgroup$ Apr 13, 2015 at 10:25

2 Answers 2

2
$\begingroup$

Claim. For all even $n \geq 4$, $\eta(L(K_n)) \geq \frac{3n-4}{2}$ and for all odd $n \geq 3, \eta(L(K_n)) \geq \frac{3n-3}{2}$

Proof. A clique-minor of size $k$ in $L(K_n)$ corresponds to $k$ edge-disjoint connected subgraphs of $K_n$ which pairwise intersect.

Let $n$ be even. For our $\frac{3n-4}{2}$ subgraphs we first take the $n-1$ edges of a star centered at $x$. By an old theorem of Walecki, the edges of $K_n-x$ can be decomposed into Hamiltonian cycles. There are $\frac{1}{2}(n-2)$ such cycles, giving us $\frac{3n-4}{2}$, as required.

For $n$ odd, we use the same argument but take a Hamiltonian path decomposition of $K_n-x$ instead.

$\endgroup$
2
  • $\begingroup$ Thanks - can you extend this argument to show that for some $n\in\mathbb{N}$ we have $L(K_n) \geq 2n$? (Sorry - I have edited the original question to make it more precise.) $\endgroup$ Apr 13, 2015 at 11:31
  • $\begingroup$ You're welcome. Sorry, off the top of my head I don't see how to get a lower bound of $2n$. I'll give it some thought when I get a chance. $\endgroup$
    – Tony Huynh
    Apr 15, 2015 at 13:00
4
$\begingroup$

Here is an idea for a yes answer: put $k$ walkers at every vertex. Order the edges randomly, and also randomly pick an orientation on each edge randomly. Now in order, walk the walker across the current edge who has been sitting at the starting vertex the longest (if the vertex has at least one walker). This should give $kn$ edge-disjoint walks of length $\sim \frac{n}{2k}$ which look very similar to random walks, so they should pairwise intersect.

$\endgroup$
1
  • $\begingroup$ That's a good start. Any proof of this would be appreciated! $\endgroup$ Apr 18, 2015 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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