It is a classical result that a random permutation of n elements has, on average, about log n cycles. We generalise this fact to all directed d-regular graphs on n vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}(n/\sqrt {\log d} )$ due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1 + {\mathcal{O}}((\log d)/d)) \cdot n$ if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least Ω ( Δ 2 log ⁡ ( n / Δ ) / log ⁡ Δ ) queries to reconstruct n -vertex graphs of maximum degree Δ with success probability at least 1/2, and we further improve this lower bound to Ω ( Δ 2 log ⁡ ( n / Δ ) ) for randomised non-adaptive algorithms. We also prove that deterministic non-adaptive algorithms require at least Ω ( Δ 3 log ⁡ n / log ⁡ Δ ) queries. This improves bounds of Konrad, O'Sullivan, and Traistaru, and answers one of their questions. The proof of the lower bound for deterministic non-adaptive algorithms relies on a connection to cover-free families, for which we also improve known bounds.

Abstract. Given a simple Eulerian binary matroid [Formula: see text], what is the minimum number of disjoint circuits necessary to decompose [Formula: see text]? We prove that [Formula: see text] many circuits suffice if [Formula: see text] is the complete binary matroid, for certain values of [Formula: see text], and that [Formula: see text] many circuits suffice for general [Formula: see text]. We also determine the asymptotic behavior of the minimum number of circuits in an odd-cover of [Formula: see text].

Abstract. Let [Formula: see text] be a set of [Formula: see text] points on the real line. Suppose that each pairwise distance is known independently with probability [Formula: see text]. How much of [Formula: see text] can be reconstructed up to isometry? We prove that [Formula: see text] is a sharp threshold for reconstructing all of [Formula: see text], which improves a result of Benjamini and Tzalik. This follows from a hitting time result for the random process where the pairwise distances are revealed one by one uniformly at random. We also show that [Formula: see text] is a weak threshold for reconstructing a linear proportion of [Formula: see text].

We consider learning policies online in Markov decision processes with the long-run average reward (a.k.a. mean payoff). To ensure implementability of the policies, we focus on policies with finite memory. Firstly, we show that near optimality can be achieved almost surely, using an unintuitive gadget we call forgetfulness. Secondly, we extend the approach to a setting with partial knowledge of the system topology, introducing two optimality measures and providing near-optimal algorithms also for these cases.