Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Update: To write a quick preamble, this question is basically asking that, if you take all possible pairs of some set of characters, call these pairs elements of the set $S$, and if you throw out some of the elements in $S$ with uniform probability, what the probability distribution is for the longest chain of elements you can construct, drawing from this pruned set, s.t. each element has exactly one character in common with both the previous element in the permutation and the next element in the permutation (noting that all elements/pairs must be distinct).

Imagine I have a set, $(s_1, ..., s_{(N^2)}) \in S$, of all possible ordered pairs of identical or non-identical integers over the domain $s_i \in [1, N]$. For example, if $N = 2$, we would have the set: $S =$ {{1,1},{1,2},{2,1},{2,2}}, where $||S|| = 2^2 = 4$.

Let $S_p$ be a "pruned" version of the set $S$, consisting of $M = ||S_p||$ elements, $M \leq N^2$, selected with uniform probability from the set $S$. Let $Q$ be an ordered set of size $R = ||Q||$, $R \leq M$, where the function $P(Q, k)$ yields the $k$th element from the ordered set $Q$.

Consider some $Q \subseteq S_p$ where, for $1 < k < M$, we have that:

$||P(Q, k-1) \cap P(Q, k)|| = 1$ and $||P(Q, k) \cap P(Q, k+1)|| = 1$

What probability distribution do we have for the size of the ordered set $Q$, i.e. $R \leq M$? Are there constraints we can place on a (deterministic) pruning function for $S_p$ that guarantees $R = M$?

Is there an algorithm (with known time complexity) for finding the largest ordered set $Q$, with the above constraints, provided some $S_p$? What if we can control the pruning function for $S_p$?

share|improve this question
add comment

1 Answer

Here's an attempt to translate your problem into a language that is more intuitive for graph theorists:

Let $\Gamma$ be a directed random graph (with loops) of order $n$, where each arc is chosen independently with a fixed probability $p$. Let $x$ be the maximal length of a trail in $\Gamma$ (a path in the line graph $\Delta$ of $\Gamma$).

  • How is $x$ distributed?
  • Under what conditions does $\Delta$ contain a Hamiltonian path?
share|improve this answer
add comment

Your Answer


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.