Growth of regular partitions 3: strong regularity and the vertex partition
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915422439211008 |
|---|---|
| author | Terry, C. |
| author_facet | Terry, C. |
| contents | We consider here the strong regularity for $3$-uniform hypergraphs developed by Frankl, Gowers, Kohayakawa, Nagle, Rödl, Skokan, and Schacht. This type of regular decomposition comes with two components, a partition of the vertices, and a partition of the pairs of vertices. The data of a regular decomposition also includes two parameters measuring quasirandomness, a fixed constant $ε_1>0$, and a function $ε_2:\mathbb{N}\rightarrow (0,1]$. We define two growth functions associated to a hereditary property $\mathcal{H}$ of $3$-uniform hypergraphs: $T_{\mathcal{H}}(ε_1,ε_2)$ which measures the size of the vertex component, and $L_{\mathcal{H}}(ε,ε_2)$ which measures the size of the pairs component. We introduce the following question. What are the possible asymptotic growth rates of functions of the form $T_{\mathcal{H}}$ and $L_{\mathcal{H}}$? In this paper, we consider this question for $T_{\mathcal{H}}$, proving a separation into four classes: constant, polynomial, exponential, or at least wowzer. The separations among the constant, polynomial and exponential ranges require only slow growing (namely polynomial) choices for $ε_2$. The jump to the wowzer range uses a very fast growing $ε_2$ and makes crucial use of a lower bound construction for strong graph regularity due to Conlon and Fox. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02024 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Growth of regular partitions 3: strong regularity and the vertex partition Terry, C. Combinatorics Logic We consider here the strong regularity for $3$-uniform hypergraphs developed by Frankl, Gowers, Kohayakawa, Nagle, Rödl, Skokan, and Schacht. This type of regular decomposition comes with two components, a partition of the vertices, and a partition of the pairs of vertices. The data of a regular decomposition also includes two parameters measuring quasirandomness, a fixed constant $ε_1>0$, and a function $ε_2:\mathbb{N}\rightarrow (0,1]$. We define two growth functions associated to a hereditary property $\mathcal{H}$ of $3$-uniform hypergraphs: $T_{\mathcal{H}}(ε_1,ε_2)$ which measures the size of the vertex component, and $L_{\mathcal{H}}(ε,ε_2)$ which measures the size of the pairs component. We introduce the following question. What are the possible asymptotic growth rates of functions of the form $T_{\mathcal{H}}$ and $L_{\mathcal{H}}$? In this paper, we consider this question for $T_{\mathcal{H}}$, proving a separation into four classes: constant, polynomial, exponential, or at least wowzer. The separations among the constant, polynomial and exponential ranges require only slow growing (namely polynomial) choices for $ε_2$. The jump to the wowzer range uses a very fast growing $ε_2$ and makes crucial use of a lower bound construction for strong graph regularity due to Conlon and Fox. |
| title | Growth of regular partitions 3: strong regularity and the vertex partition |
| topic | Combinatorics Logic |
| url | https://arxiv.org/abs/2404.02024 |