Atlas home || Conferences | Abstracts | about Atlas

21st Cumberland Conference on Graph Theory, Combinatorics, and Computing ---In Honor of Mike Plummer's 70th Birthday
May 15-17, 2008
Vanderbilt University
Nashville, TN, USA

Organizers
Mark Ellingham and Gexin Yu

View Abstracts
Conference Homepage

A Version of the Secretary Problem on a Complete Bipartite Graph with Random Size of Partite Sets.
by
Ewa Kubicka
University of Louisville
Coauthors: Grzegorz Kubicki

Consider a complete bipartite graph G of odd order 2n+1 in which the size of one partite set is given by a binomial distribution with p = 1/2. The vertices of G are observed one by one in a random order and the subgraph induced by them is revealed. We find the optimal stopping time maximizing the probability of stopping on a vertex from the smaller partite set. The probability of success is given and its asymptotic behavior is established.

Date received: April 18, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-55.