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, as n → ∞. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|