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].

Abstract. A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the “usual suspects.” Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. Using the same tools, we also study the treewidth of graphs [Formula: see text] that have a circular drawing whose crossing graph is well-behaved in some way. In this setting, we show that if the crossing graph is [Formula: see text]-minor-free, then [Formula: see text] has treewidth at most [Formula: see text] and has no [Formula: see text]-topological minor. On the other hand, we show that there are graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are 2-degenerate.

In 1967, Erdös asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An observation of Erdös and Hajnal together with Shearer's classical upper bound for the off-diagonal Ramsey number $R(3, t)$ shows that $f(n)$ is at most $(2 \sqrt{2} + o(1)) \sqrt{n/\log n}$. We improve this bound by a factor $\sqrt{2}$, as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight follows, and these results confirm a conjecture of Cames van Batenburg et al. [ Electron. J. Combin., 27 (2020), P2.34].