Name
Abstract | ||
|---|---|---|
A sequence X = {xi}ni=1 over an alphabet containing t symbols is t-universal if every permutation of those symbols is contained as a subsequence. Kleitman and Kwiatkowski showed that the minimum length of a t-universal sequence is (1 − o(1))t2. In this note we address a related Ramsey-type problem. We say that an r-colouring χ of the sequence X is canonical if χ(xi) = χ(xj) whenever xi = xj. We prove that for any fixedt the length of the shortest sequence over an alphabet of size t, which has the property that every r-colouring of its entries contains a t-universal and canonically coloured subsequence, is at most $cr^{\lfloor\frac{t}{2}\rfloor}$. This is best possible up to a multiplicative constant c independent of r. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1017/S0963548309009961 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
multiplicative constant c,t-universal sequence,canonically coloured subsequence,related ramsey-type problem,canonically coloured sequence,sequence x,minimum length,shortest sequence | Discrete mathematics,Combinatorics,Multiplicative function,Permutation,Subsequence,Mathematics,Alphabet | Journal |
Volume | Issue | ISSN |
18 | 5 | 0963-5483 |
Citations | PageRank | References |
1 | 0.38 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 114 | 23.10 |
| Peter Frankl | 2 | 578 | 126.03 |
| Vojtěch Rödl | 3 | 887 | 142.68 |