IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Unavoidable Multicoloured Families of Configurations

  • Sept. 12, 2014
  • 2:30 p.m.
  • LeConte 312


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)<(2k)^{2^k}$. Here we improve it to $f(k)<2^{ck^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,\ldots ,r-1\}$ with at least $2^{c _ rk^2}$ different columns will have a $k\times 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\ne b\in \{0,1,\ldots, r-1\}$), where $I _ k(a,b)$ is the $k\times k$ matrix with $a$'s on the diagonal and $b$'s else where, $T _ k(a,b)$ the $k\times 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 seeking a $t k\times k$ matrix obtained by taking one of the $k \times k$ matrices above and repeating each column $t$ times. We use Ramsey Theory.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster