Excluding pairs of tournaments

Abstract: The ErdH{o}s-Hajnal conjecture states that for every given undirected graph

H

there exists a constant

c (H) > 0

such that every graph

G

that does not contain

H

as an induced subgraph contains a clique or a stable set of size at least

| V (G) |^{c (H)}

. The conjecture is still open. Its equivalent directed version states that for every given tournament

H

there exists a constant

c (H) > 0

such that every

H

-free tournament

T

contains a transitive subtournament of order at least

| V (T) |^{c (H)}

. We prove in this paper that

H_{1}, H_{2}

-free tournaments

T

contain transitive subtournaments of size at least

| V (T) |^{c (H_{1}, H_{2})}

for some

c (H_{1}, H_{2}) > 0

and several pairs of tournaments:

H_{1}

,

H_{2}

. In particular we prove that

H, H^{c}

-freeness implies existence of the polynomial-size transitive subtournaments for several tournaments

H

for which the conjecture is still open (

H^{c}

stands for the extit{complement of

H

}). To the best of our knowledge these are first nontrivial results of this type.

Recommendations

Cited In (11)

This page was built for publication: Excluding pairs of tournaments