Abstract Let K be a convex body (a compact convex set) in $$\mathbb {R}^d$$ R d , that contains a copy of another body S in every possible orientation. Is it always possible to continuously move any one copy of S into another, inside K? As a stronger question, is it always possible to continuously select, for each orientation, one copy of S in that orientation? These questions were asked by Croft. We show that, in two dimensions, the stronger question always has an affirmative answer. We also show that in three dimensions the answer is negative, even for the case when S is a line segment – but that in any dimension the first question has a positive answer when S is a line segment. And we prove that, surprisingly, the answer to the first question is negative in dimensions four and higher for general S.

Abstract. How many random transpositions (meaning that we swap given pairs of elements with given probabilities independently) are needed to ensure that each element of [Formula: see text] is uniformly distributed—in the sense that the probability that [Formula: see text] is mapped to [Formula: see text] is [Formula: see text] for all [Formula: see text] and [Formula: see text]? And what if we insist that each pair is uniformly distributed? In this paper we show that the minimum for the first problem is about [Formula: see text], with this being exact when [Formula: see text] is a power of 2. For the second problem, we show that, rather surprisingly, the answer is not quadratic: [Formula: see text] random transpositions suffice. We also show that if we ask only that the pair [Formula: see text] is uniformly distributed, then the answer is [Formula: see text]. This proves a conjecture of Groenland, Johnston, Radcliffe, and Scott.

Given an edge-coloured graph, we say that a subgraph is rainbow if all of its edges have different colours. Let $\operatorname{ex}(n,H,$rainbow-$F)$ denote the maximal number of copies of $H$ that a properly edge-coloured graph on $n$ vertices can contain if it has no rainbow subgraph isomorphic to $F$. We determine the order of magnitude of $\operatorname{ex}(n,C_s,$rainbow-$C_t)$ for all $s,t$ with $s\not =3$. In particular, we answer a question of Gerbner, M\'esz\'aros, Methuku and Palmer by showing that $\operatorname{ex}(n,C_{2k},$rainbow-$C_{2k})$ is $\Theta(n^{k-1})$ if $k\geq 3$ and $\Theta(n^2)$ if $k=2$. We also determine the order of magnitude of $\operatorname{ex}(n,P_\ell,$rainbow-$C_{2k})$ for all $k,\ell\geq 2$, where $P_\ell$ denotes the path with $\ell$ edges.

We consider the problem of local planning in fixed-horizon Markov Decision Processes (MDPs) with a generative model under the assumption that the optimal value function lies close to the span of a feature map. The generative model provides a restricted, “local” access to the MDP: The planner can ask for random transitions from previously returned states and arbitrary actions, and the features are also only accessible for the states that are encountered in this process. As opposed to previous work (e.g. Lattimore et al. (2020)) where linear realizability of all policies was assumed, we consider the significantly relaxed assumption of a single linearly realizable (deterministic) policy. A recent lower bound by Weisz et al. (2020) established that the related problem when the action-value function of the optimal policy is linearly realizable requires an exponential number of queries, either in $H$ (the horizon of the MDP) or $d$ (the dimension of the feature mapping). Their construction crucially relies on having an exponentially large action set. In contrast, in this work, we establish that $\poly(H,d)$ planning is possible with state value function realizability whenever the action set has a constant size. In particular, we present the TensorPlan algorithm which uses $\poly((dH/\delta)^A)$ simulator queries to find a $\delta$-optimal policy relative to any deterministic policy for which the value function is linearly realizable with some bounded parameter (with a known bound). This is the first algorithm to give a polynomial query complexity guarantee using only linear-realizability of a single competing value function. Whether the computation cost is similarly bounded remains an interesting open question. We also extend the upper bound to the near-realizable case and to the infinite-horizon discounted MDP setup. The upper bounds are complemented by a lower bound which states that in the infinite-horizon episodic setting, planners that achieve constant suboptimality need exponentially many queries, either in the dimension or the number of actions.