Colorings of $k$-sets with low discrepancy on small sets
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908697863651328 |
|---|---|
| author | Pudlák, Pavel Rödl, Vojtěch |
| author_facet | Pudlák, Pavel Rödl, Vojtěch |
| contents | For $0<δ\leq 1$, let $R_k(m;δ)$ denote the smallest $N$ such that every coloring of $k$-element subsets by two colors yields an $m$-element set $M$ with relative discrepancy $δ$, which means that one color class has at least $(\frac{1+δ}2){m\choose k}$ elements. The number $R_k(m;δ)$ may be viewed as an extension of the usual $k$-hypergraph Ramsey number because $R_k(m)=R_k(m,1)$. Our main result is the following theorem.
%\begin{theorem} For some constants $c,k_0$, and $\eps>0$, and for all $k\geq k_0$, $c\log k\leq n\leq k/11$, \[ R_k(k+n);2^{-\eps n})\geq \tw_{\lfloor k/n\rfloor}(2). \] %\end{theorem}
In particular, for $n=\lceil c\log k\rceil$, we get a tower of height $δk/\log k$ and relative discrepancy polynomial in~$k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05286 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Colorings of $k$-sets with low discrepancy on small sets Pudlák, Pavel Rödl, Vojtěch Combinatorics 05D10 For $0<δ\leq 1$, let $R_k(m;δ)$ denote the smallest $N$ such that every coloring of $k$-element subsets by two colors yields an $m$-element set $M$ with relative discrepancy $δ$, which means that one color class has at least $(\frac{1+δ}2){m\choose k}$ elements. The number $R_k(m;δ)$ may be viewed as an extension of the usual $k$-hypergraph Ramsey number because $R_k(m)=R_k(m,1)$. Our main result is the following theorem. %\begin{theorem} For some constants $c,k_0$, and $\eps>0$, and for all $k\geq k_0$, $c\log k\leq n\leq k/11$, \[ R_k(k+n);2^{-\eps n})\geq \tw_{\lfloor k/n\rfloor}(2). \] %\end{theorem} In particular, for $n=\lceil c\log k\rceil$, we get a tower of height $δk/\log k$ and relative discrepancy polynomial in~$k$. |
| title | Colorings of $k$-sets with low discrepancy on small sets |
| topic | Combinatorics 05D10 |
| url | https://arxiv.org/abs/2402.05286 |