MathDB

A directed graph with a property.

Source: Miklos Schweitzer 2015, problem 3

April 7, 2016

combinatoricsgraph theory

Problem Statement

Let

{A}

be a finite set and

{\rightarrow}

be a binary relation on it such that for any

{a,b,c \in A}

, if

{a\neq b}, {a \rightarrow c}

and

{b \rightarrow c}

then either

{a \rightarrow b}

or

{b \rightarrow a}

(or possibly both). Let

{B,\,B \subset A}

be minimal with the property: for any

{a \in A \setminus B}

there exists

{b \in B}

, such that either

{a \rightarrow b}

or

{b \rightarrow a}

(or possibly both). Supposing that

{A}

has at most

{k}

elements that are pairwise not in relation

{\rightarrow}

, prove that

{B}

has at most

{k}

elements.

Back to Problems View on AoPS