Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let $T$ be a tournament on $X_n=\lbrace 1,2, \ldots ,n \rbrace$ (i.e. an asymmetric relation $<_T$ on $X_n$). Erdos's famous $S_k$ property says that for any $k$ elements $i_1<i_2< \ldots <i_k$ in $X_k$, there is an $i\in X_n$ such that $i_1<_T i, i_2 <_T i, \ldots i_n <_T i$. In view of the probabilistic argument used in the quick proof of existence of tournaments with property $S_k$, it is somehow natural to consider property $S'_k$ which is a very restrictive strengthening of $S_k$ : say that $T$ has property $S'_k$ if for any $k$ elements $i_1<i_2< \ldots <i_k$ in $X_n$, the random variable $(i_1<_T i, i_2 <_T i, \ldots, i_k <_T i)$ (which takes values in $\lbrace Yes, No\rbrace^k$) is uniformly distributed when $i$ varies in $X_n \setminus \lbrace i_1,i_2, \ldots ,i_k \rbrace$.

My question, then, is : for any $k$ does there exist $n>k$ and a finite tournament on $X_n$ that has property $S'_k$ ? An obvious necessary condition is that $n \equiv k ({\rm mod} \ 2^k)$.

share|cite|improve this question

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.