Seeking proof of the Cuckoo Cycle Conjecture Allow me to introduce the Cuckoo Cycle Proof of Work, and conclude with a closely related Conjecture about random graphs, which I hope someone can find a proof for.
Cuckoo Cycle is named after the Cuckoo Hashtable, in which each data item can be stored at two possible locations, one in each of two arrays. A hash function maps the pair of item and choice of array to its location in that array. When a newly stored item finds both its locations already occupied, one is kicked out and replaced by the new item. This forces the kicked-out item to move to its alternate location, possibly kicking out yet another item. Problems arise if the corresponding Cuckoo graph, a bipartite graph with array locations as nodes and item location pairs as edges, has cycles.
While $n$ items, whose edges form a cycle, could barely be stored in the table, any $n+1$st item mapping within the same set of locations (a chord in the cycle) would not fit, as the pigeonhole principle tells us.
In the Proof-of-Work problem, we typically set $n \ge 29$, and use edge indices (items) $0 \dots N-1$, where $N = 2^n$. The endpoints of edge $i$ are (siphash(i|0) % N, siphash(i|1) % N), with siphash being a popular keyed hash function. A solution is a cycle of length $L$ in this bipartite Cuckoo graph, where typically $L = 42$.
Cuckoo Cycle solvers spend nearly all cycles on edge trimming; identifying and removing edges that end in a leaf node (of degree 1), as such edges cannot be part of a cycle. Trimming rounds alternate between the two node partitions.
The fraction $f_i$ of remaining edges after $i$ trimming rounds (in the limit as $N$ goes to infinity) appears to obey

The Cuckoo Cycle Conjecture: $f_i = a_{i-1} * a_i$, where $a_{-1} = a_0 = 1$, and $a_{i+1} = 1 - e^{-a_i}$

$f_i$ could equivalently be defined as the fraction of edges whose first endpoint is the middle of a (not necessarily simple) path of length $2i$. So far I have only been able to prove the conjecture for $i \le 3$.
For instance, for i = 1, the probability that an edge endpoint is not the endpoint
of any other edge is (1-1/N)N-1 ~ 1/e.
Here's hoping someone finds an elegant proof...
 A: Theorem. Let $f_i$ be expected value of fraction of remaining edges after $i$ trimming rounds for Cuckoo graph; here $i \in \mathbb{N}_0$.
Then $f_i = a_i a_{i-1}$; here $a_{-1} = a_{0} = 1$, $a_{i+1} = (1-e^{-a_i})$.
Proof. The proof is by induction over the trimming round $i$.
For $i = 0$ it is evident.
Let us prove for $i+1$.
By $E$ denote a set of edges for initial Cuckoo graph.
By $E'$ denote a set of edges that end in a leaf node for trimmed graph after $i-1$ rounds, $i > 0$.
Let us introduce indicator random variable for edge $e$:
$$
\xi(e) = \begin{cases}
1,   & e \in E' \\
0,   & e \not\in E'. \\
\end{cases}
$$
Consider the following Bernoulli scheme for edge $e$. Succes is $e \in E'$. The probability of success is $\frac{1}{|E|}$. Then the probability that number of successes on the $(|E|a_i)^{th}$ trial is equal to one the following:
$$
C^1_{|E|a_i} \left(\frac{1}{|E|}\right)^1 \left(1 - \frac{1}{|E|}\right)^{|E|a_i-1} = \frac{a_i}{e^{a_i}}
$$
as $|E| \to \infty$.
So $\mathbb{E}[\xi(e)] = \frac{a_i}{e^{a_i}}$.
Then using linearity of expectation, we get $\mathbb{E}[|E'|] = \frac{|E|a_i}{e^{a_i}}$.
Further by the inductive assumption:
$f_{i+1} = a_{i+1}a_i = (1-e^{-a_i})a_i = (a_i-a_ie^{-a_i})$.
Then using linearity of expectation, we get $f_{i+1}|E| = a_{i+1}a_i|E| = (a_i-a_ie^{-a_i})|E|$ $=$ $a_i|E| - |E|a_ie^{-a_i}$.
It follows that $a_{i+1}a_i|E| = a_i|E| - |E'|$ and it is clear.
Finally, we get the following: $a_{i+1} = 1 - a_ie^{-a_i}$.
This completes the proof of theorem.
