Abstract. For an oriented graph [Formula: see text] and a set [Formula: see text], the inversion of [Formula: see text] in [Formula: see text] is the digraph obtained by reversing the orientations of the edges of [Formula: see text] with both endpoints in [Formula: see text]. The inversion number of [Formula: see text], [Formula: see text], is the minimum number of inversions which can be applied in turn to [Formula: see text] to produce an acyclic digraph. Answering a recent question of Bang-Jensen, da Silva, and Havet we show that, for each [Formula: see text] and tournament [Formula: see text], the problem of deciding whether [Formula: see text] is solvable in time [Formula: see text], which is tight for all [Formula: see text]. In particular, the problem is fixed-parameter tractable when parameterized by [Formula: see text]. On the other hand, we build on their work to prove their conjecture that for [Formula: see text] the problem of deciding whether a general oriented graph [Formula: see text] has [Formula: see text] is NP-complete. We also construct oriented graphs with inversion number equal to twice their cycle transversal number, confirming another conjecture of Bang-Jensen, da Silva, and Havet, and we provide a counterexample to their conjecture concerning the inversion number of so-called dijoin digraphs while proving that it holds in certain cases. Finally, we asymptotically solve the natural extremal question in this setting, improving on previous bounds of Belkhechine, Bouaziz, Boudabbous, and Pouzet to show that the maximum inversion number of an [Formula: see text]-vertex tournament is [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].

Let $\mathcal F$ be an antichain of finite subsets of $\mathbb N$. How quickly can the quantities $|\mathcal{F}\cap 2^{[n]}|$ grow as $n\to\infty$? We show that for any sequence $(f_n)_{n\ge n_0}$ of positive integers satisfying $\sum_{n=n_0}^\infty f_n/2^n \le 1/4$ and $f_n\le f_{n+1}\le 2f_n$, there exists an infinite antichain $\mathcal{F}$ of finite subsets of $\mathbb{N}$ such that $|\F\cap 2^{[n]}| \geq f_n$ for all $n\ge n_0$. It follows that for any $\varepsilon>0$ there exists an antichain $\mathcal{F}\subseteq 2^{\mathbb{N}}$ such that $\liminf_{n \to \infty} |\mathcal{F}\cap 2^{[n]}| \cdot \big(\frac{2^n}{n\log^{1+\varepsilon} n}\big)^{-1} > 0.$ This resolves a problem of Sudakov, Tomon, and Wagner in a strong form and is essentially tight.