Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656833 | Journal of Combinatorial Theory, Series B | 2014 | 22 Pages |
Abstract
Let H be a tournament, and let ϵâ¥0 be a real number. We call ϵ an “ErdÅs-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|V(G)|ϵ. The ErdÅs-Hajnal conjecture asserts, in one form, that every tournament H has a positive ErdÅs-Hajnal coefficient. This remains open, but recently the tournaments with ErdÅs-Hajnal coefficient 1 were completely characterized. In this paper we provide an analogous theorem for tournaments that have an ErdÅs-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 |V(G)|>1 does not contain H as a subtournament, then V(G) can be partitioned into at most c(logâ¡(|V(G)|))d transitive subsets.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Krzysztof Choromanski, Maria Chudnovsky, Paul Seymour,