# Probability distribution for the size of an ordered set of (randomly pruned) integer pairs with intersection constraints on successive elements in the permutation

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$?

-

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?