Tight bounds towards Zarankiewicz problem in hypergraph
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909850475167744 |
|---|---|
| author | Gao, Guorong Hou, Jianfeng Huang, Shuping Wang, Hezhi |
| author_facet | Gao, Guorong Hou, Jianfeng Huang, Shuping Wang, Hezhi |
| contents | The classical Zarankiewicz problem, which concerns the maximum number of edges in a bipartite graph without a forbidden complete bipartite subgraph, motivates a direct analogue for hypergraphs. Let $K_{s_1,\ldots, s_r}$ be the complete $r$-partite $r$-graph such that the $i$-th part has $s_i$ vertices. We say an $r$-partite $r$-graph $H=H(V_1,\ldots,V_r)$ contains an ordered $K_{s_1,\ldots, s_r}$ if $K_{s_1,\ldots, s_r}$ is a subgraph of $H$ and the set of size $s_i$ vertices is embedded in $V_i$. The Zarankiewicz number for $r$-graph, denoted by $z(m_1, \ldots, m_{r}; s_1,, \ldots,s_{r})$, is the maximum number of edges of the $r$-partite $r$-graph whose $i$-th part has $m_i$ vertices and does not contain an ordered $K_{s_1,\ldots, s_r}$. In this paper, we show that $$z(m_1,m_2, \cdots, m_{r-1},n ; s_1,s_2, \cdots,s_{r-1}, t)=Θ\left(m_1m_2\cdots m_{r-1} n^{1-1 / s_1s_2\cdots s_{r-1}}\right)$$ for a range of parameters. This extends a result of Conlon [Math. Proc. Camb. Philos. Soc. (2022)]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_14869 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight bounds towards Zarankiewicz problem in hypergraph Gao, Guorong Hou, Jianfeng Huang, Shuping Wang, Hezhi Combinatorics The classical Zarankiewicz problem, which concerns the maximum number of edges in a bipartite graph without a forbidden complete bipartite subgraph, motivates a direct analogue for hypergraphs. Let $K_{s_1,\ldots, s_r}$ be the complete $r$-partite $r$-graph such that the $i$-th part has $s_i$ vertices. We say an $r$-partite $r$-graph $H=H(V_1,\ldots,V_r)$ contains an ordered $K_{s_1,\ldots, s_r}$ if $K_{s_1,\ldots, s_r}$ is a subgraph of $H$ and the set of size $s_i$ vertices is embedded in $V_i$. The Zarankiewicz number for $r$-graph, denoted by $z(m_1, \ldots, m_{r}; s_1,, \ldots,s_{r})$, is the maximum number of edges of the $r$-partite $r$-graph whose $i$-th part has $m_i$ vertices and does not contain an ordered $K_{s_1,\ldots, s_r}$. In this paper, we show that $$z(m_1,m_2, \cdots, m_{r-1},n ; s_1,s_2, \cdots,s_{r-1}, t)=Θ\left(m_1m_2\cdots m_{r-1} n^{1-1 / s_1s_2\cdots s_{r-1}}\right)$$ for a range of parameters. This extends a result of Conlon [Math. Proc. Camb. Philos. Soc. (2022)]. |
| title | Tight bounds towards Zarankiewicz problem in hypergraph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.14869 |