In traditional “search problems”, an agent aims at exploring a graph in order to find a hidden object as fast as possible. We consider here the Bayesian repeated scenario with several iid instance of the same basic search problem. The objective is, within a given amount of time, to find as many objects as possible with the possibility to leave an instance for the next one at any moment.

We also consider the non-bayesian case with a variant of regret minimization. We provide and analyze several algorithms with fast rates of convergence and/or guaranteed efficiency.

For the game of cops and robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time and that there exist graphs in which this capture time is tight. When k ≥ 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O( n^(k+1) ), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. We answer the question of Bonato and Nowakowski on the negative, proving that the O(n^(k+1) ) bound is asymptotically tight for any constant k ≥ 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.

La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années. Nous présenterons ici un survol des liens bijectifs avec des familles de cartes planaires, en particulier avec les triangulations (pour les intervalles classiques) et avec les cartes biparties (pour les intervalles dits “nouveaux”), en mettant l'accent sur des symétries de distribution de paramètres que ces bijections révèlent (la partie sur les intervalles nouveaux est basée sur des discussions récentes avec Frédéric Chapoton).