Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

By a well-known probabilistic argument due to Erdos, if $k>1$ is an integer then for all large enough $n$, there an asymmetric relation $R$ on $X=\lbrace 1,2, \ldots ,n \rbrace$ (i.e. $R \subseteq X^2$ and $\forall (x,y) \in R, (y,x)\not\in R$ ) such that for any $k$ elements $x_1,x_2, \ldots x_k$ in $X$, there is a $y\in X$ such that $x_1Ry, x_2Ry, \ldots ,x_kRy$ (this is the famous $S_k$" property).

Denote by $f(k,n)$ the smallest size of such a relation, when it exists (here size means the cardinality of $R$). Clearly $f(1,n)=n$ (and the optimal solutions are the cycles of length $n$). What bounds are known for $f(k,n)$ when $k>1$ ?

share|improve this question
I have a suspicion that f(2,n) <= 4n for n > 8, and that for general k 4 can be replaced by 1 + 3^(k-1) and n >= 3^k. Do you have any more bounds from the literature? Gerhard "Ask Me About System Design" Paseman, 2011.10.22 –  Gerhard Paseman Oct 23 '11 at 3:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.