Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A comb can be defined by a handle $H$ and a number of teeths $T_1,T_2,\dots,T_t$ such that:

  • $H,T_1,T_2,\dots,T_t \subseteq V$
  • $T_j \setminus H \neq \emptyset$ $\,\,\, \forall 1 \leq j \leq t$
  • $T_j \cap H \neq \emptyset$ $\,\,\, \forall 1 \leq j \leq t$
  • $T_i \cap T_j = \emptyset$ $\,\,\, \forall 1 \leq i < j \leq t$
  • $t \geq 3$ and odd

A comb inequality states that:

$$x(E(H)) + \sum_{j=1}^{t} x(E(T_j)) \leq |H| + \sum_{j=1}^{t} |T_j| - \frac{3t+1}{2}$$

Comb inequalities are valid inequalities for the TSP.

I'm looking for a simple explanation of why these inequalities are valid for any hamiltonian cycle. I'm not looking for a formal proof. A simple, informal and intuitive explanation will work.

Since comb inequalities generalize 2-matching inequalities, perhaps this can be better explained by showing the special case and then extending it to the general case.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Here $x(E(S))$ is the number of edges in the cycle whose vertices are both in set $S$ of vertices. For any set $S$ of vertices, $x(E(S)) = |S| - d(S)/2$, where $d(S)$ is the number of edges of the cycle with one vertex in $S$ and one out. Thus $$ x(E(H)) + \sum_i x(E(T_i)) = |H| + \sum_i |T_i| - \frac{1}{2} \left(d(H) + \sum_i d(T_i)\right)$$ The inequality then says $$d(H) + \sum_i d(T_i) \ge 3t + 1$$ For each $i$ let $d_i(H)$ be the number of edges with one vertex in $H \cap T_i$ and one outside $H$. Then $d(H) \ge \sum_i d_i(H)$. Now it's not hard to see that $d_i(H) + d(T_i) \ge 3$ (think of the various ways the cycle can enter and leave $H \cap T_i$ and $T_i \backslash H$), so that gives us $d(H) + \sum_i d(T_i) \ge 3t$. But $d(H)$ and $d(T_i)$ are all even and $3t$ is odd, so we can't have equality here: we must have $d(H) + \sum_i d(T_i) \ge 3t+1$.

share|improve this answer
    
Is it ok to say that teeths are a way of forcing a predefined number of enters/exits from the handle? –  aromero Nov 24 '12 at 19:20
    
No, there might be just one entrance to and exit from the handle, but then the teeth get more entrances and exits. –  Robert Israel Nov 25 '12 at 2:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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