Hostname: page-component-7b7567c8c-jswmv Total loading time: 0 Render date: 2026-11-15T20:08:23.976Z Has data issue: false hasContentIssue false

Percolation and best-choice problem for powers of paths

Published online by Cambridge University Press:  22 June 2017

Fabricio Siqueira Benevides*
Affiliation:
Federal University of Ceará
Małgorzata Sulkowska*
Affiliation:
Wrocław University of Science and Technology
*
* Postal address: Department of Mathematics (Bloco 914), Federal University of Ceará, Av. Humberto Monte, s/n, 60.455-760, Fortaleza, Ceará, Brazil. Email address: fabricio@mat.ufc.br
** Postal address: Department of Computer Science, Faculty of Fundamental Problems of Technology, Wrocław University of Science and Technology, Grunwaldzki Sq. 13, 50-377 Wrocław, Poland. Email address: malgorzata.sulkowska@pwr.edu.pl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The vertices of the kth power of a directed path with n vertices are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already appeared. The selector's aim is to choose online the maximal vertex (i.e. the vertex with no outgoing edges). We give upper and lower bounds for the asymptotic behaviour of p n,k n 1/(k+1), where p n,k is the probability of success under the optimal algorithm. In order to derive the upper bound, we consider a model in which the selector obtains some extra information about the edges that have already appeared. We give the exact asymptotics of the probability of success under the optimal algorithm in this case. In order to derive the lower bound, we analyse a site percolation process on a sequence of the kth powers of a directed path with n vertices.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2017