首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On the maximum cardinality of a consistent set of arcs in a random tournament
Authors:W Fernandez de la Vega
Institution:Laboratoire de Recherche en Informatique, E.R.A. 452, Bâtiment 490, Université de Paris-Sud, Orsay, France
Abstract:For any tournament T on n vertices, let h(T) denote the maximum number of edges in the intersection of T with a transitive tournament on the same vertex set. Sharpening a previous result of Spencer, it is proved that, if Tn denotes the random tournament on n vertices, then, P(h(Tn) ≤ 12(2n) + 1.73n32) → 1 as n → ∞.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号