MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.