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
Full metadata record
DC FieldValueLanguage
dc.contributor.authorChoromanski, Krzysztof-
dc.contributor.authorChudnovsky, Maria-
dc.contributor.authorSeymour, Paul D.-
dc.date.accessioned2018-07-20T15:11:20Z-
dc.date.available2018-07-20T15:11:20Z-
dc.date.issued2014-11en_US
dc.identifier.citationChoromanski, 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.007en_US
dc.identifier.issn0095-8956-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1bq2z-
dc.description.abstractLet 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.en_US
dc.format.extent228 - 249en_US
dc.language.isoen_USen_US
dc.relation.ispartofJOURNAL OF COMBINATORIAL THEORY SERIES Ben_US
dc.rightsAuthor's manuscripten_US
dc.titleTournaments with near-linear transitive subsetsen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1016/j.jctb.2014.06.007-
dc.date.eissued2014-07-08en_US
dc.identifier.eissn1096-0902-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
pseudo.pdf193.5 kBAdobe PDFView/Download


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