Unavoidable Multicoloured Families of Configurations

Publication date 14 September 2014

Abstract: Balogh and Bollob'as [{em Combinatorica 25, 2005}] prove that for any

k

there is a constant

f (k)

such that any set system with at least

f (k)

sets reduces to a

k

-star, an

k

-costar or an

k

-chain. They proved

f (k) < (2 k)^{2^{k}}

. Here we improve it to

f (k) < 2^{c k^{2}}

for some constant

c > 0

. This is a special case of the following result on the multi-coloured forbidden configurations at 2 colours. Let

r

be given. Then there exists a constant

c_{r}

so that a matrix with entries drawn from

0, 1, ..., r - 1

with at least

2^{c_{r} k^{2}}

different columns will have a

k i m e s k

submatrix that can have its rows and columns permuted so that in the resulting matrix will be either

I_{k} (a, b)

or

T_{k} (a, b)

(for some

a e b i n 0, 1, ..., r - 1

), where

I_{k} (a, b)

is the

k i m e s k

matrix with

a

's on the diagonal and

b

's else where,

T_{k} (a, b)

the

k i m e s k

matrix with

a

's below the diagonal and

b

's elsewhere. We also extend to considering the bound on the number of distinct columns, given that the number of rows is

m

, when avoiding a

t k i m e s k

matrix obtained by taking any one of the

k i m e s k

matrices above and repeating each column

t

times. We use Ramsey Theory.

This page was built for publication: Unavoidable Multicoloured Families of Configurations