Skip to main content

Tournaments with near-linear transitive subsets

Author(s): Choromanski, Krzysztof; Chudnovsky, Maria; Seymour, Paul D

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1bq2z
Abstract: Let H be a tournament, and let epsilon >= 0 be a real number. We call an “Erdos-Hajnal coefficient” for H if there exists c > 0 such that in every tournament G not containing H as a subtournament, there is a transitive subset of cardinality at least c vertical bar V(G)vertical bar(epsilon). The Erdos-Hajnal conjecture asserts, in one form, that every tournament H has a positive Erdos-Hajnal coefficient. This remains open, but recently the tournaments with Erdos-Hajnal coefficient 1 were completely characterized. In this paper we provide an analogous theorem for tournaments that have an Erdos-Hajnal coefficient larger than 5/6; we give a construction for them all, and we prove that for any such tournament H there are numbers c, d such that, if a tournament G with vertical bar V(G)vertical bar > 1 does not contain H as a subtournament, then V(G) can be partitioned into at most c(log(vertical bar V(G)vertical bar))(d) transitive subsets. (C) 2014 Elsevier Inc. All rights reserved.
Publication Date: Nov-2014
Electronic Publication Date: 8-Jul-2014
Citation: Choromanski, Krzysztof, Chudnovsky, Maria, Seymour, Paul. (2014). Tournaments with near-linear transitive subsets. JOURNAL OF COMBINATORIAL THEORY SERIES B, 109 (228 - 249. doi:10.1016/j.jctb.2014.06.007
DOI: doi:10.1016/j.jctb.2014.06.007
ISSN: 0095-8956
EISSN: 1096-0902
Pages: 228 - 249
Type of Material: Journal Article
Journal/Proceeding Title: JOURNAL OF COMBINATORIAL THEORY SERIES B
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.