A tower lower bound for the degree relaxation of the Regularity Lemma
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916439643914240 |
|---|---|
| author | Garbe, Frederik Hladký, Jan |
| author_facet | Garbe, Frederik Hladký, Jan |
| contents | It is well-known that if $(A,B)$ is an $\tfrac{\varepsilon}{2}$-regular pair (in the sense of Szemerédi) then there exist sets $A'\subset A$ and $B'\subset B'$ with $|A'|\leq \varepsilon|A|$ and $|B'|\leq \varepsilon|B|$ so that the degrees of all vertices in $A\setminus A'$ differ by at most $\varepsilon|B|$ and the degrees of all vertices in $B\setminus B'$ differ by at most $\varepsilon|A|$. We call such a property "$\varepsilon$-degularity". This leads to the notion of an "$\varepsilon$-degular" partition of a graph in the same way as the definition of $\varepsilon$-regular pairs leads to the notion of $\varepsilon$-regular partitions. We show that there exist graphs in which any $\varepsilon$-degular partition requires the number of clusters to be $\mathrm{tower}(Θ(\varepsilon^{-1/3}))$. That is, even though degularity is a substantial relaxation of regularity, in general one cannot improve much on the bounds that come with Szemerédi's regularity lemma. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05023 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A tower lower bound for the degree relaxation of the Regularity Lemma Garbe, Frederik Hladký, Jan Combinatorics It is well-known that if $(A,B)$ is an $\tfrac{\varepsilon}{2}$-regular pair (in the sense of Szemerédi) then there exist sets $A'\subset A$ and $B'\subset B'$ with $|A'|\leq \varepsilon|A|$ and $|B'|\leq \varepsilon|B|$ so that the degrees of all vertices in $A\setminus A'$ differ by at most $\varepsilon|B|$ and the degrees of all vertices in $B\setminus B'$ differ by at most $\varepsilon|A|$. We call such a property "$\varepsilon$-degularity". This leads to the notion of an "$\varepsilon$-degular" partition of a graph in the same way as the definition of $\varepsilon$-regular pairs leads to the notion of $\varepsilon$-regular partitions. We show that there exist graphs in which any $\varepsilon$-degular partition requires the number of clusters to be $\mathrm{tower}(Θ(\varepsilon^{-1/3}))$. That is, even though degularity is a substantial relaxation of regularity, in general one cannot improve much on the bounds that come with Szemerédi's regularity lemma. |
| title | A tower lower bound for the degree relaxation of the Regularity Lemma |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.05023 |