Zarankiewicz bounds from distal regularity lemma
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910005683290112 |
|---|---|
| author | Tong, Mervyn |
| author_facet | Tong, Mervyn |
| contents | Since Kővári, Sós, and Turán proved upper bounds for the Zarankiewicz problem in 1954, much work has been undertaken to improve these bounds, and some have done so by restricting to particular classes of graphs. In 2017, Fox, Pach, Sheffer, Suk, and Zahl proved better bounds for semialgebraic binary relations, and this work was extended by Do in the following year to arbitrary semialgebraic relations. In this paper, we show that Zarankiewicz bounds in the shape of Do's are enjoyed by all relations satisfying the distal regularity lemma, an improved version of the Szemerédi regularity lemma satisfied by relations definable in distal structures (a vast generalisation of o-minimal structures). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_13695 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Zarankiewicz bounds from distal regularity lemma Tong, Mervyn Combinatorics Logic Primary 05C35, 05C75. Secondary 03C45, 03C64 Since Kővári, Sós, and Turán proved upper bounds for the Zarankiewicz problem in 1954, much work has been undertaken to improve these bounds, and some have done so by restricting to particular classes of graphs. In 2017, Fox, Pach, Sheffer, Suk, and Zahl proved better bounds for semialgebraic binary relations, and this work was extended by Do in the following year to arbitrary semialgebraic relations. In this paper, we show that Zarankiewicz bounds in the shape of Do's are enjoyed by all relations satisfying the distal regularity lemma, an improved version of the Szemerédi regularity lemma satisfied by relations definable in distal structures (a vast generalisation of o-minimal structures). |
| title | Zarankiewicz bounds from distal regularity lemma |
| topic | Combinatorics Logic Primary 05C35, 05C75. Secondary 03C45, 03C64 |
| url | https://arxiv.org/abs/2410.13695 |