Searching for Sorted Sequences and Kings in Tournaments
Date
2006-06
Authors
Shen, Jian
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A tournament is a directed graph on which there is a directed edge between each pair of vertices. A king in a tournament is a vertex that can reach every other vertex by a directed path of length at most two. The main research of this project is to study the complexity of finding a king in any given tournament. PI and Yan (a graduate student in China) proved the following: Every vertex in a random digraph with n vertices and n^{3/2+o(1)} edges is almost a king. There is almost no king in a random digraph with n vertices and n^{3/2} edges. Thus, the threshold function for the number of edges in a random digraph to have a king is determined. In 2006, PI have 4 refereed journal papers, 1 accepted refereed journal paper, 1 submitted journal paper, and 1 paper in refereed conference proceedings. PI submitted 3 external grant proposals (with all pending). PI gave 1 invited plenary conference talk, 2 contributed conference talks, 2 invited colloquium talks at other universities, and 3 talks at Texas State University. PI is the organizer of Discrete Math Seminar in the Mathematics Department. PI brought two visiting professors (Dr. Guangzhou CSU and Dr. Yanking Shoo) to the Texas State University in 2006.
Description
Research Enhancement Program Final Report
Keywords
tournament, kings, sequences
Citation
Shen, J. (2006). Searching for sorted sequences and kings in tournaments. Research Enhancement Program, Texas State University, San Marcos, Texas.