Weak randomness in graphons and theons
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913437461774336 |
|---|---|
| author | Coregliano, Leonardo N. Malliaris, Maryanthe |
| author_facet | Coregliano, Leonardo N. Malliaris, Maryanthe |
| contents | Call a hereditary family $\mathcal{F}$ of graphs strongly persistent if there exists a graphon $W$ such that in all subgraphons $W'$ of $W$, $\mathcal{F}$ is precisely the class of finite graphs that have positive density in $W'$. Our first result is a complete characterization of the hereditary families of graphs that are strongly persistent as precisely those that are closed under substitutions.
We call graphons with the self-similarity property above weakly random. A hereditary family $\mathcal{F}$ is said to have the weakly random Erdős--Hajnal property (WR) if every graphon that is a limit of graphs in $\mathcal{F}$ has a weakly random subgraphon. Among families of graphs that are closed under substitutions, we completely characterize the families that belong to WR as those with "few" prime graphs.
We also extend some of the results above to structures in finite relational languages by using the theory of theons. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_08638 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Weak randomness in graphons and theons Coregliano, Leonardo N. Malliaris, Maryanthe Combinatorics Logic Primary: 05C80, Secondary: 05C75, 03C13, 05C65, 28A35 Call a hereditary family $\mathcal{F}$ of graphs strongly persistent if there exists a graphon $W$ such that in all subgraphons $W'$ of $W$, $\mathcal{F}$ is precisely the class of finite graphs that have positive density in $W'$. Our first result is a complete characterization of the hereditary families of graphs that are strongly persistent as precisely those that are closed under substitutions. We call graphons with the self-similarity property above weakly random. A hereditary family $\mathcal{F}$ is said to have the weakly random Erdős--Hajnal property (WR) if every graphon that is a limit of graphs in $\mathcal{F}$ has a weakly random subgraphon. Among families of graphs that are closed under substitutions, we completely characterize the families that belong to WR as those with "few" prime graphs. We also extend some of the results above to structures in finite relational languages by using the theory of theons. |
| title | Weak randomness in graphons and theons |
| topic | Combinatorics Logic Primary: 05C80, Secondary: 05C75, 03C13, 05C65, 28A35 |
| url | https://arxiv.org/abs/2209.08638 |