|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Unavoidable Multicoloured Families of Configurations | | Richard P. Anstee
; Linyuan Lu
; | | Date: |
29 Sep 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)<(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,...,r-1}$ with
at least $2^{c_rk^2}$ different columns will have a $k imes 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 bin {0,1,..., r-1}$), where
$I_k(a,b)$ is the $k imes k$ matrix with $a$’s on the diagonal and $b$’s else
where, $T_k(a,b)$ the $k imes 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 imes k$ matrix obtained by taking any one of the $k imes k$ matrices above
and repeating each column $t$ times. We use Ramsey Theory. | | Source: | arXiv, 1409.4123 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER