1
$\begingroup$

Let $n \in \mathbb{N}$ and $G := \{1,2,...,n\}$. Now let $P_2(G)$ be a power set of $G$ but only with sets of cardinality $2$, e.g. if $n = 3$ then $P_2(G) = \{ \{1, 2\}, \{1, 3\}, \{2, 3\} \}$.

Now I'd like to order these sets in a list so adjacent sets are disjoint. This only works for $n > 4$.

Furthermore given a partially filled list, I want to be able to increase $n$ and therefore creating more pairs which need to be appended to the end of the list. The existing order of the list cannot be altered. If collisions can not be avoided, they need to be minimal.

e.g. the partial list

({1,2}, {3,4}, {5,1}, {3,2})

for $n = 5$ is given and $n$ is increased by 1:

({1,2}, {3,4}, {5,1}, {3,2}, {6,1}, {3,5}, {6,2}, {1,4}, ...)

Can this problem be solved in polynomial time?

I thought of the following greedy algorithm:

  1. pick the least used number that is not a subset of the previous set
  2. if there are multiple least used numbers, pick the one that has the highest distance to its last use
$\endgroup$
4
  • $\begingroup$ How many new pairs are to be added when $n$ increases? $\endgroup$
    – Russel
    Feb 27 at 15:26
  • $\begingroup$ @Russel when $n$ increases by $1$ there are always $n-1$ new pairs. The total amount of pairs is $\frac{n^2-n}{2}$. $\endgroup$
    – rn42v
    Feb 27 at 15:40
  • $\begingroup$ If this is the case I am wondering why your partial list for $n=5$ did not include {4,5}, {5,2}, etc $\endgroup$
    – Russel
    Feb 27 at 16:01
  • 1
    $\begingroup$ The usual rule is one question per post. Also, your second question is a bit vague. $\endgroup$ Feb 27 at 18:07

1 Answer 1

3
$\begingroup$

You are asking two questions. I will only answer the first. What you are looking for is a Hamiltonian path in the Kneser graph $K(n,2)$.

When $n = 5$, this is the Petersen graph, which contains a Hamiltonian path (though not a Hamiltonian cycle).

When $n \ge 6$, the existence of a Hamiltonian cycle was proved by Heinrich and Wallis, Hamiltonian cycles in certain graphs, using Ore's theorem; in fact, the special case known as Dirac's theorem suffices. Dirac's theorem states that a graph on $N$ vertices with miniimal degree $N/2$ is Hamiltonian (has a Hamiltonian cycle). The Kneser graph $K(n,2)$ contains $\binom{n}{2}$ vertices and is $\binom{n-2}{2}$-regular. A simple calculation shows that $2\binom{n-2}{2} \geq \binom{n}{2}$ when $n \ge 8$, and so $K(n,2)$ is Hamiltonian for $n \ge 8$. Since Ore's theorem has an algorithmic proof, such a Hamiltonian cycle can be constructed efficiently. For the remaining two cases, $n = 6$ and $n = 7$, Heinrich and Wallis give the following Hamiltonian cycles: $$ 25, 16, 23, 45, 12, 34, 56, 13, 24, 35, 46, 15, 26, 14, 36 \\ 25, 37, 12, 34, 56, 17, 23, 45, 67, 13, 24, 35, 46, 57, 16, 27, 36, 47, 15, 26, 14 $$

$\endgroup$

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.