Show simple item record

dc.contributor.authorShen, Jian ( )en_US
dc.date.accessioned2008-04-07T10:06:37Z
dc.date.available2012-02-24T10:06:02Z
dc.date.issued2006-06-01en_US
dc.identifier.urihttps://digital.library.txstate.edu/handle/10877/2806
dc.descriptionResearch Enhancement Program Final Reports.
dc.description.abstractA 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.
dc.formatText
dc.format.extent1 page
dc.format.medium1 file (.pdf)
dc.language.isoen
dc.subjectTournamenten_US
dc.subjectKingsen_US
dc.subjectSequencesen_US
dc.titleSearching for Sorted Sequences and Kings in Tournamentsen_US
txstate.documenttypeResearch Report


Download

Thumbnail

This item appears in the following Collection(s)

Show simple item record