2
$\begingroup$

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$ ?

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Oct 23, 2011 at 3:12

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.