.png){kind=icon}
.png){kind=icon}
Return
Hypergraphs without complete partite subgraphs
.png){kind=icon}
PRE
AI
DOI：10.1017/S0963548325100321.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Fix integers $r \ge 2$ and $1\le s_1\le \cdots \le s_{r-1}\le t$ and set $s=\prod _{i=1}<^>{r-1}s_i$ . Let $K=K(s_1, \ldots , s_{r-1}, t)$ denote the complete $r$ -partite $r$ -uniform hypergraph with parts of size $s_1, \ldots , s_{r-1}, t$ . We prove that the Zarankiewicz number $z(n, K)= n<^>{r-1/s-o(1)}$ provided $t\gt 3<^>{s+o(s)}$ . Previously this was known only for $t \gt ((r-1)(s-1))!$ due to Pohoata and Zakharov. Our novel approach, which uses Behrend's construction of sets with no 3-term arithmetic progression, also applies for small values of $s_i$ , for example, it gives $z(n, K(2,2,7))=n<^>{11/4-o(1)}$ where the exponent 11/4 is optimal, whereas previously this was only known with 7 replaced by 721.
Keywords:
Hypergraphs
Zarankiewicz problem
induced matchings
Journal
C
IF:
0.8
Papers:
30
Citations:
0
