2025-11-10T03:02:02.480547

Tight bounds towards Zarankiewicz problem in hypergraph

Gao, Hou, Huang et al.

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)].

academic

Tight bounds towards Zarankiewicz problem in hypergraph

基本信息

论文ID: 2510.14869
标题: Tight bounds towards Zarankiewicz problem in hypergraph
作者: Guorong Gao, Jianfeng Hou, Shuping Huang, Hezhi Wang
分类: math.CO (组合数学)
发表时间: 2025年10月16日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.14869

摘要

经典的Zarankiewicz问题研究不包含禁用完全二分子图的二分图中的最大边数，本文将其推广到超图。对于完全r-部r-超图 $K_{s_1,\ldots,s_r}$ ，其第i部有 $s_i$ 个顶点，本文定义了r-超图的Zarankiewicz数 $z(m_1,\ldots,m_r; s_1,\ldots,s_r)$ ，即第i部有 $m_i$ 个顶点且不包含有序 $K_{s_1,\ldots,s_r}$ 的r-部r-超图的最大边数。主要结果证明了在一定参数范围内： $z(m_1,m_2,\cdots,m_{r-1},n; s_1,s_2,\cdots,s_{r-1},t) = \Theta\left(m_1m_2\cdots m_{r-1} n^{1-1/s_1s_2\cdots s_{r-1}}\right)$ 这一结果推广了Conlon在2022年的工作。

研究背景与动机

问题背景

经典Zarankiewicz问题：研究不包含特定完全二分子图 $K_{s,t}$ 的二分图 $G(m,n)$ 的最大边数 $z(m,n;s,t)$
Turán理论：经典的Erdős-Stone-Simonovits定理给出了不包含给定子图的图的最大边数估计
超图推广：将二分图的Zarankiewicz问题自然推广到r-uniform超图

研究动机

理论完善：超图的Zarankiewicz问题是组合数学中的基本问题，需要建立完整的理论框架
技术挑战：从图到超图的推广在技术上具有挑战性，需要新的证明技术
应用价值：超图在计算机科学、信息论等领域有重要应用

现有方法局限性

Kővári-Sós-Turán定理只给出上界： $z(m,n;s,t) = O(mn^{1-1/s})$
Conlon的结果仅适用于二分图情况
缺乏超图情况下的紧界结果

核心贡献

建立超图Zarankiewicz问题的理论框架：给出了r-部r-超图中有序完全子图的精确定义
证明了超饱和定理：推广了经典的Erdős超饱和定理到超图情况（定理1.1）
给出上界：推广Kővári-Sós-Turán定理到超图（推论1.2）
建立下界：使用随机代数方法证明匹配的下界（定理1.3）
获得紧界：在特定参数范围内建立了渐近紧的界（推论1.4）

方法详解

任务定义

输入：参数 $m_1,\ldots,m_r$ （各部大小）和 $s_1,\ldots,s_r$ （禁用子图大小）输出：Zarankiewicz数 $z(m_1,\ldots,m_r; s_1,\ldots,s_r)$ 的渐近估计约束：不包含有序 $K_{s_1,\ldots,s_r}$ 作为子超图

核心定义

r-uniform超图：边集为r-元子集的超图
有序 $K_{s_1,\ldots,s_r}$ ：完全r-部r-超图，第i部的 $s_i$ 个顶点嵌入在 $V_i$ 中
Zarankiewicz数： $z(m_1,\ldots,m_r; s_1,\ldots,s_r)$ 为满足条件的最大边数

主要技术方法

1. 超饱和定理（定理1.1）

使用归纳法和双重计数技术：

基础情况（r=2）：标准双重计数，利用Jensen不等式
归纳步骤：通过link-hypergraph技术将r-超图问题约化为(r-1)-超图问题

关键不等式： $t_{s_1,1} = \sum_{v \in V_2} \binom{d(v)}{s_1} \geq m_2 \binom{e/m_2}{s_1}$

2. 随机代数方法（定理1.3）

推广Bukh的随机代数方法到超图：

构造过程：

将顶点类 $(u^1_{p_1}, \ldots, u^{r-1}_{p_{r-1}})$ 关联到 $(s_1s_2\cdots s_{r-1}-1)$ -元多项式 $f_{p_1,\ldots,p_{r-1}}$
每个顶点类连接到点集： $S_{p_1,\ldots,p_{r-1}} = \{(x_1,\ldots,x_{s-1}, f_{p_1,\ldots,p_{r-1}}(x_1,\ldots,x_{s-1})) : x_i \in \mathbb{F}_q\}$

关键引理2.5：存在多项式选择使得交集 $T_{a_1,a_2} \cap \cdots \cap T_{a_1,a_j}$ 的维数至多为 $s-j$

技术创新点

维数控制：通过代数几何中的维数理论控制交集大小
归纳构造：逐步选择多项式，保证维数条件
概率分析：使用Lemma 2.1估计随机多项式通过指定点的概率

理论结果

主要定理

定理1.1（超饱和定理）：如果r-部r-超图H的边数满足 $|E(H)| \geq c_1 \cdot (\prod_{i=1}^{r-1} m_i) \cdot m_r^{1-1/(s_1s_2\cdots s_{r-1})}$ ，则H包含至少 $c_2 \cdot \prod_{i=1}^r \binom{m_i}{s_i} \cdot p^{\prod_{i=1}^r s_i}$ 个有序 $K_{s_1,\ldots,s_r}$ 的拷贝。

推论1.2（上界）： $z(m_1,\ldots,m_r; s_1,\ldots,s_r) = O(m_1\cdots m_{r-1} m_r^{1-1/(s_1\cdots s_{r-1})})$

定理1.3（下界）：在条件 $s \leq t$ 和 $m \leq n^{t^{1/s-1}/s(s-1)}$ 下， $z(m_1,\ldots,m_{r-1},n; s_1,\ldots,s_{r-1},t) = \Omega(m_1\cdots m_{r-1} n^{1-1/(s_1\cdots s_{r-1})})$